From 1beac514711d848407c3e56ff43734a5d324ac1a Mon Sep 17 00:00:00 2001
From: david <david>
Date: Tue, 17 Nov 2009 18:21:46 +0000
Subject: Correct exercise 3.

---
 controle-20091124.tex | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

(limited to 'controle-20091124.tex')

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}
+
 %
 %
 %
-- 
cgit v1.2.3