diff options
| -rw-r--r-- | controle-20091124.tex | 24 |
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} + % % % |