Another exercise.

1 files changed, 161 insertions, 3 deletions

diff --git a/controle-20111122.tex b/controle-20111122.tex
index 4a85454..45aed92 100644
--- a/controle-20111122.tex
+++ b/controle-20111122.tex
@@ -28,7 +28,7 @@
 \DeclareUnicodeCharacter{00A0}{~}
 %
 \newif\ifcorrige
-\corrigefalse
+\corrigetrue
 \newenvironment{corrige}%
 {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
 \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
@@ -74,6 +74,162 @@ Durée : 2h
 
 \exercice
 
+(1a) Rappeler pourquoi, si $x$ n'est pas multiple de $13$, alors
+$x^{12} \equiv 1 \pmod{13}$, et pourquoi, si $x$ n'est pas multiple de
+$19$, alors $x^{18} \equiv 1 \pmod{19}$.
+
+\begin{corrige}
+Cela découle, dans les deux cas, du petit théorème de Fermat ($x^{p-1}
+\equiv 1 \pmod{p}$ si $p$ est premier et $x$ non multiple de $p$).
+\end{corrige}
+
+(1b) En déduire que, si $x$ n'est pas multiple de $13$, alors $x^{36}
+\equiv 1 \pmod{13}$, et que, si $x$ n'est pas multiple de $19$, alors
+$x^{36} \equiv 1 \pmod{19}$.
+
+\begin{corrige}
+On a $36 = 12\times 3$ ; donc, si on a $x^{12} \equiv 1 \pmod{13}$
+(pour $x$ non multiple de $13$), alors en particulier $x^{36} =
+x^{12\times 3} = (x^{12})^3 \equiv 1 \pmod{13}$.  De la même façon,
+puisque $36 = 18\times 2$, le fait que $x^{18} \equiv 1 \pmod{19}$
+entraîne $x^{36} \equiv 1 \pmod{19}$.
+\end{corrige}
+
+(2) Conclure de la question précédente que si $x$ est premier avec
+$247$, alors $x^{36} \equiv 1 \pmod{247}$ (remarque : $247 = 13 \times
+19$).
+
+\begin{corrige}
+Dire que $x$ est premier avec $247 = 13 \times 19$ signifie que $x$
+n'est multiple ni de $13$ ni de $19$.  D'après la question précédente,
+on a alors $x^{36} \equiv 1$ modulo $13$ et modulo $19$.  Le théorème
+chinois implique, vu que $13$ et $19$ sont premiers entre eux, que
+cette congruence $x^{36} \equiv 1$ vaut encore modulo $13\times 19 =
+247$.  (Ou, de façon équivalente, $x^{36} - 1$ est multiple de $13$ et
+de $19$, donc de $247$.)
+\end{corrige}
+
+(3) Que vaut $\varphi(247)$ (où bien sûr $\varphi$ désigne
+l'indicatrice d'Euler) ?
+
+\begin{corrige}
+On a $\varphi(13\times 19) = (13-1)\times(19-1) = 12\times 18 = 216$.
+\end{corrige}
+
+(4) En oubliant provisoirement les questions (1) et (2), quel théorème
+connu permettait d'énoncer le fait que $x^N \equiv 1 \pmod{247}$ si
+$x$ est premier avec $247$, pour un certain $N$ (à préciser) ne
+dépendant pas de $x$ ?  Comparer ce résultat avec celui de la
+question (2), et commenter (lequel est le plus fort ?).
+
+\begin{corrige}
+Le théorème d'Euler assure que $x^{\varphi(247)} \equiv 1 \pmod{247}$
+pour tout $x$ premier avec $247$, c'est-à-dire $x^{216} \equiv 1
+\pmod{247}$ (bref, $N=216$ convient).  La question (2) affirmait la
+même chose pour $N=36$.  Cette dernière est donc plus forte (comme
+$36$ divise $216$, le fait que $x^{36} \equiv 1$ entraîne
+automatiquement $x^{216} \equiv 1$).
+\end{corrige}
+
+(5) Rappeler pourquoi il existe $g_1$ (resp. $g_2$) un élément de
+$(\mathbb{Z}/13\mathbb{Z})^\times$
+(resp. $(\mathbb{Z}/19\mathbb{Z})^\times$) dont l'ordre multiplicatif
+vaut exactement $12$ (resp. $18$) : comment appelle-t-on un tel
+élément ?
+
+\begin{corrige}
+Un tel élément s'appelle un élément primitif.  Il existe car $13$
+(resp. $19$) est premier.
+\end{corrige}
+
+(6) Rappeler pourquoi il existe $h \in
+(\mathbb{Z}/247\mathbb{Z})^\times$ tel que $h \equiv g_1 \pmod{13}$ et
+$h \equiv g_2 \pmod{19}$.
+
+\begin{corrige}
+Un tel $h$ existe d'après le théorème chinois, qui garantit que la
+donnée d'une congruence quelconque modulo $13$ et d'une congruence
+quelconque modulo $19$ peut toujours s'écrire comme une unique
+congruence modulo $13\times 19 = 247$ (de nouveau, parce que $13$ et
+$19$ sont premiers entre eux).
+\end{corrige}
+
+(7) Montrer que l'ordre multiplicatif (modulo $247$) d'un tel $h$ vaut
+exactement $36$.  Quel est l'ordre multiplicatif maximal possible d'un
+élément de $(\mathbb{Z}/247\mathbb{Z})^\times$ ?
+
+\begin{corrige}
+Supposons que $h^s \equiv 1 \pmod{247}$ pour un certain entier $s$.
+Alors, en réduisant modulo $13$, puisque $h \equiv g_1 \pmod{13}$, on
+a $g_1^s \equiv 1 \pmod{13}$, ce qui, vu que $g_1$ est d'ordre
+exactement $12$, entraîne que $s$ est multiple de $12$.  De même,
+$g_2^s \equiv 1 \pmod{19}$, ce qui entraîne que $s$ est multiple
+de $18$.  On en conclut que $s$ est multiple de $\ppcm(12,18) = 36$.
+
+On a vu en (2) que l'ordre multiplicatif de tout élément de
+$(\mathbb{Z}/247\mathbb{Z})^\times$ divise $36$, on vient de voir
+qu'il existe des éléments d'ordre $36$, donc l'ordre maximal possible
+est $36$.
+\end{corrige}
+
+(8) Dresser la table des puissances de $2$ modulo $13$ puis
+modulo $19$.
+
+\begin{corrige}
+Modulo $13$, on calcule (de proche en proche) :
+
+{\noindent\footnotesize
+\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c}
+$s$&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$&$10$&$11$\\\hline
+$2^s$&$1$&$2$&$4$&$8$&$3$&$6$&$12$&$11$&$9$&$5$&$10$&$7$\\
+\end{tabular}
+\par}
+
+Ces douze puissances sont distinctes (après quoi on retombe sur $1$),
+donc $2$ est primitif modulo $13$.
+
+Modulo $19$, on calcule (de proche en proche) :
+
+{\noindent\footnotesize
+\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
+$s$&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$&$10$&$11$&$12$&$13$&$14$&$15$&$16$&$17$\\\hline
+$2^s$&$1$&$2$&$4$&$8$&$16$&$13$&$7$&$14$&$9$&$18$&$17$&$15$&$11$&$3$&$6$&$12$&$5$&$10$\\
+\end{tabular}
+\par}
+
+Ces dix-huit puissances sont distinctes (après quoi on retombe
+sur $1$), donc $2$ est primitif modulo $19$.
+\end{corrige}
+
+(9) Montrer que $2$ est d'ordre multiplicatif $36$ modulo $247$.
+
+\begin{corrige}
+On vient de voir que $g_1 = 2$ est primitif modulo $13$ et que $g_2 =
+2$ l'est modulo $19$, donc $h = 2$ est primitif modulo $13\times 19 =
+247$ d'après la question (7).
+\end{corrige}
+
+(10) Montrer que l'élément $\bar 3 \in
+(\mathbb{Z}/247\mathbb{Z})^\times$ \emph{n'est pas} une puissance
+de $2$ (on justifiera la réponse).
+
+\begin{corrige}
+Si $2^s \equiv 3 \pmod{247}$, on a $2^s \equiv 3 \pmod{13}$ et $2^s
+\equiv 3 \pmod{19}$.  La première partie donne $s \equiv 4 \pmod{12}$
+d'après la table des puissances de $2$ modulo $13$ qu'on a calculée.
+La seconde condition donne $s \equiv 13 \pmod{18}$ d'après la table
+des puissances de $2$ modulo $18$.  Ces deux conditions ne sont pas
+compatibles (la première implique que $s$ est pair, la seconde, que
+$s$ est impair) : la prémisse est donc absurde, c'est-à-dire que $3$
+n'est pas une puissance de $2$ modulo $247$.
+\end{corrige}
+
+%
+%
+%
+
+\exercice
+
 Soit $p$ un nombre premier tel que $p \equiv 3 \pmod{4}$.
 
 (1) Montrer que $(p-1)/2$ est impair.  Que vaut $(-1)^{(p-1)/2}$ ?
@@ -258,7 +414,7 @@ donc $u_r^2 + v_r^2 = 1$.
 Si $0 \leq r \leq p$, c'est-à-dire $0 \leq r < p+1$, alors $0 \leq
 r(p-1) < p^2-1$.  Puisque $g$ est d'ordre exactement $p^2-1$, les
 $g^s$ pour $0 \leq s < p^2-1$ sont deux-à-deux distincts, et en
-particulire les $g^{r(p-1)}$ pour $0 \leq r < p+1$ le sont.  Comme par
+particulier les $g^{r(p-1)}$ pour $0 \leq r < p+1$ le sont.  Comme par
 ailleurs $u_r$ et $v_r$ déterminent complètement $u_r + v_r
 \sqrt{-1}$, les couples $(u_r,v_r)$ avec $0 \leq r \leq p$ sont
 eux-mêmes deux-à-deux distincts.
@@ -267,7 +423,9 @@ eux-mêmes deux-à-deux distincts.
 (14) Réciproquement, si $u,v$ dans $\mathbb{F}_p$ vérifient $u^2 + v^2
 = 1$, montrer que $u + v\sqrt{-1}$ peut s'écrire sous la forme
 $g^{r(p-1)}$ (on a donc $(u,v) = (u_r,v_r)$) pour un certain $r$ qu'on
-peut trouver vérifiant $0 \leq r \leq p$.
+peut trouver vérifiant $0 \leq r \leq p$.  (On pourra commencer par
+écrire $u + v\sqrt{-1} = g^s$ pour un certain $s$, puis montrer que
+celui-ci est un multiple de $p-1$ en utilisant $u^2 + v^2 = 1$.)
 
 \begin{corrige}
 Comme $g$ est primitif, on peut écrire $u + v\sqrt{-1} = g^s$ pour un