%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} \usepackage[latin1]{inputenc} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \usepackage{url} % \theoremstyle{definition} \newtheorem{comcnt}{Tout} \newcommand\exercice{% \refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} \newcommand{\limp}{\mathrel{\Rightarrow}} \newcommand{\liff}{\mathrel{\Longleftrightarrow}} \newcommand{\pgcd}{\operatorname{pgcd}} \newcommand{\ppcm}{\operatorname{ppcm}} \newcommand{\signe}{\operatorname{signe}} \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Fr}} % \newif\ifcorrige \corrigetrue \newenvironment{corrige}% {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\relax\else\egroup\fi\par} % % % \begin{document} \ifcorrige \title{INFMDI720\\Contrôle de connaissance --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}} \else \title{INFMDI720\\Contrôle de connaissance\\{\normalsize Rappels mathématiques pour la cryptographie}} \fi \author{} \date{24 novembre 2009} \maketitle \pretolerance=10000 \tolerance=8000 \vskip1truein\relax \textbf{Consignes :} Les exercices sont complètement indépendants. Ils pourront être traités dans un ordre quelconque, mais on demande de faire apparaître de façon très visible dans les copies où commence chaque exercice. À l'intérieur d'un exercice donné (sauf l'exercice 3), les parties A,B,C..., sont encore essentiellement indépendantes, mais comme elles peuvent se ressembler et s'éclairer les unes les autres il est recommandé de les traiter dans l'ordre. Les questions 1,2,3... dépendent les unes des autres. Le sujet étant volontairement trop long pour le temps imparti, il ne sera pas nécessaire de traiter tous les exercices pour avoir le maximum des points. Il est suggéré de prendre le temps de tous les lire, pour bien choisir ceux que l'on traitera. Il n'est pas nécessaire de faire des réponses longues. L'usage de tous les documents (notes de cours manuscrites ou imprimées, livres) est autorisé. L'usage des calculatrices électroniques est interdit. (Certains exercices peuvent apparaître calculatoires, mais les calculs sont toujours faisables à la main en un temps raisonnable, parfois au prix de quelques astuces.) Durée : 1h30 \newpage % % % \exercice (A) (1) À quoi est congru $10^n$ modulo $9$ (en fonction éventuellement de l'entier naturel $n$) ? (2) En déduire une démonstration de l'affirmation suivante : un entier naturel écrit en décimal (=base $10$) est congru modulo $9$ à la somme de ses chiffres. Comment faire pour calculer très simplement le reste de la division euclidienne par $9$ d'un entier naturel écrit en décimal ? (3) Montrer que la multiplication suivante est erronée : $745\,330\,964 \times 390\,158\,565 = 290\,797\,259\,507\,306\,660$. \begin{corrige} (A) (1) On a $10 \equiv 1 \pmod{9}$ donc $10^n \equiv 1^n \equiv 1\pmod{9}$. (2) Si $A = \sum_{i=0}^{+\infty} a_i\, 10^i$ (avec $a_i \in \{0,1,2,\ldots,9\}$) est l'écriture en base $10$ d'un entier naturel $A$, alors $A \equiv \sum_{i=0}^{+\infty} a_i \pmod{9}$ puisque $10^i \equiv 1$ comme on vient de le voir : on a bien montré que $A$ est congru modulo $9$ à la somme $\sum_{i=0}^{+\infty} a_i$ de ses chiffres décimaux. Pour calculer le reste de la division euclidienne par $9$ d'un entier naturel $A$, il suffit donc de calculer celui de la somme de ses chiffres décimaux (ce qui peut se faire en itérant l'opération « somme des chiffres décimaux » jusqu'à obtenir un résultat à un chiffre, et remplacer $9$ par $0$ à la fin si nécessaire). Remarquons qu'on peut simplifier certaines choses : par exemple, ignorer les $9$ dans l'écriture décimale, et remplacer les $8$ par des $-1$, et évidemment remplacer un nombre par la somme de ses chiffres décimaux à n'importe quelle étape du calcul. \leavevmode\hphantom{(A)} (3) En appliquant ce procédé, on voit que $745\,330\,964 \equiv\penalty-100 7+4+5+\penalty0 3+3+\penalty0 6+4 =\penalty0 32 \equiv 5 \pmod{9}$, que $390\,158\,565 \equiv\penalty-100 3+\penalty0 1+5+8+\penalty0 5+6+5 =\penalty0 33 \equiv 6 \pmod{9}$ et que $290\,797\,259\,507\,306\,660 \equiv\penalty-100 2+\penalty0 7+7+\penalty0 2+5+\penalty0 5+7+\penalty0 3+6+\penalty0 6+6 = 56 \equiv 2 \pmod{9}$. Comme $5\times 6 \equiv 3 \not\equiv 2 \pmod{9}$, cette « preuve par $9$ » montre que la multiplication proposée est erronée. \end{corrige} \ifcorrige\medbreak\else\relax\fi (B) (1) À quoi est congru $10^n$ modulo $11$ (en fonction éventuellement de l'entier naturel $n$) ? (Remarque : le nombre $10$ peut s'écrire d'une manière très simple modulo $11$...) (2) Comment faire pour calculer très simplement le reste de la division euclidienne par $11$ d'un entier naturel écrit en décimal ? (3) Montrer que la multiplication suivante est encore erronée : $745\,330\,964 \times 390\,158\,565 = 290\,797\,259\,517\,306\,660$. \begin{corrige} (B) (1) On a $10 \equiv -1 \pmod{11}$ donc $10^n \equiv (-1)^n \equiv 1\pmod{11}$, c'est-à-dire concrètement que $10^n$ vaut $+1$ ou $-1$ modulo $11$ selon que $n$ est respectivement pair ou impair. (2) Si $A = \sum_{i=0}^{+\infty} a_i\, 10^i$ (avec $a_i \in \{0,1,2,\ldots,9\}$) est l'écriture en base $10$ d'un entier naturel $A$, alors $A \equiv \sum_{i=0}^{+\infty} (-1)^i a_i \pmod{11}$ puisque $10^i \equiv (-1)^i$ comme on vient de le voir : on a bien montré que $A$ est congru modulo $11$ à la somme \emph{alternée} $\sum_{i=0}^{+\infty} (-1)^i a_i$ de ses chiffres décimaux, c'est-à-dire en comptant avec un $+$ tous les chiffres de puissance paire (unités, centaines, dizaines de milliers...) et avec un $-$ tous les chiffres de puissance impaire (dizaines, milliers, etc.). Pour calculer le reste de la division euclidienne par $11$ d'un entier naturel $A$, il suffit donc de calculer celui de la somme alternée de ses chiffres décimaux (ce qui peut se faire en itérant l'opération « somme alternée des chiffres décimaux », en n'oubliant pas les signes, jusqu'à obtenir un résultat entre $-9$ et $9$, et ajouter $11$ à la fin si nécessaire pour obtenir un reste entre $0$ et $10$ inclus). \leavevmode\hphantom{(B)} (3) En appliquant ce procédé, on voit que $745\,330\,964 \equiv\penalty-100 7-4+5-\penalty0 3+3+\penalty0 9-6+4 =\penalty0 15 \equiv 4 \pmod{11}$, que $390\,158\,565 \equiv\penalty-100 3-9-\penalty0 1+5-8+\penalty0 5-6+5 =\penalty0 -6 \equiv 5 \pmod{11}$ et que $290\,797\,259\,517\,306\,660 \equiv\penalty-100 -2+9+\penalty0 7-9+7-\penalty0 2+5-9+\penalty0 5-1+7-\penalty0 3-6+\penalty0 6-6 =\penalty0 8 \pmod{11}$. Comme $4\times 5 \equiv\penalty0 9 \not\equiv 8 \pmod{11}$, cette « preuve par $11$ » montre que la multiplication proposée est erronée. \end{corrige} \ifcorrige\medbreak\else\relax\fi (C) (1) À quoi est congru $10^n$ modulo $7$, selon la valeur de $n$ ? (2) Proposer une méthode (moins simple que celles données en A et B, mais néanmoins plus économique que de poser la division) permettant de calculer le reste de la division euclidienne par $7$ d'un entier naturel écrit en décimal. (On cherchera à se limiter à des additions et des multiplications par $\pm 1, \pm 2, \pm 3$.) (3) Montrer que le calcul suivant est erroné : $3^{31} = 617\,673\,693\,283\,947$. \begin{corrige} (C) (1) Remarquons tout d'abord que $10 \equiv 3 \pmod{7}$. On peut dresser de proche en proche la table suivante des puissances de $10$ modulo $7$ : \begin{center} \begin{tabular}{c|c|c|c|c|c|c} $i$&$0$&$1$&$2$&$3$&$4$&$5$\\\hline $10^i$&$1$&$3$&$2$&$-1$&$-3$&$-2$\\ \end{tabular} \end{center} \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 (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) est congru modulo $7$ à la somme de ses chiffres décimaux $a_i$ chacun multiplié par une valeur dans $\{\pm 1, \pm 2, \pm 3\}$ donnée (en fonction de $i$ modulo $6$) par la table ci-dessus : c'est-à-dire $a_0 +\penalty100 3 \times a_1 +\penalty0 2 \times a_2 -\penalty0 a_3 -\penalty0 3\times a_4 -\penalty0 2 \times a_5 +\penalty0 a_6 +\penalty0 3 \times a_7 + \cdots$. Pour simplifier les calculs ultérieurs, il peut être astucieux de précalculer les multiplications par tous les chiffres décimaux possibles, c'est-à-dire de dresser le tableau des valeurs de $a_i \times 10^i$ modulo $7$ en fonction de $a_i$ et de $i$ : \begin{center} \footnotesize \begin{tabular}{r|c|c|c|c|c|c} $a_i\downarrow$\textbackslash $i\rightarrow$&$0$&$1$&$2$&$3$&$4$&$5$\\\hline $0$\rlap{, $7$}\hphantom{\textbackslash $i\rightarrow$}&$0$&$0$&$0$&$0$&$0$&$0$\\ $1$\rlap{, $8$}\hphantom{\textbackslash $i\rightarrow$}&$1$&$3$&$2$&$6$&$4$&$5$\\ $2$\rlap{, $9$}\hphantom{\textbackslash $i\rightarrow$}&$2$&$6$&$4$&$5$&$1$&$3$\\ $3$\hphantom{\textbackslash $i\rightarrow$}&$3$&$2$&$6$&$4$&$5$&$1$\\ $4$\hphantom{\textbackslash $i\rightarrow$}&$4$&$5$&$1$&$3$&$2$&$6$\\ $5$\hphantom{\textbackslash $i\rightarrow$}&$5$&$1$&$3$&$2$&$6$&$4$\\ $6$\hphantom{\textbackslash $i\rightarrow$}&$6$&$4$&$5$&$1$&$3$&$2$\\ \end{tabular} \end{center} \noindent Avec ce tableau, pour calculer la classe modulo $7$ de $A = \sum_{i=0}^{+\infty} a_i\, 10^i$, il suffit de sommer modulo $7$ les valeurs des cases de chaque chiffre (la ligne étant déterminée par la valeur $a_i$ du chiffre décimal en question, et la colonne par l'exposant $i$ modulo $6$ de la puissance de $10$ utilisée). Il s'agit simplement d'une façon de regrouper une fois pour toutes le calcul des multiplications par $\pm 1, \pm 2, \pm 3$, le calcul étant toujours le même. Pour être encore plus efficace, on peut d'ailleurs remplir le tableau de façon « paresseuse », c'est-à-dire en ne calculant le contenu des cases que lorsqu'on en a besoin. \leavevmode\hphantom{(C)} (3) En appliquant ce procédé, on voit qu'on a $617\,673\,693\,283\,947 \equiv\penalty-100 2\times 6 +\penalty1000 3\times 1 +\penalty1000 7 -\penalty0 2\times 6 -\penalty1000 3\times 7 -\penalty1000 3 +\penalty0 2\times 6 +\penalty1000 3\times 9 +\penalty1000 3 -\penalty0 2\times 2 -\penalty1000 3\times 8 -\penalty1000 3 +\penalty0 2\times 9 +\penalty1000 3\times 4 +\penalty1000 7 =\penalty-100 34 \equiv 6 \pmod{7}$ ou, en utilisant directement le tableau ci-dessus, $\equiv 5 + 3 + 0 +\penalty0 2 + 0 + 4 +\penalty0 5 + 6 + 3 +\penalty0 3 + 4 + 4 +\penalty0 4 + 5 + 0 =\penalty-100 48 \equiv 6 \pmod{7}$. Mais d'autre part $3^{31}$ est, modulo $7$, congru à ($10^{31}$ donc à) $3$ puisque $31 \equiv 1 \pmod 6$ (ou si on veut, $3^{31} \equiv 3^{5\times 6 + 1} \equiv 3 \pmod{7}$ puisque $3^6 \equiv 1 \pmod{7}$). Comme $6 \not\equiv 3$, le nombre proposé n'est pas la valeur correcte de $3^{31}$. \end{corrige} % % % \exercice (A) Quel entier entre $0$ et $100$ est congru à $19$ modulo $13$ et à $13$ modulo $19$ ? \begin{corrige} (A) Commençons par trouver un entier qui convient. On pourrait se rendre compte que $19+13 = 32$ convient pour des raisons de symétrie. Pour procéder de façon plus systématique, cherchons une relation de Bézout entre $19$ et $13$, qui sont visiblement premiers entre eux (et ceci va de toute façon le confirmer) : on a $19 = 1\times 13 + 6$ puis $13 = 2\times 6 + 1$ donc le pgcd est bien $1$, et on a $1 = 13 - 2\times 6 = 3\times 13 - 2\times 19$. Ainsi, d'après un résultat du cours (version « effective » du théorème chinois), un nombre congru à $19$ (soit $6$) modulo $13$ et à $13$ modulo $19$ est donné par $3 \times 13 \times 13 - 2 \times 19 \times 6$ : ceci vaut $279$, mais pour simplifier les calculs on pouvait calculer $3\times 13 \equiv 1 \pmod{19}$ et $-2 \times 6 \equiv 1 \pmod{13}$, donc il reste $13 + 19 = 32$. En tout état de cause, comme $13$ et $19$ sont premiers entre eux, les nombres congrus à $x$ modulo $13$ et à $y$ modulo $19$, quels que soient $x$ et $y$ entiers, forment une unique classe de congruence modulo $13 \times 19 = 247$ (qu'il n'était pas vraiment nécessaire de calculer, seul importe que ce soit $>100$, ce qui est évident), donc dès qu'on a trouvé un nombre vérifiant les congruences demandées (en l'occurrence $32$), on sait que les autres sont les nombres qui lui sont congrus modulo $13 \times 19$, et en particulier il n'y en a pas d'autre entre $0$ et $100$. \end{corrige} \ifcorrige\medbreak\else\relax\fi (B) Quel entier à trois chiffres en base $10$ se termine par $23$ et est multiple de $19$ ? \begin{corrige} (B) Se terminer par $23$ en base $10$ signifie être congru à $23$ modulo $100$. Cherchons une relation de Bézout entre $100$ et $19$ qui sont premiers entre eux : on a $100 = 5\times 19 + 5$ et $19 = 3\times 5 + 4$ et $5 = 1\times 4 + 1$ donc $1 = 5 - 4 = 4 \times 5 - 19 = 4 \times 100 - 21 \times 19$. Ainsi, d'après un résultat du cours (version « effective » du théorème chinois), un nombre congru à $23$ modulo $100$ et à $0$ modulo $19$ (i.e., divisible par $19$) est donné par $- 21 \times 19 \times 23$ : ceci vaut $-9177$, mais pour simplifier les calculs on pouvait calculer $-21\times 23 \equiv -83 \equiv 17 \pmod{100}$ et ainsi $- 21 \times 19 \times 23 \equiv 17 \times 19 = 323 \pmod{1900}$. Le nombre $323$ répond aux conditions demandées, et comme tout les entiers congrus à $23$ modulo $100$ et à $0$ modulo $19$ forment une unique classe de congruence modulo $1900$, on a trouvé le seul nombre à trois chiffres. \end{corrige} \ifcorrige\medbreak\else\relax\fi (C) Quel entier entre $0$ et $100$ est congru respectivement à $1,2,3,4$ modulo $2,3,5,7$ ? (C'est-à-dire : congru à $1$ modulo $2$, et à $2$ modulo $3$, et à $3$ modulo $5$, et à $4$ modulo $7$.) \begin{corrige} (C) Les nombres $2,3,5,7$ sont premiers entre eux deux à deux. Commençons par trouver des solutions à deux congruences simultanées : comme les nombres sont assez petits, il est plus simple de le faire par tâtonnement : par exemple, $5$ est congru à $1$ modulo $2$ et à $2$ modulo $3$, cela se trouve immédiatement en parcourant les entiers de $0$ à $5$ ou plus astucieusement ceux qui vérifient une des deux congruences pour chercher ceux qui vérifient l'autre. Comme on va vouloir mettre ensuite ensemble deux congruences de ce genre, il vaut mieux les trouver de même taille et, si possible, vérifiant une relation de Bézout simple : le plus économique est donc de mettre $2$ avec $7$ et $3$ avec $5$, ce qui a le bon goût que $1\times 15 - 1\times 14 = 1$ est une relation de Bézout évidente entre $3\times 5$ et $2\times 7$. Par tâtonnement, on trouve que $11$ (et exactement les nombres de sa classe modulo $14$) est congru à $1$ modulo $2$ et à $4$ modulo $7$, et que $8$ (et exactement les nombres de sa classe modulo $15$) est congru à $2$ modulo $3$ et à $3$ modulo $5$. Avec la relation de Bézout $1\times 15 - 1\times 14 = 1$, toujours en appliquant la même version « effective » du théorème chinois, on voit que les entiers vérifiant les quatre congruences demandées sont exactement la classe de $1\times 15\times 11 - 1\times 14\times 8 = 53$ modulo $15 \times 14 = 210$, donc le seul entre $0$ et $100$ est $53$. \end{corrige} \ifcorrige\medbreak\else\relax\fi (D) Déterminer tous les entiers entre $0$ et $2009$ congrus à $1$ modulo chacun des nombres $7$, $11$ et $13$. (C'est-à-dire : congrus à $1$ modulo $7$, et à $1$ modulo $11$, et à $1$ modulo $13$.) (Indication : y-t-il un nombre évident qui répond à cette condition ?) \begin{corrige} (D) Comme le suggère l'indication, il y a un nombre évident congru à $1$ modulo $7$ et $11$ et $13$ à la fois, c'est $1$ lui-même. Le théorème chinois assure que, comme $7$ et $11$ et $13$ sont premiers entre eux deux à deux, les entiers congrus à $1$ modulo chacun d'eux forment une classe de congruence modulo $7 \times 11 \times 13 = 1001$. Les nombres entre $0$ et $2009$ vérifiant les congruences demandées sont donc : $1$, $1002$ et $2003$. \end{corrige} \ifcorrige\medbreak\else\relax\fi (E) Déterminer tous les entiers entre $0$ et $100\,000$ congrus à $192$ modulo $300$ et à $169$ modulo $305$. \begin{corrige} (E) Un entier congru à $192$ modulo $300$ est (comme $5|300$) congru à $192 \equiv 2$ modulo $5$, et un entier congru à $169$ modulo $305$ est (comme $5|305$) congru à $169 \equiv 4$ modulo $5$. Comme $2 \not\equiv 4 \pmod{5}$, il n'existe \emph{aucun} entier vérifiant les deux congruences demandées. \end{corrige} % % % \exercice \textit{(Les nombres $101$ et $401$ sont premiers.)} (1) Que vaut $\varphi(40\,501)$ ? (2) Quel est l'inverse de $3$ dans $\mathbb{Z}/40\,000\mathbb{Z}$ ? On note $s$ un entier naturel qui le représente. (Il n'est pas nécessaire d'avoir trouvé la valeur numérique de $s$ pour pouvoir répondre aux questions suivantes.) (3) Montrer l'affirmation suivante : si $n$ est premier avec $40\,501$, alors $(n^3)^s \equiv n \pmod{40\,501}$. (4) Que vaut $8^s$ modulo $40\,501$ ? \begin{corrige} (1) On a $40\,501 = 101\times 401$ donc $\varphi(40\,501) = 100\times 400 = 40\,000$. (2) Cherchons une relation de Bézout entre $3$ et $40\,000$ : on a $40\,000 = 13\,333 \times 3 + 1$ donc $1 = 40\,000 - 13\,333\times 3$. Ceci montre que $3$ est inversible d'inverse $-13\,333 \equiv 26\,667 \pmod{40\,000}$ dans $\mathbb{Z}/40\,000\mathbb{Z}$. Disons donc $s = 26\,667$. (3) Si $n$ est premier avec $40\,501$, on sait que $n^{\varphi(40\,501)} \equiv 1 \pmod{40\,501}$ (théorème d'Euler), c'est-à-dire $n^{40\,000} \equiv 1 \pmod{40\,501}$, et bien sûr $n^{40\,000\,k} \equiv 1 \pmod{40\,501}$ pour tout naturel $k$. Or $3s \equiv 1 \pmod{40\,000}$, c'est-à-dire $3s = 40\,000\,k + 1$ pour un certain $k$ (en l'occurrence $k=2$ avec notre choix $s = 26\,667$, mais peu importe). On a donc $(n^3)^s = n^{3s} = n^{40\,000\,k + 1} = n^{40\,000\,k}\cdot n^1 \equiv n \pmod{40\,501}$. (4) En prenant $n=2$ dans la question précédente, on a montré $8^s \equiv 2 \pmod{40\,501}$. \end{corrige} % % % \exercice (A) (1) Montrer que le polynôme $t^2 + t - 1 \in \mathbb{F}_3[t]$ est 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 \penalty0 \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 (a) $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, (b) $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 impose), 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 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 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} (B) (1) Le polynôme $f = t^2 + t \in \mathbb{F}_3[t]$ s'annule en $0$ et en $-1$ : ce sont les deux racines de $f$, et on a donc $f = t(t+1)$, qui est la décomposition en facteurs irréductibles de ce polynôme. \leavevmode\hphantom{(B)} (2) On peut dire que puisque $f = t^2 + t$ n'est pas irréductible, l'anneau $\mathbb{F}_3[t]/(f)$ n'est pas un corps : et d'ailleurs ni $\bar t$ ni $\bar t + 1$ n'est inversible dans cet anneau puisque leur produit est $\bar t^2 + \bar t = 0$ (ce n'est pas un anneau intègre). On peut aussi être plus précis : puisque $f = t(t+1)$, le théorème chinois assure que $\mathbb{F}_3[t]/(f) \cong \mathbb{F}_3[t]/(t) \times \mathbb{F}_3[t]/(t+1)$ (où $\cong$ signifie « isomorphe »), c'est-à-dire en fait $\mathbb{F}_3[t]/(f) \cong \mathbb{F}_3 \times \mathbb{F}_3$ avec un isomorphisme $\mathbb{F}_3[t]/(f) \to \mathbb{F}_3 \times \mathbb{F}_3$ qui envoie la classe dans $\mathbb{F}_3[t]/(f)$ d'un polynôme $u \in \mathbb{F}_3[t]$ sur le couple $(u(0), u(-1))$ formé des valeurs en $0$ et $-1$ de $u$ ; le fait qu'on ait $\bar t \cdot (\bar t + 1) = 0$ se traduit, \textit{via} cet isomorphism, en $(0,-1)\cdot (1,0) = (0,0)$. \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} (C) (1) Le plus simple est d'appliquer le critère de Rabin : pour montrer que $f = t^5 + t^2 + 1 \in \mathbb{F}_2[t]$ est irréductible, il s'agit de vérifier que (a) $f$ divise $t^{32} - t$, et (b) $f$ est premier avec $t^2 - t$. Pour ce qui est de (a), on a $t^5 \equiv t^2 + 1 \pmod{f}$ et on peut utiliser cette relation pour calculer les puissances suivantes de $t$ modulo $f$ : $t^6 \equiv t^3 + t \pmod{f}$ (en multipliant par $t$) et $t^8 \equiv t^5 + t^3 \equiv t^3 + t^2 + 1 \pmod{f}$ (en multipliant encore), donc (en élevant au carré, c'est-à-dire en appliquant le morphisme de Forbenius), $t^{16} \equiv t^6 + t^4 + 1 \equiv t^4 + t^3 + t + 1 \pmod{f}$ (car on a vu $t^6 \equiv t^3 + t$), et en élevant de nouveau au carré, $t^{32} \equiv t^8 + t^6 + t^2 + 1 \equiv (t^3 + t^2 + 1) + (t^3 + t) + t^2 + 1 = t \pmod{f}$, ce qui prouve bien que $f$ divise $t^{32} - t$. On pouvait aussi, bien entendu, poser la division euclidienne (mais elle est un peu fastidieuse\footnote{On trouve $t^{32} + t = (t^{27} + t^{24} + t^{22} + t^{21} + t^{18} + t^{17} + t^{16} + t^{15} + t^{14} + t^{10} + t^9 + t^7 + t^6 + t^5 + t^3 + t)(t^2+t)$.}). Pour ce qui est de (b), la division euclidienne de $f$ par $t^2 + t$ est $f = (t^3 + t^2 + t)(t^2 + t) + 1$, et comme le reste est $1$, c'est le pgcd souhaité et $f$ et $t^2 - t$ sont premiers entre eux. \leavevmode\hphantom{(C)} (2) Puisque $f = t^5 + t^2 + 1$ est irréductible, le quotient $\mathbb{F}_2[t]/(f)$ est un corps, ayant $2^{\deg f} = 32$ éléments, qu'on peut aussi noter $\mathbb{F}_{32}$. Le groupe multiplicatif $\mathbb{F}_{32}^\times$ de ses éléments non nuls a $31$ éléments. Comme $31$ est premier, ses seuls diviseurs sont $1$ et $31$, donc les seuls ordres multiplicatifs possibles d'un élément non nul de $\mathbb{F}_{32}$ sont $1$ et $31$. \leavevmode\hphantom{(C)} (3) On vient de voir que l'ordre multiplicatif de $\bar t$ ne peut être que $1$ ou $31$. Manifestement ce n'est pas $1$ car $\bar t \neq 1$ : il s'ensuit que c'est $31$, et $\bar t$ (comme \emph{tout} élément de $\mathbb{F}_{32}$ autre que $0$ et $1$) est primitif. (On pouvait aussi se fatiguer à énumérer les $31$ puissances $\bar t^i$ pour $i$ allant de $0$ à $30$, et vérifier qu'elles sont bien toutes distinctes.) \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 $\Phi_{19}$ le second facteur ($t^{18}+\cdots+t+1$). On \emph{admet} que $\Phi_{19}$ est irréductible dans $\mathbb{F}_2[t]$. \leavevmode\hphantom{(D)} (2) Quel est l'ordre multiplicatif de l'élément $\bar t$ (représenté par $t$) dans $\mathbb{F}_2[t]/(t^{19}+1)$ ? Dans $\mathbb{F}_2[t]/(\Phi_{19})$ ? Quel est le nombre d'éléments de $\mathbb{F}_2[t]/(\Phi_{19})$ (on ne demande pas de l'écrire en décimal) ? Est-ce un corps ? L'élément $\bar t$ est-il primitif (on parle toujours dans $\mathbb{F}_2[t]/(\Phi_{19})$) ? Question subsidiaire, plus difficile : quelle est la décomposition en facteurs irréductibles du polynôme $\Phi_{19}(X) = X^{18} + X^{17} + \cdots + X + 1$ vu comme 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} (D) (1) On a ${(t+1)} \penalty0\, {(t^{18}+t^{17} + \cdots + t^2+t+1)} = (t^{19}+t^{18} + \cdots + t^3+t^2+t) + (t^{18}+t^{17} + \cdots + t^2+t+1)$, et en regroupant par puissances de $t$ tous les termes de $t^{18} + t^{18}$ à $t+t$ s'annulent, et il ne reste que $t^{19} + 1$. \leavevmode\hphantom{(D)} (2) Dans $\mathbb{F}_2[t]/(t^{19}+1)$, on a $\bar t^{19} = 1$ puisque $t^{19} \equiv 1 \pmod{t^{19}+1}$, et si $0