summaryrefslogtreecommitdiffstats
path: root/controle-20091124.tex
diff options
context:
space:
mode:
authordavid <david>2009-11-17 19:06:53 +0000
committerdavid <david>2009-11-17 19:06:53 +0000
commit15ddc480597f5b8e7ffffe793fc78fb9ac7fbec7 (patch)
treed25100dc7a3d4585f54e63848787532f4b72c200 /controle-20091124.tex
parent1beac514711d848407c3e56ff43734a5d324ac1a (diff)
downloadinfmdi720-15ddc480597f5b8e7ffffe793fc78fb9ac7fbec7.zip
infmdi720-15ddc480597f5b8e7ffffe793fc78fb9ac7fbec7.tar.gz
infmdi720-15ddc480597f5b8e7ffffe793fc78fb9ac7fbec7.tar.bz2
Correct exercise 4 part (A).
Diffstat (limited to 'controle-20091124.tex')
-rw-r--r--controle-20091124.tex113
1 files changed, 110 insertions, 3 deletions
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éductible. (2) En déduire des tables d'opération du corps
$\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ôme (en la nouvelle indéterminée $X$)
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}
+
%
%
%