diff options
| -rw-r--r-- | controle-20081202.tex | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/controle-20081202.tex b/controle-20081202.tex index 75c5a8d..7710f9f 100644 --- a/controle-20081202.tex +++ b/controle-20081202.tex @@ -25,6 +25,14 @@ \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Fr}} % +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\textit{Corrigé.}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\relax\else\egroup\fi\par} +% % % \begin{document} @@ -79,6 +87,30 @@ Les deux questions suivantes sont indépendantes. (2) Pourquoi a-t-on $a^{32} \equiv 1 \pmod{128}$ pour tout $a$ impair (note : $128 = 2^7$) ? +\begin{corrige} +(1) Comme $11$ et $31$ sont premiers entre eux, + $\mathbb{Z}/341\mathbb{Z} \cong (\mathbb{Z}/11\mathbb{Z}) \times + (\mathbb{Z}/31\mathbb{Z})$, donc il suffit de prouver $a^{31} \equiv + a \pmod{31}$ et $a^{31} \equiv a \pmod{11}$ pour tout $a + \in\mathbb{Z}$. Or on a $a^{31} \equiv a \pmod{31}$ d'après le + petit théorème de Fermat ; s'agissant de la relation modulo $11$, on + a $a^{10} \equiv 1 \pmod{11}$ si $11$ ne divise pas $a$ (théorème + d'Euler), donc $a^{30} = (a^{10})^3 \equiv 1 \pmod{11}$ donc $a^{31} + \equiv a \pmod{11}$, et ceci est aussi vrai lorsque $a \equiv 0 + \pmod{11}$, donc dans tous les cas $a^{31} \equiv a \pmod{11}$. + +(2) Le théorème d'Euler ne suffit pas, car $\varphi(128) = 64$ donc il + donne seulement $a^{64} \equiv 1 \pmod{128}$ lorsque $a$ est impair + (ce qui équivaut à premier à $128$). En revanche, on sait (cours) + que $(\mathbb{Z}/128\mathbb{Z})^\times = + (\mathbb{Z}/2^7\mathbb{Z})^\times$ n'a pas d'éléments primitifs : il + est produit d'un groupe cyclique d'ordre $2$ (engendré par $-1$) et + d'un groupe cyclique d'ordre $2^5 = 32$ (engendré par $5$). Si on + note ces deux groupes multiplicativement, on a $a^{32} = a$ dans + chacun d'entre eux par le théorème de Lagrange, donc c'est le cas + dans $(\mathbb{Z}/128\mathbb{Z})^\times$. +\end{corrige} + % % % |