+

+\exercice

+

+(A)�Pour chaque �l�ment de $\mathbb{Z}/18\mathbb{Z}$, calculer son

+ordre additif et, si cela a un sens, son ordre multiplicatif. Quels

+sont les entiers primitifs modulo�$18$�?

+

+(B)�Dresser la table d'un isomorphisme entre le groupe additif

+$\mathbb{Z}/n\mathbb{Z}$ (pour un $n$ � d�terminer) et le groupe

+multiplicatif $(\mathbb{Z}/18\mathbb{Z})^\times$.

+

+(C)�Que vaut $7^{333\,333}$ modulo�$18$�? Que vaut $5^{6\,000\,004}$

+modulo�$18$�?

+

+\begin{corrige}

+(A)\strut\par{\footnotesize

+\begin{tabular}{r|c|c}

+&add.&mult.\\\hline

+$\bar 0$&$1$&---\\

+$\bar 1$&$18$&$1$\\

+$\bar 2$&$9$&---\\

+$\bar 3$&$6$&---\\

+$\bar 4$&$9$&---\\

+$\bar 5$&$18$&$6$\\

+$\bar 6$&$3$&---\\

+$\bar 7$&$18$&$3$\\

+$\bar 8$&$9$&---\\

+$\bar 9$&$2$&---\\

+$\bar{10}$&$9$&---\\

+$\bar{11}$&$18$&$6$\\

+$\bar{12}$&$3$&---\\

+$\bar{13}$&$18$&$3$\\

+$\bar{14}$&$9$&---\\

+$\bar{15}$&$6$&---\\

+$\bar{16}$&$9$&---\\

+$\bar{17}$&$18$&$2$\\

+\end{tabular}

+\par}

+

+Il existe donc des �l�ments primitifs, il en existe

+$\varphi(\varphi(18)) = \varphi(6) = 2$, � savoir $\bar 5$ et

+$\bar{11}$. (Les entiers primitifs modulo�$18$ sont donc ceux congrus

+� $5$ ou $11$ modulo�$18$.)

+

+(B)�Une fois choisi un �l�ment primitif, disons $g = \bar 5$,

+l'isomorphisme $\mathbb{Z}/6\mathbb{Z} \to

+(\mathbb{Z}/18\mathbb{Z})^\times$ est donn� par $\bar k \mapsto g^k$,

+soit ici�:

+

+\begin{tabular}{c|cccccc}

+$\bar k \in \mathbb{Z}/6\mathbb{Z}$&$\bar 0$&$\bar 1$&$\bar 2$&$\bar 3$&$\bar 4$&$\bar 5$\\\hline

+$g^k \in (\mathbb{Z}/18\mathbb{Z})^\times$&$\bar 1$&$\bar 5$&$\bar 7$&$\bar{17}$&$\bar{13}$&$\bar{11}$\\

+\end{tabular}

+

+(C)�On vient de voir que l'ordre de $\bar 7$ dans

+$(\mathbb{Z}/18\mathbb{Z})^\times$ vaut�$3$, donc $7^{3k} \equiv 1

+\pmod{18}$ pour tout�$k$ et en particulier pour $k = 111\,111$, de

+sorte que $7^{333\,333} \equiv 1 \pmod{18}$. Pour ce qui est de

+$5^{6\,000\,004}$, il suffit de chercher la valeur en regard de

+$6\,000\,004$ modulo�$6$ dans le tableau ci-dessus�: on a $5^6 \equiv

+1 \pmod{18}$ donc $5^{6\,000\,000} \equiv 1$ donc $5^{6\,000\,004}

+\equiv 5^4 \equiv 13 \pmod{18}$.

+\end{corrige}

+

+%

+%

+%

+

+\exercice

+

+(A)�Calculer $\varphi(3\,125)$. Que vaut $2^{5\,000\,000}$

+modulo�$3\,125$�?

+

+(B)�Que vaut $2^{5\,000\,000}$ modulo�$32$�?

+

+(C)�Sachant que $293\times 32 - 3\times 3\,125 = 1$, quels sont les

+cinq derniers chiffres en base�$10$ de $2^{5\,000\,000}$�?

+

+\begin{corrige}

+(A)�On a $3\,125 = 5^5$ donc $\varphi(3\,125) = 4\times 5^4 = 2\,500$.

+ Comme $2$ est premier avec $3\,125$, le th�or�me d'Euler entra�ne

+ que $2^{2\,500} \equiv 1 \pmod{3\,125}$, donc $2^{5\,000\,000}

+ \equiv 1 \pmod{3\,125}$ (puisque $2\,500\,|\,5\,000\,000$).

+

+(B)�(Attention � ne pas chercher � appliquer le th�or�me d'Euler�!

+ $2$ n'est pas du tout premier avec�$32$...) On a $32 = 2^5$ donc

+ $32 | 2^{5\,000\,000}$, c'est-�-dire que $2^{5\,000\,000} \equiv 0

+ \pmod{32}$.

+

+(C)�Trouver les cinq derniers chiffres de $2^{5\,000\,000}$ en

+ base�$10$ revient � calculer ce nombre modulo $100\,000 = 10^5 = 2^5

+ \times 5^5 = 32 \times 3\,125$. On vient de le calculer modulo $32$

+ (il vaut�$0$) et modulo $3\,125$ (il vaut $1$). Le th�or�me chinois

+ assure donc que $2^{5\,000\,000}$ est, modulo $100\,000$, l'unique

+ classe de congruence possible qui vaut $0$ modulo $32$ et $1$

+ modulo�$3\,125$. C'est donc $293\times 32 = 1 + 3\times 3\,125 =

+ 9\,376$. Les cinq derniers chiffres de $2^{5\,000\,000}$ en

+ base�$10$ sont donc�: $09376$.

+\end{corrige}

+

+%

+%

+%

+

+\exercice

+

+Les nombres $593$ et $1\,187$ sont premiers.

+

+(A)�Expliquer bri�vement pourquoi, si $b^2 = \bar 1$ avec $b \in

+\mathbb{Z}/1187\mathbb{Z}$ alors $b = \bar 1$ ou $b = -\bar 1$

+(indication�: factoriser $b^2 - \bar 1$).

+

+(B)�Quelles sont les valeurs possibles de $a^{593}$ modulo�$1\,187$

+(pour $a$ un entier quelconque)�?

+

+(C)�Montrer que $a^{593} \equiv -1 \pmod{1\,187}$ si et seulement si

+$a$ est primitif modulo�$1\,187$ \emph{ou} $a \equiv -1

+\pmod{1\,187}$.

+

+\begin{corrige}

+(A)�Si $b^2 = \bar 1$ avec $b \in \mathbb{Z}/1187\mathbb{Z}$, alors

+ $(b-\bar 1)(b+\bar 1) = b^2 - \bar 1 = \bar 0$. Comme

+ $\mathbb{Z}/1187\mathbb{Z}$ est un corps (et en particulier, un

+ anneau int�gre), un produit ne peut �tre nul que si un des deux

+ facteurs est nul, donc soit $b - \bar 1 = \bar 0$, soit $b + \bar 1

+ = \bar 0$, c'est-�-dire soit $b = \bar 1$ soit $b = -\bar 1$.

+

+(B)�On a $1\,186 = 2\times 593$. Le th�or�me d'Euler ou de Fermat

+ assure que $a^{1\,186} \equiv 1 \pmod{1\,187}$ pour tout $a$ non

+ multiple de $1\,187$, c'est-�-dire $(a^{593})^2 \equiv 1

+ \pmod{1\,187}$�: d'apr�s ce qu'on vient de voir, ceci signifie que

+ $a^{593}\equiv 1$ ou $a^{593}\equiv -1$. (Et ces deux cas se

+ produisent effectivement, comme le montrent les exemples de $a=1$ et

+ $a=-1$.) Enfin, si $a$ est multiple de $1\,187$, on a �videmment

+ $a^{593} \equiv 0^{593} = 0 \pmod{1\,187}$. Les trois valeurs

+ possibles sont donc�: $+1, -1, 0$.

+

+(Remarquons que les deux sous-questions ci-dessus n'ont pas utilis� le

+ fait que $593$ �tait premier, et fonctionnaient �galement en

+ rempla�ant $1\,187$ par n'importe quel nombre premier $p$ impair et

+ $593$ par $(p-1)/2$.)

+

+(C)�Tout d'abord, si $a^{593} \not\equiv 0 \pmod{1\,187}$ alors $a$

+ n'est pas multiple de $1\,187$, c'est-�-dire qu'il est premier avec

+ $1\,187$. Lorsque c'est le cas, l'ordre multiplicatif de $a$ doit

+ diviser $\varphi(1\,187) = 2\times 593$�: les diviseurs de ce nombre

+ sont $1$, $2$, $593$ et�$1\,186$. Le seul �l�ment (de n'importe

+ quel groupe, not� multiplicativement) dont l'ordre est $1$ est�$1$

+ (le neutre)�; la premi�re question montre que le seul �l�ment de

+ $(\mathbb{Z}/1187\mathbb{Z})^\times$ dont l'ordre est $2$ est $-1$�;

+ si l'ordre de $a$ est $593$ (en particulier, $a$ n'est pas

+ primitif), alors $a^{593} \equiv 1 \pmod{1\,187}$. Enfin, si

+ l'ordre de $a$ est $1\,186$, c'est-�-dire si $a$ est primitif, alors

+ $a^{593}$ ne peut pas valoir�$1$, et doit donc valoir�$-1$. Tout

+ ceci mis ensemble, on a bien�: $a^{593} \equiv -1 \pmod{1\,187}$ si

+ et seulement si $a \equiv -1 \pmod{1\,187}$ ou bien $a$ est primitif

+ modulo�$1\,187$.

+\end{corrige}

+

+%

+%

+%