summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2013-11-21 15:26:14 (GMT)
committerDavid A. Madore <david+git@madore.org>2013-11-21 15:26:14 (GMT)
commit002df83e10b139a5c630359e5b3d733cec046fff (patch)
treed64709d9c01c8f3ae2ec20af069e8f8ecd509739
parentf8cd23a92861f51d89c9857e4ab373ae937d1da1 (diff)
downloadinfmdi720-002df83e10b139a5c630359e5b3d733cec046fff.zip
infmdi720-002df83e10b139a5c630359e5b3d733cec046fff.tar.gz
infmdi720-002df83e10b139a5c630359e5b3d733cec046fff.tar.bz2
Exam answers.
-rw-r--r--controle-20131126.tex166
1 files changed, 165 insertions, 1 deletions
diff --git a/controle-20131126.tex b/controle-20131126.tex
index fc8bece..479d18d 100644
--- a/controle-20131126.tex
+++ b/controle-20131126.tex
@@ -81,15 +81,68 @@ Durée : 1h30
(1) Quel est l'ordre multiplicatif de $2$ dans
$\mathbb{F}_{11}^\times$ ? Comment peut-on le qualifier ?
+\begin{corrige}
+On calcule successivement, modulo $11$ :
+
+\begin{tabular}{c|cccccccccccc}
+$i$&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$&$10$\\\hline
+$2^i$&$1$&$2$&$4$&$8$&$5$&$10$&$9$&$7$&$3$&$6$&$1$\\
+\end{tabular}
+
+On savait d'avance qu'on aurait $2^{10} \equiv 1 \pmod{11}$ (petit
+théorème de Fermat), c'est-à-dire que l'ordre (multiplicatif) de $2$
+dans $\mathbb{F}_{11}^\times$ diviserait $10$. Le fait qu'on ne soit
+pas tombé sur $1$ plus tôt que $10$ signifie que l'ordre
+(multiplicatif) de $2$ dans $\mathbb{F}_{11}^\times$ vaut
+exactement $10$. On peut donc qualifier $2$ de primitif modulo $11$.
+\end{corrige}
+
(2) Expliquer pourquoi $\bar\imath \mapsto 2^i$ définit un
isomorphisme de groupes de $\mathbb{Z}/10\mathbb{Z}$ (additif) sur
$\mathbb{F}_{11}^\times$ (multiplicatif).
+\begin{corrige}
+Le fait d'avoir $2^{10} = 1 \in \mathbb{F}_{11}^\times$ assure qu'on a
+un morphisme de groupes $\mathbb{Z}/10\mathbb{Z} \to
+\mathbb{F}_{11}^\times$ défini par $\bar\imath \mapsto 2^i$ (les
+puissances de $2$ sont périodiques de période $10$
+dans $\mathbb{F}_{11}^\times$). Le fait que l'ordre de $2$ soit
+exactement $10$ signifie que ce morphisme est un isomorphisme (tout
+élément de $\mathbb{F}_{11}^\times$ s'écrit de la forme $2^i$ pour un
+$i$ uniquement déterminé modulo $10$).
+
+On notera $\bar\psi \colon \mathbb{Z}/10\mathbb{Z} \to
+\mathbb{F}_{11}^\times$ cet isomorphisme.
+\end{corrige}
+
(3) Montrer qu'il n'existe aucun $x \in \mathbb{F}_{11}$ tel que $x^2
= 2$ (dans $\mathbb{F}_{11}$).
+\begin{corrige}
+Manifestement $0^2 \neq 2$, donc il s'agit de voir qu'il n'existe
+aucun $x \in \mathbb{F}_{11}^\times$ tel que $x^2 = 2$. Or si un tel
+$x$ existait, il pourrait s'écrire $x = \bar\psi(\bar\imath)$ pour un
+certain $\bar\imath \in \mathbb{Z}/10\mathbb{Z}$, et on aurait $
+\bar\psi(2\bar\imath) = x^2 = 2 = \bar\psi(\bar 1)$, donc $2\bar\imath
+= \bar 1$ dans $\mathbb{Z}/10\mathbb{Z}$ vu que $\bar\psi$ est un
+isomorphisme. Or il n'existe pas de $\bar\imath \in
+\mathbb{Z}/10\mathbb{Z}$ tel que $2\bar\imath = \bar 1$ car
+$2\bar\imath$ est pair (ceci a bien un sens vu que $2$ divise $10$)
+alors que $\bar 1$ est impair.
+\end{corrige}
+
(4) Montrer que le polynôme $t^2 - 2$ est irréductible dans
-$\mathbb{F}_{11}[t]$.
+$\mathbb{F}_{11}[t]$. (Il est recommandé d'utiliser la question (3).)
+
+\begin{corrige}
+Il s'agit d'un polynôme de degré $2$, donc s'il était réductible, il
+aurait une racine, et on vient de voir que ce n'est pas le cas.
+
+(On pouvait aussi appliquer le critère de Rabin : $t^2 - 2$ est
+irréductible dans $\mathbb{F}_{11}[t]$ si et seulement si il divise
+$t^{121} - t$ et est premier à $t^{11} - t$. C'est toutefois beaucoup
+plus fastidieux.)
+\end{corrige}
On note $K = \mathbb{F}_{11}[t] / (t^2 - 2)$ l'anneau quotient de
$\mathbb{F}_{11}[t]$ par le polynôme $t^2-2$.
@@ -97,6 +150,15 @@ $\mathbb{F}_{11}[t]$ par le polynôme $t^2-2$.
(5) Combien $K$ a-t-il d'éléments ? Que peut-on déduire de (4) sur
l'anneau $K$ ?
+\begin{corrige}
+L'anneau $K$ a $11^2 = 121$ éléments, qui s'écrivent de façon unique
+comme la classe d'un polynôme de degré $<2$, c'est-à-dire sous la
+forme $a + b\bar t$ (qu'on notera ci-après $a + b\sqrt{2}$) avec
+$a,b\in\mathbb{F}_{11}$. Le fait que $t^2 - 2 \in \mathbb{F}_{11}[t]$
+soit irréductible nous apprend que $K$ est un corps, c'est-à-dire
+\emph{le} corps à $121$ éléments.
+\end{corrige}
+
Dans ce qui suit, on notera\footnote{Comme on ne parlera jamais de
nombres réels, et notamment pas du nombre réel noté de la même
manière, ceci ne devrait pas causer de confusion.} « $\sqrt{2}$ »
@@ -107,35 +169,137 @@ Expliquer brièvement pourquoi tous les éléments de $K$ s'écrivent sous
la forme $a + b\sqrt{2}$ avec $a,b \in \mathbb{F}_{11}$ uniquement
déterminés.
+\begin{corrige}
+On a $(\sqrt{2})^2 = 2$ (puisque $t^2 \equiv 2 \pmod{t^2-2}$), ce qui
+rend la notation raisonnable. On a rappelé ci-dessus pourquoi tout
+élément de $K$ s'écrit sous la forme $a + b\sqrt{2}$) avec
+$a,b\in\mathbb{F}_{11}$ uniques.
+\end{corrige}
+
(7) Quel est l'ordre multiplicatif de $\sqrt{2}$ dans $K^\times$ ?
+\begin{corrige}
+Si $r \in \mathbb{Z}$ est pair, disons $r=2i$, alors $(\sqrt{2})^r =
+(\sqrt{2})^{2i} = 2^i \in K$, or on a caclulé en (1) les puissances de
+$2$ dans $\mathbb{F}_{11}$ (ce sont aussi, bien sûr, les puissances de
+$2$ dans $K$), en particulier ceci vaut $1$ si et seulement si $i$ est
+multiple de $10$ (donc $r$ multiple de $20$). Si $r$ est impair,
+disons $r = 2i+1$, alors $(\sqrt{2})^r = 2^i \sqrt{2}$ (et d'après
+l'unicité de l'écriture $a + b\sqrt{2}$, ceci ne peut jamais valoir
+$1$). On en déduit que le plus petit $r \geq 1$ pour lequel
+$(\sqrt{2})^r = 1$ est $20$ : c'est-à-dire que $\sqrt{2}$ est
+d'ordre $20$ dans $K^\times$.
+\end{corrige}
+
(8) On note $\Frob\colon K \to K$ l'application $x \mapsto x^{11}$.
Rappeler brièvement ce qu'on peut dire sur $\Frob$.
+\begin{corrige}
+On sait que $\Frob$ (le « Frobenius ») est un morphisme d'anneau (ou
+de corps) : c'est-à-dire qu'il vérifie $\Frob(x+y) = \Frob(x) +
+\Frob(y)$ et $\Frob(xy) = \Frob(x)\,\Frob(y)$ pour tous $x,y \in K$.
+\end{corrige}
+
(9) Que vaut $\Frob(a)$ si $a \in \mathbb{F}_{11}$ ? Que vaut
$\Frob(\sqrt{2})$ ? Que vaut $\Frob(a+b\sqrt{2})$ lorsque $a,b \in
\mathbb{F}_{11}$ ? (On demande évidemment une réponse meilleure que
$(a+b\sqrt{2})^{11}$...)
+\begin{corrige}
+Si $a \in \mathbb{F}_{11}$ alors $\Frob(a) = a^{11} = a$ d'après le
+petit théorème de Fermat. Quant à $\Frob(\sqrt{2}) = \sqrt{2}^{11} =
+2^5 \sqrt{2}$ (cf. réponse à la question (7)), c'est $10\sqrt{2}$
+(cf. réponse à la question (1)), ou, si on préfère, $-\sqrt{2}$.
+Enfin, puisque $\Frob$ est un morphisme, $\Frob(a+b\sqrt{2}) =
+\Frob(a) + \Frob(b)\,\Frob(\sqrt{2})$, ce qui montre
+$\Frob(a+b\sqrt{2}) = a - b\sqrt{2}$.
+\end{corrige}
+
(10) Rappeler brièvement pourquoi il existe un isomorphisme de groupes
de $\mathbb{Z}/120\mathbb{Z}$ (additif) sur $K^\times$
(multiplicatif). (On ne demande pas de l'expliciter.)
+\begin{corrige}
+Dans tout corps fini (et notamment dans $K$), il existe des éléments
+primitifs, c'est-à-dire des éléments $g$ d'ordre égal à l'ordre du
+groupe multiplicatif des éléments non nuls. Ici, il existe $g$
+d'ordre $\#K^\times = 120$, et alors $\bar\imath \mapsto g^i$ définit
+un isomorphisme $\bar\Psi \colon \mathbb{Z}/120\mathbb{Z} \to
+K^\times$ exactement comme en (2).
+\end{corrige}
+
(11) Calculer l'inverse de $13$ dans l'anneau
$\mathbb{Z}/120\mathbb{Z}$. (On le représentera par un entier entre
$0$ et $119$.)
+\begin{corrige}
+On cherche une relation de Bézout entre $13$ et $120$ : on a $120 =
+9\times 13 + 3$ et $13 = 4\times 3 + 1$ donc $1 = 13 - 4\times 3$ et
+$3 = 120 - 9\times 13$ donc $1 = 13 - 4\times(120-9\times 13) = 37
+\times 13 - 4\times 120$. Ceci montre que $37$ est l'inverse de $13$
+modulo $120$.
+\end{corrige}
+
(12) Déduire de (10) et (11) que pour tout $x \in K$ il existe un
unique $y \in K$ tel que $x = y^{13}$ (on pourra distinguer les deux
cas $x \in K^\times$ et $x=0$). Expliciter $y$ en fonction de $x$.
+\begin{corrige}
+Si $x = 0$, chercher $y \in K$ tel que $y^{13} = 0$ a pour seule
+solution $y=0$ puisque $K$ est un corps. Considérons maintenant le
+cas $x \in K^\times$ : comme $0^{13} = 0$, si $y^{13} = x$, on aura
+forcément $y \neq 0$, autrement dit $y \in K^\times$.
+
+Soit $\bar\Psi \colon \mathbb{Z}/120\mathbb{Z} \to K^\times$ un
+isomorphisme de groupes (qui existe d'après (10)). Il existe donc un
+unique $\bar\imath \in \mathbb{Z}/120\mathbb{Z}$ tel que
+$\bar\Psi(\bar\imath) = x$. Par ailleurs, si $y \in K^\times$, il
+existe un unique $\bar\jmath \in \mathbb{Z}/120\mathbb{Z}$ tel que
+$\bar\Psi(\bar\jmath) = y$. L'équation $x = y^{13}$ signife
+$\bar\Psi(\bar\imath) = x = y^{13} = \bar\Psi(13\bar\jmath)$, donc
+(puisque $\bar\Psi$ est un isomorphisme) $\bar\imath = 13\bar\jmath$
+dans $\mathbb{Z}/120\mathbb{Z}$. Mais on vient de voir que ceci
+signifie $\bar\jmath = 37\bar\imath$ (car $37$ est l'inverse de $13$
+dans $\mathbb{Z}/120\mathbb{Z}$) : autrement dit $y =
+\bar\Psi(\bar\jmath) = \bar\Psi(37\bar\imath) = x^{37}$.
+
+Comme on a aussi $0 = 0^{37}$, on voit que (quel que soit $x\in K$)
+l'unique solution de $y^{13} = x$ (en l'indéterminée $y$) est : $y =
+x^{37}$.
+\end{corrige}
+
(13) Calculer $(2+\sqrt{2})^r$ dans $K$ pour $r$ valant $2$ et et $4$,
puis pour $r$ valant $11$ (il est recommandé d'utiliser la
question (9)), $22$ et $33$, et enfin pour $r$ valant $37$.
+\begin{corrige}
+On a $(2+\sqrt{2})^2 = 4 + 4\sqrt{2} + 2 = 6 + 4\sqrt{2}$.
+
+On a $(2+\sqrt{2})^4 = (6 + 4\sqrt{2})^2 = 36 + 48\sqrt{2} + 32 = 2 +
+4\sqrt{2}$ (se rappeler que les coefficients sont
+dans $\mathbb{F}_{11}$).
+
+On a $(2+\sqrt{2})^{11} = 2-\sqrt{2} = 2+10\sqrt{2}$ d'après la question (9).
+
+On a $(2+\sqrt{2})^{22} = (6+4\sqrt{2})^{11} = 6 - 4\sqrt{2} = 6 +
+7\sqrt{2}$.
+
+On a $(2+\sqrt{2})^{33} = (2+10\sqrt{2}) \times (6+7\sqrt{2}) = 12 +
+74\sqrt{2} + 140 = 9 + 8\sqrt{2}$.
+
+Enfin, on a $(2+\sqrt{2})^{37} =(9+8\sqrt{2}) \times (2+4\sqrt{2}) =
+18 + 52\sqrt{2} + 64 = 5 + 8\sqrt{2}$.
+\end{corrige}
+
(14) En utilisant (12) et (13), résoudre l'équation $y^{13} =
2+\sqrt{2}$ dans $K$ (en l'indéterminée $y$).
+\begin{corrige}
+D'après ce qu'on a vu en (12), l'unique solution de $y^{13} =
+2+\sqrt{2}$ vaut $(2+\sqrt{2})^{37}$, et d'après (13), ceci vaut $5 +
+8\sqrt{2}$.
+\end{corrige}
+
%
%
%