summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2010-10-04 16:22:11 (GMT)
committerDavid A. Madore <david+git@madore.org>2010-10-04 16:22:11 (GMT)
commit668f84d0c4f39b92715ef5bd2b65c32fad21a3e8 (patch)
treefe27e5c50661597f6703f41015ce503008fadf4a
parent30b4ef2ae7f9391e948a5a1369886ebfdd58a6e0 (diff)
downloadinfmdi720-668f84d0c4f39b92715ef5bd2b65c32fad21a3e8.zip
infmdi720-668f84d0c4f39b92715ef5bd2b65c32fad21a3e8.tar.gz
infmdi720-668f84d0c4f39b92715ef5bd2b65c32fad21a3e8.tar.bz2
More exercises on Z/mZ.
-rw-r--r--exercices.tex162
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}