diff options
| -rw-r--r-- | controle-20111122.tex | 164 |
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 |