From 668f84d0c4f39b92715ef5bd2b65c32fad21a3e8 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 4 Oct 2010 18:22:11 +0200 Subject: More exercises on Z/mZ. --- exercices.tex | 162 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 162 insertions(+) diff --git a/exercices.tex b/exercices.tex index 243bf28..69b61d6 100644 --- a/exercices.tex +++ b/exercices.tex @@ -164,6 +164,168 @@ $192$ modulo les deux congruences demandées. \end{corrige} +% +% +% + +\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} + % % % -- cgit v1.2.3