From 15ddc480597f5b8e7ffffe793fc78fb9ac7fbec7 Mon Sep 17 00:00:00 2001
From: david <david>
Date: Tue, 17 Nov 2009 19:06:53 +0000
Subject: Correct exercise 4 part (A).

---
 controle-20091124.tex | 113 ++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 110 insertions(+), 3 deletions(-)

(limited to 'controle-20091124.tex')

diff --git a/controle-20091124.tex b/controle-20091124.tex
index cc52097..f29d01c 100644
--- a/controle-20091124.tex
+++ b/controle-20091124.tex
@@ -190,9 +190,11 @@ $10^i$&$1$&$3$&$2$&$-1$&$-3$&$-2$\\
 \noindent (On a représenté $6$, $4$ et $5$ modulo $7$ par $-1$, $-3$
 et $-2$ respectivement, de façon à rendre les calculs plus faciles.)
 Le fait (qu'on trouve ensuite) que $10^6 \equiv 1 \pmod{7}$ était
-prévu par le petit théorème de Fermat.  De façon plus générale,
-$10^{6k} \equiv 1 \pmod{7}$ donc $10^{6k+i} \equiv 10^i \pmod{7}$ :
-ainsi, dans la table ci-dessus, l'indice $i$ peut se lire modulo $6$.
+prévu par le petit théorème de Fermat (et le fait qu'on n'ait pas
+trouvé $1$ plus tôt signifie que $10 \equiv 3$ est primitif
+modulo $7$).  De façon plus générale, $10^{6k} \equiv 1 \pmod{7}$ donc
+$10^{6k+i} \equiv 10^i \pmod{7}$ : ainsi, dans la table ci-dessus,
+l'indice $i$ peut se lire modulo $6$.
 
 \leavevmode\hphantom{(C)} (2) D'après ce qu'on vient d'expliquer, un
 entier naturel $A = \sum_{i=0}^{+\infty} a_i 10^i$ (écrit en décimal)
@@ -420,17 +422,119 @@ irr
 $\mathbb{F}_9$ à $9$ éléments.  (3) Quels en sont les éléments
 primitifs ?
 
+\begin{corrige}
+(A) (1) On peut par exemple remarquer que le polynôme $f = t^2 + t - 1
+  \in \mathbb{F}_3[t]$ n'a pas de racine dans $\mathbb{F}_3$ (car
+  $f(0) = -1$, $f(1) = 1$ et $f(-1) = -1$), ce qui interdit qu'il
+  possède une factorisation non-triviale (car si $f = f_1 f_2$ avec
+  $f_1,f_2$ de degré $<2$, ils seront chacun de degré $1$, donc ils
+  auront nécessairement des racines).  On peut aussi préférer
+  appliquer le critère de Rabin : d'une part $f$ divise $t^9 - t$ car
+  $t^2 \equiv -t + 1 \pmod{f}$ donc $t^3 \equiv -t^2 + t \equiv -t - 1
+  \pmod{f}$, et ainsi $t^9 \equiv -t^3 - 1 \equiv t \pmod{f}$ (ce
+  n'est qu'une façon de mener le calcul, on pouvait aussi préférer
+  calculer la division euclidienne de $t^9 - t$ par $f$) ; d'autre
+  part, $f$ est premier avec $t^3 - t$ car $t^3 - t \equiv t - 1
+  \pmod{f}$ (reste de la division de $t^3 - t$ par $f$) et $f \equiv 1
+  \pmod{t-1}$ (reste de la division de $f$ par $t-1$), donc
+  l'algorithme d'Euclide a montré que $f$ et $t^3 - t$ sont premiers
+  entre eux : ainsi, le critère de Rabin assure que $f$ est
+  irréductible.
+
+\leavevmode\hphantom{(A)} (2) Puisque $f = t^2 + t - 1$ est
+irréductible, on sait que $\mathbb{F}_3[t]/(f)$ sera un corps a
+$3^{\deg f} = 9$ éléments.  En représentant les éléments de
+$\mathbb{F}_9$ par des polynômes de degré $<2$ en $t$ vus comme des
+classes de congruence modulo $f$ (de sorte que les $9$ éléments sont :
+$0$, $1$, $-1$, $\bar t$, $\bar t+1$, $\bar t-1$, $-\bar t$, $-\bar
+t+1$, $-\bar t-1$), on obtient les tables d'opérations suivantes :
+
+\begin{center}
+\tiny
+\begin{tabular}{c|ccccccccc}
+$+$&$0$&$1$&$-1$&$\bar t$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$\\\hline
+$0$&$0$&$1$&$-1$&$\bar t$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$\\
+$1$&$1$&$-1$&$0$&$\bar t+1$&$\bar t-1$&$\bar t$&$-\bar t+1$&$-\bar t-1$&$-\bar t$\\
+$-1$&$-1$&$0$&$1$&$\bar t-1$&$\bar t$&$\bar t+1$&$-\bar t-1$&$-\bar t$&$-\bar t+1$\\
+$\bar t+0$&$\bar t+0$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$&$0$&$1$&$-1$\\
+$\bar t+1$&$\bar t+1$&$\bar t-1$&$\bar t+0$&$-\bar t+1$&$-\bar t-1$&$-\bar t$&$1$&$-1$&$0$\\
+$\bar t-1$&$\bar t-1$&$\bar t+0$&$\bar t+1$&$-\bar t-1$&$-\bar t$&$-\bar t+1$&$-1$&$0$&$1$\\
+$-\bar t+0$&$-\bar t$&$-\bar t+1$&$-\bar t-1$&$0$&$1$&$-1$&$\bar t+0$&$\bar t+1$&$\bar t-1$\\
+$-\bar t+1$&$-\bar t+1$&$-\bar t-1$&$-\bar t$&$1$&$-1$&$0$&$\bar t+1$&$\bar t-1$&$\bar t+0$\\
+$-\bar t-1$&$-\bar t-1$&$-\bar t$&$-\bar t+1$&$-1$&$0$&$1$&$\bar t-1$&$\bar t+0$&$\bar t+1$\\
+\end{tabular}
+\end{center}
+
+\begin{center}
+\tiny
+\begin{tabular}{c|ccccccccc}
+$\times$&$0$&$1$&$-1$&$\bar t$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$\\\hline
+$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\
+$1$&$0$&$1$&$-1$&$\bar t$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$\\
+$-1$&$0$&$-1$&$1$&$-\bar t$&$-\bar t-1$&$-\bar t+1$&$\bar t$&$\bar t-1$&$\bar t+1$\\
+$\bar t$&$0$&$\bar t$&$-\bar t$&$-\bar t+1$&$1$&$\bar t+1$&$\bar t-1$&$-\bar t-1$&$-1$\\
+$\bar t+1$&$0$&$\bar t+1$&$-\bar t-1$&$1$&$\bar t-1$&$-\bar t$&$-1$&$\bar t$&$-\bar t+1$\\
+$\bar t-1$&$0$&$\bar t-1$&$-\bar t+1$&$\bar t+1$&$-\bar t$&$-1$&$-\bar t-1$&$1$&$\bar t$\\
+$-\bar t$&$0$&$-\bar t$&$\bar t$&$\bar t-1$&$-1$&$-\bar t-1$&$-\bar t+1$&$\bar t+1$&$1$\\
+$-\bar t+1$&$0$&$-\bar t+1$&$\bar t-1$&$-\bar t-1$&$\bar t$&$1$&$\bar t+1$&$-1$&$-\bar t$\\
+$-\bar t-1$&$0$&$-\bar t-1$&$\bar t+1$&$-1$&$-\bar t+1$&$\bar t$&$1$&$-\bar t$&$\bar t-1$\\
+\end{tabular}
+\end{center}
+
+\leavevmode\hphantom{(A)} (3) Les ordres multiplicatifs possibles d'un
+élément non nul dans $\mathbb{F}_9$ sont les diviseurs de $8$ (car $8$
+est l'ordre du groupe multiplicatif $\mathbb{F}_9^\times$),
+c'est-à-dire $1$, $2$, $4$ ou $8$.  On peut calculer les puissances
+successives de $\bar t$ grâce à la table de multiplication : ce sont
+
+\begin{center}
+\begin{tabular}{c|c|c|c|c|c|c|c|c}
+$i$&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$\\\hline
+$\bar t^i$&$1$&$\bar t$&$-\bar t+1$&$-\bar t-1$&$-1$&$-\bar t$&$-\bar t-1$&$\bar t+1$\\
+\end{tabular}
+\end{center}
+
+\noindent Le fait (qu'on trouve ensuite) que $\bar t^8 = 1$ était
+prévu par le petit théorème de Fermat généralisé.  Comme on a trouvé
+$8$ puissances de $\bar t$ distinctes (c'est-à-dire qu'on n'est pas
+retombé sur $1$ avant ce que le petit théorème de Fermat imposé),
+l'élément $\bar t$ est primitif.  La table ci-dessus est alors la
+donnée d'un isomorphisme $i \mapsto \bar t^i$ entre le groupe additif
+$\mathbb{Z}/8\mathbb{Z}$ et le groupe multiplicatif
+$\mathbb{F}_9^\times$ (tous deux étant cycliques d'ordre $8$).  Les
+générateurs de $\mathbb{F}_9^\times$ sont alors les $\varphi(8) = 4$
+éléments écrits qui correspondent à un générateur de
+$\mathbb{Z}/8\mathbb{Z}$ par cet isomorphisme : comme les générateurs
+du groupe additif $\mathbb{Z}/8\mathbb{Z}$ sont $1,3,5,7$ (ce sont les
+éléments nombres premiers avec $8$ modulo $8$, c'est-à-dire les
+nombres impairs), les générateurs de $\mathbb{F}_9^\times$, autrement
+dit les éléments primitifs de $\mathbb{F}_9$, sont $\bar t$, $-\bar
+t-1$, $-\bar t$ et $\bar t+1$.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
 (B) (1) Donner une racine, puis la décomposition en facteurs
 irréductibles, de $t^2 + t \in \mathbb{F}_3[t]$.  (2) Que peut-on
 dire de $\mathbb{F}_3[t]/(t^2 + t)$ ?  (Plusieurs réponses
 possibles.)
 
+\begin{corrige}
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
 (C) (1) Montrer que le polynôme $t^5 + t^2 + 1 \in \mathbb{F}_2[t]$
 est irréductible.  (2) Quels sont \textit{a priori} les ordres
 multiplicatifs possibles de l'élément $\bar t$ (représenté par le
 polynôme $t$) dans $\mathbb{F}_2[t]/(t^5 + t^2 + 1)$ ?  (3) L'élément
 $\bar t$ est-il primitif dans $\mathbb{F}_2[t]/(t^5 + t^2 + 1)$ ?
 
+\begin{corrige}
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
 (D) (1) Justifier brièvement l'égalité suivante dans
 $\mathbb{F}_2[t]$ : on a $t^{19}+1 = {(t+1)} \penalty0\,
 {(t^{18}+t^{17}+t^{16} + \cdots + t^3+t^2+t+1)}$.  On appellera
@@ -450,6 +554,9 @@ polyn
 sur $\mathbb{F}_2[t]/(\Phi_{19})$ ?  (On pourra par exemple chercher
 une racine, puis une façon d'en produire de nouvelles.)
 
+\begin{corrige}
+\end{corrige}
+
 %
 %
 %
-- 
cgit v1.2.3

