summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordavid <david>2009-11-17 18:21:46 +0000
committerdavid <david>2009-11-17 18:21:46 +0000
commit1beac514711d848407c3e56ff43734a5d324ac1a (patch)
tree865b1fed1d6b5e5e7070c149781de80aef3cf8eb
parente36a72557f72d6737440a0ae39acb75ad85e6de7 (diff)
downloadinfmdi720-1beac514711d848407c3e56ff43734a5d324ac1a.tar.gz
infmdi720-1beac514711d848407c3e56ff43734a5d324ac1a.tar.bz2
infmdi720-1beac514711d848407c3e56ff43734a5d324ac1a.zip
Correct exercise 3.
-rw-r--r--controle-20091124.tex24
1 files changed, 24 insertions, 0 deletions
diff --git a/controle-20091124.tex b/controle-20091124.tex
index 8274a5d..cc52097 100644
--- a/controle-20091124.tex
+++ b/controle-20091124.tex
@@ -385,6 +385,30 @@ $40\,501$, alors $(n^3)^s \equiv n \pmod{40\,501}$.
(4) Que vaut $8^s$ modulo $40\,501$ ?
+\begin{corrige}
+(1) On a $40\,501 = 101\times 401$ donc $\varphi(40\,501) = 100\times
+ 400 = 40\,000$.
+
+(2) Cherchons une relation de Bézout entre $3$ et $40\,000$ : on a
+ $40\,000 = 13\,333 \times 3 + 1$ donc $1 = 40\,000 - 13\,333\times
+ 3$. Ceci montre que $3$ est inversible d'inverse $-13\,333 \equiv
+ 26\,667 \pmod{40\,000}$ dans $\mathbb{Z}/40\,000\mathbb{Z}$. Disons
+ donc $s = 26\,667$.
+
+(3) Si $n$ est premier avec $40\,501$, on sait que
+ $n^{\varphi(40\,501)} \equiv 1 \pmod{40\,501}$ (théorème d'Euler),
+ c'est-à-dire $n^{40\,000} \equiv 1 \pmod{40\,501}$, et bien sûr
+ $n^{40\,000\,k} \equiv 1 \pmod{40\,501}$ pour tout naturel $k$. Or
+ $3s \equiv 1 \pmod{40\,000}$, c'est-à-dire $3s = 40\,000\,k + 1$
+ pour un certain $k$ (en l'occurrence $k=2$ avec notre choix $s =
+ 26\,667$, mais peu importe). On a donc $(n^3)^s = n^{3s} =
+ n^{40\,000\,k + 1} = n^{40\,000\,k}\cdot n^1 \equiv n
+ \pmod{40\,501}$.
+
+(4) En prenant $n=2$ dans la question précédente, on a montré $8^s
+ \equiv 2 \pmod{40\,501}$.
+\end{corrige}
+
%
%
%