More exercises on Z/mZ.

1 files changed, 162 insertions, 0 deletions

diff --git a/exercices.tex b/exercices.tex
index 243bf28..69b61d6 100644
--- a/exercices.tex
+++ b/exercices.tex
@@ -167,4 +167,166 @@ $192$ modulo $300$ et à $169$ modulo $305$.
 %
 %
 %
+
+\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}
+
+%
+%
+%
 \end{document}