From 15ddc480597f5b8e7ffffe793fc78fb9ac7fbec7 Mon Sep 17 00:00:00 2001 From: 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