From 2c0256cb192f4579ba7ae9c4d57886a5af93c043 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 24 Oct 2011 15:39:14 +0200 Subject: Re-encode as utf-8. --- exercices.tex | 276 +++++----- exercices2.tex | 263 ++++----- rappels-maths.tex | 1543 +++++++++++++++++++++++++++-------------------------- 3 files changed, 1043 insertions(+), 1039 deletions(-) diff --git a/exercices.tex b/exercices.tex index 69b61d6..d512820 100644 --- a/exercices.tex +++ b/exercices.tex @@ -1,7 +1,8 @@ %% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} -\usepackage[latin1]{inputenc} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} @@ -24,12 +25,13 @@ \newcommand{\signe}{\operatorname{signe}} \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Fr}} +\DeclareUnicodeCharacter{00A0}{~} % \newif\ifcorrige \corrigetrue \newenvironment{corrige}% {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% -\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\relax\else\egroup\fi\par} % @@ -37,9 +39,9 @@ % \begin{document} \ifcorrige -\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}} +\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}} \else -\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}} +\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}} \fi \author{} \date{} @@ -53,115 +55,115 @@ \exercice -(A) Quel entier entre $0$ et $100$ est congru à $19$ modulo $13$ et à -$13$ modulo $19$ ? +(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 +(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 + 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 + 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$. + 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$ ? +(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 = +(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 + \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. + \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$.) +(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 +(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 + 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$. + 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 ?) +(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 +(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$. + 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$. +(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. +(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} % @@ -170,16 +172,16 @@ $192$ modulo \exercice -(A) Pour chaque élément de $\mathbb{Z}/18\mathbb{Z}$, calculer son +(A) Pour chaque élément de $\mathbb{Z}/18\mathbb{Z}$, calculer son ordre additif et, si cela a un sens, son ordre multiplicatif. Quels -sont les entiers primitifs modulo $18$ ? +sont les entiers primitifs modulo $18$ ? -(B) Dresser la table d'un isomorphisme entre le groupe additif -$\mathbb{Z}/n\mathbb{Z}$ (pour un $n$ à déterminer) et le groupe +(B) Dresser la table d'un isomorphisme entre le groupe additif +$\mathbb{Z}/n\mathbb{Z}$ (pour un $n$ à déterminer) et le groupe multiplicatif $(\mathbb{Z}/18\mathbb{Z})^\times$. -(C) Que vaut $7^{333\,333}$ modulo $18$ ? Que vaut $5^{6\,000\,004}$ -modulo $18$ ? +(C) Que vaut $7^{333\,333}$ modulo $18$ ? Que vaut $5^{6\,000\,004}$ +modulo $18$ ? \begin{corrige} (A)\strut\par{\footnotesize @@ -206,27 +208,27 @@ $\bar{17}$&$18$&$2$\\ \end{tabular} \par} -Il existe donc des éléments primitifs, il en existe -$\varphi(\varphi(18)) = \varphi(6) = 2$, à savoir $\bar 5$ et -$\bar{11}$. (Les entiers primitifs modulo $18$ sont donc ceux congrus -à $5$ ou $11$ modulo $18$.) +Il existe donc des éléments primitifs, il en existe +$\varphi(\varphi(18)) = \varphi(6) = 2$, à savoir $\bar 5$ et +$\bar{11}$. (Les entiers primitifs modulo $18$ sont donc ceux congrus +à $5$ ou $11$ modulo $18$.) -(B) Une fois choisi un élément primitif, disons $g = \bar 5$, +(B) Une fois choisi un élément primitif, disons $g = \bar 5$, l'isomorphisme $\mathbb{Z}/6\mathbb{Z} \to -(\mathbb{Z}/18\mathbb{Z})^\times$ est donné par $\bar k \mapsto g^k$, -soit ici : +(\mathbb{Z}/18\mathbb{Z})^\times$ est donné par $\bar k \mapsto g^k$, +soit ici : \begin{tabular}{c|cccccc} $\bar k \in \mathbb{Z}/6\mathbb{Z}$&$\bar 0$&$\bar 1$&$\bar 2$&$\bar 3$&$\bar 4$&$\bar 5$\\\hline $g^k \in (\mathbb{Z}/18\mathbb{Z})^\times$&$\bar 1$&$\bar 5$&$\bar 7$&$\bar{17}$&$\bar{13}$&$\bar{11}$\\ \end{tabular} -(C) On vient de voir que l'ordre de $\bar 7$ dans -$(\mathbb{Z}/18\mathbb{Z})^\times$ vaut $3$, donc $7^{3k} \equiv 1 -\pmod{18}$ pour tout $k$ et en particulier pour $k = 111\,111$, de +(C) On vient de voir que l'ordre de $\bar 7$ dans +$(\mathbb{Z}/18\mathbb{Z})^\times$ vaut $3$, donc $7^{3k} \equiv 1 +\pmod{18}$ pour tout $k$ et en particulier pour $k = 111\,111$, de sorte que $7^{333\,333} \equiv 1 \pmod{18}$. Pour ce qui est de $5^{6\,000\,004}$, il suffit de chercher la valeur en regard de -$6\,000\,004$ modulo $6$ dans le tableau ci-dessus : on a $5^6 \equiv +$6\,000\,004$ modulo $6$ dans le tableau ci-dessus : on a $5^6 \equiv 1 \pmod{18}$ donc $5^{6\,000\,000} \equiv 1$ donc $5^{6\,000\,004} \equiv 5^4 \equiv 13 \pmod{18}$. \end{corrige} @@ -237,34 +239,34 @@ $6\,000\,004$ modulo \exercice -(A) Calculer $\varphi(3\,125)$. Que vaut $2^{5\,000\,000}$ -modulo $3\,125$ ? +(A) Calculer $\varphi(3\,125)$. Que vaut $2^{5\,000\,000}$ +modulo $3\,125$ ? -(B) Que vaut $2^{5\,000\,000}$ modulo $32$ ? +(B) Que vaut $2^{5\,000\,000}$ modulo $32$ ? -(C) Sachant que $293\times 32 - 3\times 3\,125 = 1$, quels sont les -cinq derniers chiffres en base $10$ de $2^{5\,000\,000}$ ? +(C) Sachant que $293\times 32 - 3\times 3\,125 = 1$, quels sont les +cinq derniers chiffres en base $10$ de $2^{5\,000\,000}$ ? \begin{corrige} -(A) On a $3\,125 = 5^5$ donc $\varphi(3\,125) = 4\times 5^4 = 2\,500$. - Comme $2$ est premier avec $3\,125$, le théorème d'Euler entraîne +(A) On a $3\,125 = 5^5$ donc $\varphi(3\,125) = 4\times 5^4 = 2\,500$. + Comme $2$ est premier avec $3\,125$, le théorème d'Euler entraîne que $2^{2\,500} \equiv 1 \pmod{3\,125}$, donc $2^{5\,000\,000} \equiv 1 \pmod{3\,125}$ (puisque $2\,500\,|\,5\,000\,000$). -(B) (Attention à ne pas chercher à appliquer le théorème d'Euler ! - $2$ n'est pas du tout premier avec $32$...) On a $32 = 2^5$ donc - $32 | 2^{5\,000\,000}$, c'est-à-dire que $2^{5\,000\,000} \equiv 0 +(B) (Attention à ne pas chercher à appliquer le théorème d'Euler ! + $2$ n'est pas du tout premier avec $32$...) On a $32 = 2^5$ donc + $32 | 2^{5\,000\,000}$, c'est-à-dire que $2^{5\,000\,000} \equiv 0 \pmod{32}$. -(C) Trouver les cinq derniers chiffres de $2^{5\,000\,000}$ en - base $10$ revient à calculer ce nombre modulo $100\,000 = 10^5 = 2^5 +(C) Trouver les cinq derniers chiffres de $2^{5\,000\,000}$ en + base $10$ revient à calculer ce nombre modulo $100\,000 = 10^5 = 2^5 \times 5^5 = 32 \times 3\,125$. On vient de le calculer modulo $32$ - (il vaut $0$) et modulo $3\,125$ (il vaut $1$). Le théorème chinois + (il vaut $0$) et modulo $3\,125$ (il vaut $1$). Le théorème chinois assure donc que $2^{5\,000\,000}$ est, modulo $100\,000$, l'unique classe de congruence possible qui vaut $0$ modulo $32$ et $1$ - modulo $3\,125$. C'est donc $293\times 32 = 1 + 3\times 3\,125 = + modulo $3\,125$. C'est donc $293\times 32 = 1 + 3\times 3\,125 = 9\,376$. Les cinq derniers chiffres de $2^{5\,000\,000}$ en - base $10$ sont donc : $09376$. + base $10$ sont donc : $09376$. \end{corrige} % @@ -275,55 +277,55 @@ cinq derniers chiffres en base Les nombres $593$ et $1\,187$ sont premiers. -(A) Expliquer brièvement pourquoi, si $b^2 = \bar 1$ avec $b \in +(A) Expliquer brièvement pourquoi, si $b^2 = \bar 1$ avec $b \in \mathbb{Z}/1187\mathbb{Z}$ alors $b = \bar 1$ ou $b = -\bar 1$ -(indication : factoriser $b^2 - \bar 1$). +(indication : factoriser $b^2 - \bar 1$). -(B) Quelles sont les valeurs possibles de $a^{593}$ modulo $1\,187$ -(pour $a$ un entier quelconque) ? +(B) Quelles sont les valeurs possibles de $a^{593}$ modulo $1\,187$ +(pour $a$ un entier quelconque) ? -(C) Montrer que $a^{593} \equiv -1 \pmod{1\,187}$ si et seulement si -$a$ est primitif modulo $1\,187$ \emph{ou} $a \equiv -1 +(C) Montrer que $a^{593} \equiv -1 \pmod{1\,187}$ si et seulement si +$a$ est primitif modulo $1\,187$ \emph{ou} $a \equiv -1 \pmod{1\,187}$. \begin{corrige} -(A) Si $b^2 = \bar 1$ avec $b \in \mathbb{Z}/1187\mathbb{Z}$, alors +(A) Si $b^2 = \bar 1$ avec $b \in \mathbb{Z}/1187\mathbb{Z}$, alors $(b-\bar 1)(b+\bar 1) = b^2 - \bar 1 = \bar 0$. Comme $\mathbb{Z}/1187\mathbb{Z}$ est un corps (et en particulier, un - anneau intègre), un produit ne peut être nul que si un des deux + anneau intègre), un produit ne peut être nul que si un des deux facteurs est nul, donc soit $b - \bar 1 = \bar 0$, soit $b + \bar 1 - = \bar 0$, c'est-à-dire soit $b = \bar 1$ soit $b = -\bar 1$. + = \bar 0$, c'est-à-dire soit $b = \bar 1$ soit $b = -\bar 1$. -(B) On a $1\,186 = 2\times 593$. Le théorème d'Euler ou de Fermat +(B) On a $1\,186 = 2\times 593$. Le théorème d'Euler ou de Fermat assure que $a^{1\,186} \equiv 1 \pmod{1\,187}$ pour tout $a$ non - multiple de $1\,187$, c'est-à-dire $(a^{593})^2 \equiv 1 - \pmod{1\,187}$ : d'après ce qu'on vient de voir, ceci signifie que + multiple de $1\,187$, c'est-à-dire $(a^{593})^2 \equiv 1 + \pmod{1\,187}$ : d'après ce qu'on vient de voir, ceci signifie que $a^{593}\equiv 1$ ou $a^{593}\equiv -1$. (Et ces deux cas se produisent effectivement, comme le montrent les exemples de $a=1$ et - $a=-1$.) Enfin, si $a$ est multiple de $1\,187$, on a évidemment + $a=-1$.) Enfin, si $a$ est multiple de $1\,187$, on a évidemment $a^{593} \equiv 0^{593} = 0 \pmod{1\,187}$. Les trois valeurs - possibles sont donc : $+1, -1, 0$. + possibles sont donc : $+1, -1, 0$. -(Remarquons que les deux sous-questions ci-dessus n'ont pas utilisé le - fait que $593$ était premier, et fonctionnaient également en - remplaçant $1\,187$ par n'importe quel nombre premier $p$ impair et +(Remarquons que les deux sous-questions ci-dessus n'ont pas utilisé le + fait que $593$ était premier, et fonctionnaient également en + remplaçant $1\,187$ par n'importe quel nombre premier $p$ impair et $593$ par $(p-1)/2$.) -(C) Tout d'abord, si $a^{593} \not\equiv 0 \pmod{1\,187}$ alors $a$ - n'est pas multiple de $1\,187$, c'est-à-dire qu'il est premier avec +(C) Tout d'abord, si $a^{593} \not\equiv 0 \pmod{1\,187}$ alors $a$ + n'est pas multiple de $1\,187$, c'est-à-dire qu'il est premier avec $1\,187$. Lorsque c'est le cas, l'ordre multiplicatif de $a$ doit - diviser $\varphi(1\,187) = 2\times 593$ : les diviseurs de ce nombre - sont $1$, $2$, $593$ et $1\,186$. Le seul élément (de n'importe - quel groupe, noté multiplicativement) dont l'ordre est $1$ est $1$ - (le neutre) ; la première question montre que le seul élément de - $(\mathbb{Z}/1187\mathbb{Z})^\times$ dont l'ordre est $2$ est $-1$ ; + diviser $\varphi(1\,187) = 2\times 593$ : les diviseurs de ce nombre + sont $1$, $2$, $593$ et $1\,186$. Le seul élément (de n'importe + quel groupe, noté multiplicativement) dont l'ordre est $1$ est $1$ + (le neutre) ; la première question montre que le seul élément de + $(\mathbb{Z}/1187\mathbb{Z})^\times$ dont l'ordre est $2$ est $-1$ ; si l'ordre de $a$ est $593$ (en particulier, $a$ n'est pas primitif), alors $a^{593} \equiv 1 \pmod{1\,187}$. Enfin, si - l'ordre de $a$ est $1\,186$, c'est-à-dire si $a$ est primitif, alors - $a^{593}$ ne peut pas valoir $1$, et doit donc valoir $-1$. Tout - ceci mis ensemble, on a bien : $a^{593} \equiv -1 \pmod{1\,187}$ si + l'ordre de $a$ est $1\,186$, c'est-à-dire si $a$ est primitif, alors + $a^{593}$ ne peut pas valoir $1$, et doit donc valoir $-1$. Tout + ceci mis ensemble, on a bien : $a^{593} \equiv -1 \pmod{1\,187}$ si et seulement si $a \equiv -1 \pmod{1\,187}$ ou bien $a$ est primitif - modulo $1\,187$. + modulo $1\,187$. \end{corrige} % diff --git a/exercices2.tex b/exercices2.tex index c36ddd2..7cee362 100644 --- a/exercices2.tex +++ b/exercices2.tex @@ -1,7 +1,7 @@ %% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} -\usepackage[latin1]{inputenc} +\usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{times} % A tribute to the worthy AMS: @@ -25,12 +25,13 @@ \newcommand{\signe}{\operatorname{signe}} \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Fr}} +\DeclareUnicodeCharacter{00A0}{~} % \newif\ifcorrige \corrigetrue \newenvironment{corrige}% {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% -\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\relax\else\egroup\fi\par} % @@ -38,9 +39,9 @@ % \begin{document} \ifcorrige -\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}} +\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}} \else -\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}} +\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}} \fi \author{} \date{} @@ -54,42 +55,42 @@ \exercice -Déterminer une relation de Bézout entre les polynômes $A = t^7 - t^6 + +Déterminer une relation de Bézout entre les polynômes $A = t^7 - t^6 + t^4 - t + 1$ et $B = t^6 + t^5 - t^4 + t^3 + t^2 + 1$ dans $\mathbb{F}_3[t]$. Quel est l'inverse de $\bar B$ dans -$\mathbb{F}_3[t]/(A)$ ? +$\mathbb{F}_3[t]/(A)$ ? \begin{corrige} -On calcule les divisions euclidiennes successives : $t^7 - t^6 + t^4 - +On calcule les divisions euclidiennes successives : $t^7 - t^6 + t^4 - t + 1 = (t+1)\penalty0 (t^6+t^5-t^4+t^3+t^2+1) + (t^4+t^3-t^2+t)$, puis $t^6 + t^5 - t^4 + t^3 + t^2 + 1 = t^2(t^4+t^3-t^2+t) + (t^2+1)$, puis $t^4 + t^3 - t^2 + t = (t^2+t+1)\penalty0 (t^2+1) - 1$. Le pgcd -de $A$ et $B$ est donc $1$ (ou $-1$, mais on a choisi de le prendre +de $A$ et $B$ est donc $1$ (ou $-1$, mais on a choisi de le prendre unitaire). -On calcule alors des relations $UP + VQ = D$ comme suit : +On calcule alors des relations $UP + VQ = D$ comme suit : \begin{itemize} -\item[$\bullet$] $U= -1$ ; $P= t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q= - t^2+1$ ; $D= 1$ (d'après la dernière division effectuée). -\item[$\bullet$] $U= -t^2$ ; $P= t^4+t^3-t^2+t$ ; $V= 1$ ; $Q= - t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^2+1$ (d'après l'avant-dernière - division effectuée). -\item[$\bullet$] $U= -t^2(t^2+t+1)-1 = -t^4-t^3-t^2-1$ ; $P= - t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$ - (en remplaçant la valeur de $t^2+1$ donnée par la dernière égalité à - la place du $Q$ de l'égalité précédente). -\item[$\bullet$] $U= 1$ ; $P= t^7-t^6+t^4-t+1$ ; $V= -(t+1)$ ; $Q= - t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^4+t^3-t^2+t$ (d'après la première - division effectuée). -\item[$\bullet$] $U= -t^4-t^3-t^2-1$ ; $P= t^7-t^6+t^4-t+1$ ; $V= - (t^2+t+1) - (-t^4-t^3-t^2-1)\penalty0 (t+1) = t^5-t^4-t^3-t^2-t-1$ ; - $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$ (en remplaçant la valeur de - $t^4+t^3-t^2+t$ donnée par la dernière égalité à la place du $P$ de - l'égalité précédente. +\item[$\bullet$] $U= -1$ ; $P= t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q= + t^2+1$ ; $D= 1$ (d'après la dernière division effectuée). +\item[$\bullet$] $U= -t^2$ ; $P= t^4+t^3-t^2+t$ ; $V= 1$ ; $Q= + t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^2+1$ (d'après l'avant-dernière + division effectuée). +\item[$\bullet$] $U= -t^2(t^2+t+1)-1 = -t^4-t^3-t^2-1$ ; $P= + t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$ + (en remplaçant la valeur de $t^2+1$ donnée par la dernière égalité à + la place du $Q$ de l'égalité précédente). +\item[$\bullet$] $U= 1$ ; $P= t^7-t^6+t^4-t+1$ ; $V= -(t+1)$ ; $Q= + t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^4+t^3-t^2+t$ (d'après la première + division effectuée). +\item[$\bullet$] $U= -t^4-t^3-t^2-1$ ; $P= t^7-t^6+t^4-t+1$ ; $V= + (t^2+t+1) - (-t^4-t^3-t^2-1)\penalty0 (t+1) = t^5-t^4-t^3-t^2-t-1$ ; + $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$ (en remplaçant la valeur de + $t^4+t^3-t^2+t$ donnée par la dernière égalité à la place du $P$ de + l'égalité précédente. \end{itemize} -On a donc trouvé la relation de Bézout : $(-t^4-t^3-t^2-1) \penalty0 +On a donc trouvé la relation de Bézout : $(-t^4-t^3-t^2-1) \penalty0 (t^7-t^6+t^4-t+1) + (t^5-t^4-t^3-t^2-t-1) \penalty0 (t^6+t^5-t^4+t^3+t^2+1) = 1$. @@ -104,54 +105,54 @@ t^3-\bar t^2-\bar t-1$. \exercice -(A) On admet que le polynôme $P := t^4 + t^3 + t^2 + t + 1 \in -\mathbb{F}_3[t]$ est irréductible. Combien d'éléments a $F := -\mathbb{F}_3[t]/(P)$ ? +(A) On admet que le polynôme $P := t^4 + t^3 + t^2 + t + 1 \in +\mathbb{F}_3[t]$ est irréductible. Combien d'éléments a $F := +\mathbb{F}_3[t]/(P)$ ? -(B) Quel est l'ordre (additif) de $\bar t$ dans le groupe additif -de $F$ ? +(B) Quel est l'ordre (additif) de $\bar t$ dans le groupe additif +de $F$ ? -(C) Calculer $\bar t^4$ et $\bar t^5$. Quel est l'ordre +(C) Calculer $\bar t^4$ et $\bar t^5$. Quel est l'ordre (multiplicatif) de $\bar t$ dans le groupe multiplicatif $F^\times$ -des éléments non-nuls de $F$ ? L'élément $\bar t$ est-il primitif ? -Le polynôme $P$ est-il primitif ? +des éléments non-nuls de $F$ ? L'élément $\bar t$ est-il primitif ? +Le polynôme $P$ est-il primitif ? -(D) Quels sont les conjugués de $\bar t$ (=ses images successives par -le morphisme de Frobenius) ? Quel est le degré de $\bar t$ ? +(D) Quels sont les conjugués de $\bar t$ (=ses images successives par +le morphisme de Frobenius) ? Quel est le degré de $\bar t$ ? \begin{corrige} -(A) Le nombre d'éléments de $F$ est $3^{\deg P} = 3^4 = 81$ (comme le - nombre de polynômes de degré $<4$ sur $\mathbb{F}_3$). On peut donc +(A) Le nombre d'éléments de $F$ est $3^{\deg P} = 3^4 = 81$ (comme le + nombre de polynômes de degré $<4$ sur $\mathbb{F}_3$). On peut donc noter $F = \mathbb{F}_{81}$. Il s'agit d'un corps, puisque $P$ est - irréductible. - -(B) Les multiples additifs de $\bar t$ sont $0$, $\bar t$ et $2\bar t - = -\bar t$, après quoi on retombe sur $0$ (la caractéristique de $F$ - est $3$). L'ordre additif de $\bar t$, comme celui de n'importe - quel élément non nul dans un corps de caractéristique $3$, est - donc $3$. - -(C) On a $\bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ comme il - résulte d'une division euclidienne (évidente) de $t^4$ par $P$. Par - conséquent, $\bar t^5 = -\bar t^4 - \bar t^3 - \bar t^2 - \bar t = - 1$ (on peut aussi faire la division euclidienne de $t^5$ par $P$). - Ceci signifie que l'ordre multiplicatif de $\bar t$ divise $5$, - c'est-à-dire qu'il vaut $1$ ou $5$. Comme il ne vaut pas $1$ - (puisque $\bar t$ ne vaut pas $1$), il vaut $5$. De fait, les - puissances de $\bar t$ sont : $1$, $\bar t$, $\bar t^2$, $\bar t^3$ - et $-\bar t^3 - \bar t^2 - \bar t - 1$, après quoi on retombe - sur $1$. Comme $F^\times$ a $80$ éléments, $\bar t$ n'est pas - primitif (un élément primitif est un élément d'ordre - multiplicatif $80$). Ceci signifie précisément que le polynôme $P$ + irréductible. + +(B) Les multiples additifs de $\bar t$ sont $0$, $\bar t$ et $2\bar t + = -\bar t$, après quoi on retombe sur $0$ (la caractéristique de $F$ + est $3$). L'ordre additif de $\bar t$, comme celui de n'importe + quel élément non nul dans un corps de caractéristique $3$, est + donc $3$. + +(C) On a $\bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ comme il + résulte d'une division euclidienne (évidente) de $t^4$ par $P$. Par + conséquent, $\bar t^5 = -\bar t^4 - \bar t^3 - \bar t^2 - \bar t = + 1$ (on peut aussi faire la division euclidienne de $t^5$ par $P$). + Ceci signifie que l'ordre multiplicatif de $\bar t$ divise $5$, + c'est-à-dire qu'il vaut $1$ ou $5$. Comme il ne vaut pas $1$ + (puisque $\bar t$ ne vaut pas $1$), il vaut $5$. De fait, les + puissances de $\bar t$ sont : $1$, $\bar t$, $\bar t^2$, $\bar t^3$ + et $-\bar t^3 - \bar t^2 - \bar t - 1$, après quoi on retombe + sur $1$. Comme $F^\times$ a $80$ éléments, $\bar t$ n'est pas + primitif (un élément primitif est un élément d'ordre + multiplicatif $80$). Ceci signifie précisément que le polynôme $P$ n'est pas primitif. -(D) Le morphisme de Frobenius est l'application $x \mapsto x^3$ - dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images - successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^3$, +(D) Le morphisme de Frobenius est l'application $x \mapsto x^3$ + dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images + successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^3$, puis $\bar t^9 = \bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ (car - $\bar t^5 = 1$ à ce qu'on a vu), et ensuite on retombe sur $\bar - t^{81} = \bar t$. Le degré de $\bar t$ est $4$ (c'est forcément le - degré de $P$). + $\bar t^5 = 1$ à ce qu'on a vu), et ensuite on retombe sur $\bar + t^{81} = \bar t$. Le degré de $\bar t$ est $4$ (c'est forcément le + degré de $P$). \end{corrige} % @@ -160,29 +161,29 @@ le morphisme de Frobenius) \exercice -(A) On admet que le polynôme $P := t^4 + t + 1 \in \mathbb{F}_2[t]$ -est irréductible. Combien d'éléments a $F := \mathbb{F}_2[t]/(P)$ ? +(A) On admet que le polynôme $P := t^4 + t + 1 \in \mathbb{F}_2[t]$ +est irréductible. Combien d'éléments a $F := \mathbb{F}_2[t]/(P)$ ? -(B) Dresser la liste des puissances successives de $\bar t$ dans $F$. -Quel est l'ordre de $\bar t$ ? Est-il primitif ? Quel est l'inverse -de $\bar t$ ? Quels sont tous les éléments primitifs de $F$ ? Quel -est l'ordre multiplicatif de $\bar t^3$ ? Même question pour $\bar +(B) Dresser la liste des puissances successives de $\bar t$ dans $F$. +Quel est l'ordre de $\bar t$ ? Est-il primitif ? Quel est l'inverse +de $\bar t$ ? Quels sont tous les éléments primitifs de $F$ ? Quel +est l'ordre multiplicatif de $\bar t^3$ ? Même question pour $\bar t^5$. -(C) Quels sont les conjugués de $\bar t$ ? Quel est son degré ? -Mêmes questions pour $\bar t^3$. Mêmes questions pour $\bar t^5$. +(C) Quels sont les conjugués de $\bar t$ ? Quel est son degré ? +Mêmes questions pour $\bar t^3$. Mêmes questions pour $\bar t^5$. -(D) Quels sont les éléments de l'unique corps à $4$ éléments contenu -dans $F$ ? +(D) Quels sont les éléments de l'unique corps à $4$ éléments contenu +dans $F$ ? \begin{corrige} -(A) Le nombre d'éléments de $F$ est $2^{\deg P} = 2^4 = 16$ (comme le - nombre de polynômes de degré $<4$ sur $\mathbb{F}_2$). On peut donc +(A) Le nombre d'éléments de $F$ est $2^{\deg P} = 2^4 = 16$ (comme le + nombre de polynômes de degré $<4$ sur $\mathbb{F}_2$). On peut donc noter $F = \mathbb{F}_{16}$. Il s'agit d'un corps, puisque $P$ est - irréductible. + irréductible. -(B) On calcule successivement en multipliant par $t$ et en se - rappelant que $t^4 \equiv t+1 \pmod{P}$ : +(B) On calcule successivement en multipliant par $t$ et en se + rappelant que $t^4 \equiv t+1 \pmod{P}$ : \begin{tabular}{r|l} $i$&$\bar t^i$\\\hline @@ -204,52 +205,52 @@ $14$&$\bar t^4+\bar t^3+\bar t = \bar t^3+1$\\\hline $15$&$\bar t^4+\bar t = 1$\\ \end{tabular} -L'ordre de $\bar t$ est donc $15$, il est primitif puisque $\#F^\times -= \#F-1 = 15$, tous les éléments non-nuls de $F$ ont été listés -ci-dessus et on a même, plus précisément, établi un isomorphisme de +L'ordre de $\bar t$ est donc $15$, il est primitif puisque $\#F^\times += \#F-1 = 15$, tous les éléments non-nuls de $F$ ont été listés +ci-dessus et on a même, plus précisément, établi un isomorphisme de groupes $(\mathbb{Z}/15\mathbb{Z}) \to F^\times$ par $\bar\imath -\mapsto \bar t^i$. Cet isomorphisme permet de répondre facilement aux -questions suivantes : l'inverse de $\bar t$ est celui qui correspond à -l'opposé de $1$, soit $\bar t^{14} = \bar t^3+1$. Les éléments -primitifs sont ceux qui correspondent aux générateurs de -$\mathbb{Z}/15\mathbb{Z}$ (c'est-à-dire les classes des nombres +\mapsto \bar t^i$. Cet isomorphisme permet de répondre facilement aux +questions suivantes : l'inverse de $\bar t$ est celui qui correspond à +l'opposé de $1$, soit $\bar t^{14} = \bar t^3+1$. Les éléments +primitifs sont ceux qui correspondent aux générateurs de +$\mathbb{Z}/15\mathbb{Z}$ (c'est-à-dire les classes des nombres premiers avec $15$, soit $\bar 1$, $\bar 2$, $\bar 4$, $\bar 7$, $\bar 8$, $\bar{11}$, $\bar{13}$, $\bar{14}$), donc $\bar t$, $\bar t^2$, $\bar t^4 = \bar t+1$, $\bar t^7 = \bar t^3+\bar t+1$, $\bar t^8 = \bar t^2+1$, $\bar t^{11} = \bar t^3+\bar t^2+\bar t$, $\bar t^{13} = \bar t^3+\bar t^2+1$ et $\bar t^{14} = \bar t^3+1$. L'ordre -(multiplicatif) de $\bar t^3$ dans $F^\times$ est le même que l'ordre -(additif) de $3$ dans $\mathbb{Z}/15\mathbb{Z}$, soit $5$, et de même -l'ordre multiplicatif de $\bar t^5$ dans $F^\times$ est $3$. - -(C) Le morphisme de Frobenius est l'application $x \mapsto x^2$ -dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images -successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^2$, -$\bar t^4 = \bar t+1$, $\bar t^8 = \bar t^2+1$ après quoi on retombe -sur $\bar t^{16} = \bar t$. Le degré de $\bar t$ est $4$ (c'est -forcément le degré de $P$). Pour ce qui est du degré de $\bar t^3$, -ses images successives par le Frobenius sont : $\bar t^3$ lui-même, +(multiplicatif) de $\bar t^3$ dans $F^\times$ est le même que l'ordre +(additif) de $3$ dans $\mathbb{Z}/15\mathbb{Z}$, soit $5$, et de même +l'ordre multiplicatif de $\bar t^5$ dans $F^\times$ est $3$. + +(C) Le morphisme de Frobenius est l'application $x \mapsto x^2$ +dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images +successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^2$, +$\bar t^4 = \bar t+1$, $\bar t^8 = \bar t^2+1$ après quoi on retombe +sur $\bar t^{16} = \bar t$. Le degré de $\bar t$ est $4$ (c'est +forcément le degré de $P$). Pour ce qui est du degré de $\bar t^3$, +ses images successives par le Frobenius sont : $\bar t^3$ lui-même, $\bar t^6 = \bar t^3+\bar t^2$, $\bar t^{12} = \bar t^3+\bar t^2+\bar -t+1$ et $\bar t^{24} = \bar t^9 = \bar t^3+\bar t$, après quoi on -retombe sur $\bar t^{48} = \bar t^3$ ; donc le degré de $\bar t^3$ est -également $4$. Enfin, pour calculer le degré de $\bar t^5$, on a ses -images successives qui sont $\bar t^5 = \bar t^2+\bar t$ lui-même et +t+1$ et $\bar t^{24} = \bar t^9 = \bar t^3+\bar t$, après quoi on +retombe sur $\bar t^{48} = \bar t^3$ ; donc le degré de $\bar t^3$ est +également $4$. Enfin, pour calculer le degré de $\bar t^5$, on a ses +images successives qui sont $\bar t^5 = \bar t^2+\bar t$ lui-même et $\bar t^{10} = \bar t^2+\bar t+1$, puis $\bar t^{20} = \bar t^5$, donc -il n'y a que deux conjugués (en comptant $\bar t^5$ lui-même), et son -degré est $2$. - -(D) On sait que $\mathbb{F}_4$ est contenu dans $F = \mathbb{F}_{16}$ -car $16$ est une puissance de $4$, et on sait qu'alors $\mathbb{F}_4 = -\{x\in F : x^4=x\}$. Une façon de trouver ces éléments est de -réécrire $x^4 = x$ comme $(x^2)^2 = x$ (on retombe sur $x$ après deux -applications du Frobenius : ou encore, le degré de $x$ est $1$ -ou $2$) ; les éléments vérifiant ceci sont $0$ et $1$, bien sûr, et +il n'y a que deux conjugués (en comptant $\bar t^5$ lui-même), et son +degré est $2$. + +(D) On sait que $\mathbb{F}_4$ est contenu dans $F = \mathbb{F}_{16}$ +car $16$ est une puissance de $4$, et on sait qu'alors $\mathbb{F}_4 = +\{x\in F : x^4=x\}$. Une façon de trouver ces éléments est de +réécrire $x^4 = x$ comme $(x^2)^2 = x$ (on retombe sur $x$ après deux +applications du Frobenius : ou encore, le degré de $x$ est $1$ +ou $2$) ; les éléments vérifiant ceci sont $0$ et $1$, bien sûr, et aussi $\bar t^5 = \bar t^2+\bar t$ comme on vient de le voir, et -forcément $\bar t^5 + 1 = \bar t^2+\bar t+1$ (puisqu'un corps est -stable ar addition). Une autre façon de résoudre $x^4 = x$ est de le -réécrire comme $x=0$ ou bien $x^3 = 1$, c'est-à-dire qu'il s'agit de -$0$ et des éléments d'ordre divisant $3$, donc, d'après l'isomorphisme -déjà déterminé, $\bar t^5 = \bar t^2+\bar t$ et $\bar t^{10} = \bar +forcément $\bar t^5 + 1 = \bar t^2+\bar t+1$ (puisqu'un corps est +stable ar addition). Une autre façon de résoudre $x^4 = x$ est de le +réécrire comme $x=0$ ou bien $x^3 = 1$, c'est-à-dire qu'il s'agit de +$0$ et des éléments d'ordre divisant $3$, donc, d'après l'isomorphisme +déjà déterminé, $\bar t^5 = \bar t^2+\bar t$ et $\bar t^{10} = \bar t^2+\bar t+1$. \end{corrige} @@ -260,30 +261,30 @@ t^2+\bar t+1$. \exercice Calculer le pgcd dans $\mathbb{F}_{11}[t]$ de $t^2 - 2$ et $t^{11}-t$. -En déduire que $2$ n'est pas un carré dans $\mathbb{F}_{11}$ -(c'est-à-dire qu'il n'existe pas de $\alpha \in \mathbb{F}_{11}$ tel -que $\alpha^2 = 2$ ; indication : de quels polynômes intéressants -$\alpha$ serait-il racine ?). +En déduire que $2$ n'est pas un carré dans $\mathbb{F}_{11}$ +(c'est-à-dire qu'il n'existe pas de $\alpha \in \mathbb{F}_{11}$ tel +que $\alpha^2 = 2$ ; indication : de quels polynômes intéressants +$\alpha$ serait-il racine ?). \begin{corrige} -On calcule les divisions euclidiennes successives : $t^{11}-t = (t^9 + +On calcule les divisions euclidiennes successives : $t^{11}-t = (t^9 + 2t^7 + 4t^5 - 3t^3 + 5t)\penalty0 (t^2-2) + 9t$, puis $t^2-2 = (5t)(9t) - 2$, le dernier reste est une constante donc le pgcd -vaut $1$. +vaut $1$. S'il y avait un $\alpha \in \mathbb{F}_{11}$ tel que $\alpha^2 = 2$, -alors il serait racine à la fois de $t^2 - 2$ en vertu de +alors il serait racine à la fois de $t^2 - 2$ en vertu de $\alpha^2=2$, et $t^{11} - t$ en vertu de $\alpha\in\mathbb{F}_{11}$ -(et du petit théorème de Fermat). C'est-à-dire que $t-\alpha$ serait -un facteur commu à $t^2-2$ et $t^{11}-t$, et on vient de voir qu'il +(et du petit théorème de Fermat). C'est-à-dire que $t-\alpha$ serait +un facteur commu à $t^2-2$ et $t^{11}-t$, et on vient de voir qu'il n'y en a pas. -\emph{Remarque :} Vérifier que $t^2-2$ et $t^{11}-t$ sont premiers -entre eux est une des parties du critère de Rabin pour vérifier que -$t^2-2$ est irréductible. Ici, il n'y a pas besoin d'en faire plus : +\emph{Remarque :} Vérifier que $t^2-2$ et $t^{11}-t$ sont premiers +entre eux est une des parties du critère de Rabin pour vérifier que +$t^2-2$ est irréductible. Ici, il n'y a pas besoin d'en faire plus : comme $t^2-2$ n'a pas de racine, cela signifie qu'il n'a pas de -facteur de degré $1$, et comme il est de degré $2$, il est -irréductible. +facteur de degré $1$, et comme il est de degré $2$, il est +irréductible. \end{corrige} % diff --git a/rappels-maths.tex b/rappels-maths.tex index 50168cf..8df213a 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -1,8 +1,8 @@ %% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} +\usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} -\usepackage[latin1]{inputenc} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} @@ -18,10 +18,10 @@ \newtheorem{comcnt}{Tout}[subsection] \newcommand\thingy{% \refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } -\newtheorem{defn}[comcnt]{Définition} +\newtheorem{defn}[comcnt]{Définition} \newtheorem{prop}[comcnt]{Proposition} \newtheorem{lem}[comcnt]{Lemme} -\newtheorem{thm}[comcnt]{Théorème} +\newtheorem{thm}[comcnt]{Théorème} \newtheorem{cor}[comcnt]{Corollaire} \newtheorem{rmk}[comcnt]{Remarque} \newtheorem{exmps}[comcnt]{Exemples} @@ -33,6 +33,7 @@ \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Frob}} \renewcommand{\qedsymbol}{\smiley} +\DeclareUnicodeCharacter{00A0}{~} % % % @@ -60,185 +61,185 @@ On appelle $\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ l'ensemble des entiers relatifs. Il a pour sous-ensemble $\mathbb{N} = \{0,1,2,3,\ldots\}$ l'ensemble des entiers naturels (ou positifs). -Sur $\mathbb{Z}$ on a les opérations : $+$ (addition) et $\times$ -(multiplication) ; et les éléments remarquables : $0$, $1$. Ces -données vérifient les propriétés suivantes : +Sur $\mathbb{Z}$ on a les opérations : $+$ (addition) et $\times$ +(multiplication) ; et les éléments remarquables : $0$, $1$. Ces +données vérifient les propriétés suivantes : \begin{enumerate} -\item Associativité de l'addition : $x+(y+z) = (x+y)+z$ -\item Neutralité de zéro pour l'addition : $0+x = x+0 = x$ -\item Existence d'opposés (=symétriques pour l'addition) : (pour - chaque $x$, il existe un élément noté $-x$ tel que) $x + (-x) = (-x) +\item Associativité de l'addition : $x+(y+z) = (x+y)+z$ +\item Neutralité de zéro pour l'addition : $0+x = x+0 = x$ +\item Existence d'opposés (=symétriques pour l'addition) : (pour + chaque $x$, il existe un élément noté $-x$ tel que) $x + (-x) = (-x) + x = 0$ -\item Commutativité de l'addition : $y+x = x+y$ -\item Distributivité de la multiplication sur l'addition : $x(y+z) = +\item Commutativité de l'addition : $y+x = x+y$ +\item Distributivité de la multiplication sur l'addition : $x(y+z) = xy + xz$ et $(x+y)z=xz+yz$ -\item Associativité de la multiplication : $x(yz) = (xy)z$ -\item Neutralité de un pour la multiplication : $1x = x1 = x$ -\item Commutativité de la multiplication : $yx = xy$ +\item Associativité de la multiplication : $x(yz) = (xy)z$ +\item Neutralité de un pour la multiplication : $1x = x1 = x$ +\item Commutativité de la multiplication : $yx = xy$ \end{enumerate} -Les trois premières propriétés traduisent le fait que $\mathbb{Z}$ est -un \emph{groupe} pour l'addition ; les quatre premières, que -$\mathbb{Z}$ est un \emph{groupe abélien} pour l'addition ; les sept -premières propriétés traduisent le fait que $\mathbb{Z}$ est un -\emph{anneau} ; les huit propriétés réunies traduisent le fait que +Les trois premières propriétés traduisent le fait que $\mathbb{Z}$ est +un \emph{groupe} pour l'addition ; les quatre premières, que +$\mathbb{Z}$ est un \emph{groupe abélien} pour l'addition ; les sept +premières propriétés traduisent le fait que $\mathbb{Z}$ est un +\emph{anneau} ; les huit propriétés réunies traduisent le fait que $\mathbb{Z}$ est un \textbf{anneau commutatif}. -Mieux : c'est un \emph{anneau intègre} : si $uv=0$ alors $u=0$ ou -$v=0$ (la réciproque est vraie dans n'importe quel anneau : $0x = x0 = +Mieux : c'est un \emph{anneau intègre} : si $uv=0$ alors $u=0$ ou +$v=0$ (la réciproque est vraie dans n'importe quel anneau : $0x = x0 = 0$). -Éléments inversibles : un \textbf{inversible} ou une \textbf{unité} -(dans un anneau commutatif) est un élément $x$ tel qu'il existe $y$ +Éléments inversibles : un \textbf{inversible} ou une \textbf{unité} +(dans un anneau commutatif) est un élément $x$ tel qu'il existe $y$ tel que $xy = 1$. Dans $\mathbb{Z}$, les inversibles sont $1$ et $-1$. -On a aussi sur $\mathbb{Z}$ une relation d'ordre : c'est-à-dire une -relation réflexive (on a toujours $x\leq x$), antisymétrique (si +On a aussi sur $\mathbb{Z}$ une relation d'ordre : c'est-à-dire une +relation réflexive (on a toujours $x\leq x$), antisymétrique (si $x\leq y$ et $y\leq x$ alors $x=y$) et transitive (si $x\leq y$ et $y\leq z$ alors $x\leq z$). % -\subsection{Écriture $b$-adique} +\subsection{Écriture $b$-adique} -Si $b\geq 2$ est un entier naturel, tout entier naturel $A$ s'écrit de -façon unique $A = \sum_{i=0}^{+\infty} a_i b^i$ avec $0\leq a_i1$, il y a toujours un nombre premier $p$ tel que $x < p -< 2x$ (\v Ceby\v sëv : « postulat de Bertrand », démontré en 1850). -De façon équivalente : si $p$ est premier, alors le nombre premier qui -le suit immédiatement est $<2p$. - -Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à -$\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée -Poussin : « théorème des nombres premiers », démontré en 1896). -Moralement : la probabilité qu'un nombre de $n$ bits aléatoire soit +< 2x$ (\v Ceby\v sëv : « postulat de Bertrand », démontré en 1850). +De façon équivalente : si $p$ est premier, alors le nombre premier qui +le suit immédiatement est $<2p$. + +Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à +$\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée +Poussin : « théorème des nombres premiers », démontré en 1896). +Moralement : la probabilité qu'un nombre de $n$ bits aléatoire soit premier est environ $\frac{1}{n\,\ln 2}$. -Beaucoup de questions ouvertes. Par exemple : Conjecture des nombres -premiers jumeaux : existe-t-il une infinité de nombres premiers $p$ +Beaucoup de questions ouvertes. Par exemple : Conjecture des nombres +premiers jumeaux : existe-t-il une infinité de nombres premiers $p$ tels que $p+2$ soit aussi premier (tels que $3$, $5$, $11$, $17$, -$29$, $41$, $59$, $71$...) ? +$29$, $41$, $59$, $71$...) ? \smallbreak -\textbf{Lemme de Gauß :} pour $p$ premier, si $p$ divise $ab$ alors -$p$ divise $a$ ou $p$ divise $b$. +\textbf{Lemme de Gauß :} pour $p$ premier, si $p$ divise $ab$ alors +$p$ divise $a$ ou $p$ divise $b$. % -\subsection{Décomposition en facteurs premiers} +\subsection{Décomposition en facteurs premiers} -Pour tout entier $n$ \emph{non nul}, il existe une écriture -\emph{unique} (à l'ordre près) de $n$ comme produit d'une \emph{unité} -($1$ ou $-1$) et de nombres premiers : en regroupant les facteurs -premiers $p$, +Pour tout entier $n$ \emph{non nul}, il existe une écriture +\emph{unique} (à l'ordre près) de $n$ comme produit d'une \emph{unité} +($1$ ou $-1$) et de nombres premiers : en regroupant les facteurs +premiers $p$, \[ n = u\, 2^{v_2(n)} \, 3^{v_3(n)} \cdots p^{v_p(n)}\cdots \] Ici, $v_p(n)$ (un entier naturel) est l'exposant de la plus grande -puissance de $p$ qui divise $n$ : on l'appelle \emph{valuation -$p$-adique} de $n$. Presque tous ces nombres sont nuls, ce qui permet +puissance de $p$ qui divise $n$ : on l'appelle \emph{valuation +$p$-adique} de $n$. Presque tous ces nombres sont nuls, ce qui permet de donner un sens au produit infini. Dire que $b|a$ signifie $v_p(b) -\leq v_p(a)$ pour tout $p$. +\leq v_p(a)$ pour tout $p$. -Quant à $u$, c'est simplement le signe de $n$. +Quant à $u$, c'est simplement le signe de $n$. -Exemple : $7920 = 2^4\times 3^2\times 5\times 11$, c'est-à-dire que +Exemple : $7920 = 2^4\times 3^2\times 5\times 11$, c'est-à-dire que $v_2(7920)=4$, $v_3(7920)=2$, $v_5(7920)=1$, $v_7(7920)=0$, $v_{11}(7920)=1$, et $v_p(7920)=0$ pour n'importe quel nombre premier $p\geq 13$. % -\subsection{Remarques sur la complexité} +\subsection{Remarques sur la complexité} Toujours pour des nombres de $n$ bits. -\textbf{Tests de primalité :} \emph{polynomiaux}. Un test polynomial -\emph{déterministe} est connu depuis seulement récemment -(Agrawal-Kayal-Saxena), démontrablement en $O(n^{12})$, sans doute -meilleur ($O(n^3)$ ?). En pratique, des tests probabilistes sont -suffisants et plus efficaces (p.e., Miller-Rabin « pratiquement » en -$O(n^2)$) éventuellement complétés par des certificats de primalité +\textbf{Tests de primalité :} \emph{polynomiaux}. Un test polynomial +\emph{déterministe} est connu depuis seulement récemment +(Agrawal-Kayal-Saxena), démontrablement en $O(n^{12})$, sans doute +meilleur ($O(n^3)$ ?). En pratique, des tests probabilistes sont +suffisants et plus efficaces (p.e., Miller-Rabin « pratiquement » en +$O(n^2)$) éventuellement complétés par des certificats de primalité (p.e., test d'Atkin). -\textbf{Algorithmes de factorisation :} \emph{lents}. Font appel à -des résultats difficiles de théorie algébrique et analytique des -nombres. La meilleure méthode connue (« méthode du crible général de -corps de nombres ») a une complexité « attendue » (et heuristique) en +\textbf{Algorithmes de factorisation :} \emph{lents}. Font appel à +des résultats difficiles de théorie algébrique et analytique des +nombres. La meilleure méthode connue (« méthode du crible général de +corps de nombres ») a une complexité « attendue » (et heuristique) en $O(e^{n^{1/3}\,(\log n)^{2/3}\,(\textrm{cte}+o(1))})$ (avec $\textrm{cte} \approx 2$). -On ne pourra donc pas envisager d'utiliser la décomposition en +On ne pourra donc pas envisager d'utiliser la décomposition en facteurs premiers pour calculer les pgcd. % @@ -246,21 +247,21 @@ facteurs premiers pour calculer les pgcd. Si $n$ est un entier et $p$ un nombre premier, $v_p(n)$ est l'exposant de la plus grande puissance de $p$ qui divise $n$. Si $a/b$ est un -rationnel, on pose $v_p(a/b) = v_p(a)-v_p(b)$ (ne dépend pas de la -représentation $a/b$ choisie). Par convention, $v_p(0) = +\infty$. +rationnel, on pose $v_p(a/b) = v_p(a)-v_p(b)$ (ne dépend pas de la +représentation $a/b$ choisie). Par convention, $v_p(0) = +\infty$. -Quelle est la valuation $2$-adique de $192$ ? $3$-adique ? -$5$-adique ? Quelles sont les valuations $p$-adiques de -$-\frac{24}{11}$, pour tous les $p$ possibles ? +Quelle est la valuation $2$-adique de $192$ ? $3$-adique ? +$5$-adique ? Quelles sont les valuations $p$-adiques de +$-\frac{24}{11}$, pour tous les $p$ possibles ? -Propriétés de $v_p$ : produit (cf. lemme de Gauß) : on a $v_p(xy) = -v_p(x) + v_p(y)$ ; inégalité sur la somme : on a $v_p(x+y) \geq -\min(v_p(x), v_p(y))$ avec égalité si $v_p(x) \neq v_p(y)$. Dire que +Propriétés de $v_p$ : produit (cf. lemme de Gauß) : on a $v_p(xy) = +v_p(x) + v_p(y)$ ; inégalité sur la somme : on a $v_p(x+y) \geq +\min(v_p(x), v_p(y))$ avec égalité si $v_p(x) \neq v_p(y)$. Dire que $x \in \mathbb{Q}$ est entier signifie exactement $v_p(x) \geq 0$ pour -tout $p$. +tout $p$. -Remarque : calculer $v_p(n)$, pour un $n$ donné et un $p$ premier -donné, est facile. Ce qui est difficile dans la décomposition en +Remarque : calculer $v_p(n)$, pour un $n$ donné et un $p$ premier +donné, est facile. Ce qui est difficile dans la décomposition en facteurs premiers, c'est de trouver tous les $p$ tels que $v_p(n) > 0$ (ou en fait, en trouver \emph{un}). @@ -268,88 +269,88 @@ facteurs premiers, c'est de trouver tous les $p$ tels que $v_p(n) > 0$ \subsection{Division euclidienne} Si $a$ est un entier relatif et $b$ un entier naturel \emph{non nul}, -il existe un unique couple $(q,r)$ tel que : +il existe un unique couple $(q,r)$ tel que : \begin{itemize} \item $q$ est un entier relatif, \item $r$ est un entier naturel tel que $0\leq r2$), $\varphi(m)$ est toujours \emph{pair} (sauf pour $m=2$). Si $p$ est premier, alors tous les nombres entre $1$ et $p-1$ sont -premiers avec $p$ : $(\mathbb{Z}/p\mathbb{Z})^\times = \{\bar +premiers avec $p$ : $(\mathbb{Z}/p\mathbb{Z})^\times = \{\bar 1,\ldots, \overline{p-1}\}$ (et notamment $\varphi(p) = p-1$). Tous -les éléments de $\mathbb{Z}/p\mathbb{Z}$ sont inversibles sauf $\bar -0$ : on dit que l'anneau $\mathbb{Z}/p\mathbb{Z}$ est un \emph{corps} -et on le note $\mathbb{F}_p$. +les éléments de $\mathbb{Z}/p\mathbb{Z}$ sont inversibles sauf $\bar +0$ : on dit que l'anneau $\mathbb{Z}/p\mathbb{Z}$ est un \emph{corps} +et on le note $\mathbb{F}_p$. % -\subsection{Théorème chinois} +\subsection{Théorème chinois} Si $m$ et $n$ sont deux naturels non nuls \textbf{premiers entre eux}, -considérons l'application dont les composantes sont les deux -surjections canoniques : +considérons l'application dont les composantes sont les deux +surjections canoniques : \[ \mathbb{Z}/(mn)\mathbb{Z} \to (\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z}) \] Autrement dit, il s'agit de l'application qui envoie un entier $z$ -modulo $mn$ sur sa classe modulo $m$ et sa classe modulo $n$. +modulo $mn$ sur sa classe modulo $m$ et sa classe modulo $n$. Il s'agit d'un \emph{morphisme d'anneaux} (car les surjections -canoniques en sont !) : +canoniques en sont !) : \begin{itemize} \item il est injectif car un entier multiple de $m$ et de $n$ -est multiple de $mn$ (lemme de Gauß), -\item il est surjectif car les cardinaux coïncident ($mn$ au départ et -à l'arrivée), +est multiple de $mn$ (lemme de Gauß), +\item il est surjectif car les cardinaux coïncident ($mn$ au départ et +à l'arrivée), \end{itemize} c'est donc un \textbf{isomorphisme}. @@ -699,17 +700,17 @@ $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z})$... \smallbreak -Concrètement, le théorème chinois signifie : lorsque $m$ et $n$ sont -premiers entre eux, se donner un entier modulo $mn$ revient au même -que se donner cet entier modulo $m$ et modulo $n$ séparément (et, de +Concrètement, le théorème chinois signifie : lorsque $m$ et $n$ sont +premiers entre eux, se donner un entier modulo $mn$ revient au même +que se donner cet entier modulo $m$ et modulo $n$ séparément (et, de plus, toutes les combinaisons d'une classe modulo $m$ et d'une classe -modulo $n$ sont possibles pour une unique classe modulo $mn$). +modulo $n$ sont possibles pour une unique classe modulo $mn$). % -\subsection{Théorème chinois explicite} +\subsection{Théorème chinois explicite} -Si on a une relation de Bézout $um+vn=1$, alors l'isomorphisme chinois -a pour réciproque +Si on a une relation de Bézout $um+vn=1$, alors l'isomorphisme chinois +a pour réciproque \[ \begin{array}{c} (\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z}) \to @@ -718,36 +719,36 @@ a pour r \end{array} \] -(Remarque : dans cette expression, on peut se contenter de calculer -$uy$ modulo $n$ avant de le multiplier par $m$, et de même $vx$ -modulo $m$ avant de le multiplier par $n$, ce qui est parfois plus -efficace que de faire tout le calcul modulo $mn$.) +(Remarque : dans cette expression, on peut se contenter de calculer +$uy$ modulo $n$ avant de le multiplier par $m$, et de même $vx$ +modulo $m$ avant de le multiplier par $n$, ce qui est parfois plus +efficace que de faire tout le calcul modulo $mn$.) -Exemple : trouver le nombre entre $0$ et $100$ congru à $9$ -modulo $11$ et à $3$ modulo $13$. (Relation de Bézout : $6\times 11 - -5 \times 13 = 1$ ; ensuite, $6 \times 11 \times 3 - 5 \times 13 \times +Exemple : trouver le nombre entre $0$ et $100$ congru à $9$ +modulo $11$ et à $3$ modulo $13$. (Relation de Bézout : $6\times 11 - +5 \times 13 = 1$ ; ensuite, $6 \times 11 \times 3 - 5 \times 13 \times 9 \equiv 5\times 11 - 1\times 13 \equiv 42 \pmod{11\times 13}$.) \medskip -Généralisations du théorème chinois : +Généralisations du théorème chinois : \begin{itemize} -\item Si $m$ et $n$ ne sont pas premiers entre eux, toute donnée d'une +\item Si $m$ et $n$ ne sont pas premiers entre eux, toute donnée d'une classe $x$ modulo $m$ et d'une classe $y$ modulo $n$ ne permet pas - forcément de retrouver une classe modulo $mn$ (il faut, et il - suffit, pour cela, que $x$ et $y$ soient « compatibles », - c'est-à-dire congrus modulo $d = \pgcd(m,n)$). Lorsque $x$ et $y$ + forcément de retrouver une classe modulo $mn$ (il faut, et il + suffit, pour cela, que $x$ et $y$ soient « compatibles », + c'est-à-dire congrus modulo $d = \pgcd(m,n)$). Lorsque $x$ et $y$ sont compatibles, alors on retrouve une unique classe modulo $\ppcm(m,n)$ (pour faire le calcul en pratique, diviser les nombres - $m,n$ par $d',d''$ tels que $d'd''=d$ pour se ramener à deux nombres + $m,n$ par $d',d''$ tels que $d'd''=d$ pour se ramener à deux nombres $m/d'$ et $n/d''$ premiers entre eux). -\item Si $m_1,\ldots,m_k$ sont premiers entre eux \emph{deux à deux}, - alors la donnée d'une classe modulo le produit $m_1\cdots m_k$ - équivaut à la donnée de classes modulo chacun des $m_i$ (pour faire +\item Si $m_1,\ldots,m_k$ sont premiers entre eux \emph{deux à deux}, + alors la donnée d'une classe modulo le produit $m_1\cdots m_k$ + équivaut à la donnée de classes modulo chacun des $m_i$ (pour faire le calcul en pratique, on utilise les classes modulo $m_1,m_2$ pour trouver une classe modulo $m_1 m_2$, puis celle-ci et la classe - modulo $m_3$ déterminent une classe modulo $m_1 m_2 m_3$, etc.). -\item En combinant ces deux généralisations : connaissant la classe + modulo $m_3$ déterminent une classe modulo $m_1 m_2 m_3$, etc.). +\item En combinant ces deux généralisations : connaissant la classe d'un entier modulo $m_1,\ldots,m_k$, on peut retrouver sa classe modulo $\ppcm(m_1,\ldots,m_k)$. \end{itemize} @@ -756,785 +757,785 @@ G \subsection{Calcul de l'indicatrice d'Euler} Si $m$ et $n$ (naturels non nuls) sont premiers entre eux, par le -théorème chinois on a $(\mathbb{Z}/(mn)\mathbb{Z})^\times \cong +théorème chinois on a $(\mathbb{Z}/(mn)\mathbb{Z})^\times \cong (\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times$, donc \[ \varphi(mn) = \varphi(m)\,\varphi(n) \] -Si $p$ est premier alors $\varphi(p^r) = (p-1)\,p^{r-1}$ (car être -premier avec $p^r$ équivaut à être premier à $p$, et c'est le cas de -$p-1$ entiers sur $p$). +Si $p$ est premier alors $\varphi(p^r) = (p-1)\,p^{r-1}$ (car être +premier avec $p^r$ équivaut à être premier à $p$, et c'est le cas de +$p-1$ entiers sur $p$). -On en déduit : +On en déduit : \[ \varphi(n) = n\,\prod_{p|n}\left(1-\frac{1}{p}\right) \] -où $p$ parcourt les premiers divisant $n$. +où $p$ parcourt les premiers divisant $n$. -Exemple : $\varphi(63) = \frac{2}{3}\times\frac{6}{7}\times 63 = 36$. +Exemple : $\varphi(63) = \frac{2}{3}\times\frac{6}{7}\times 63 = 36$. -(Intuitivement : parmi les $n$ entiers de $0$ à $n-1$, pour chacun des +(Intuitivement : parmi les $n$ entiers de $0$ à $n-1$, pour chacun des nombres premiers $p$ divisant $n$, il y a une proportion -$\frac{p-1}{p}$ des nombres qui ne sont pas multiples de $p$, et -toutes ces propriétés sont indépendantes --- c'est essentiellement le -théorème chinois --- donc la proportion des nombres qui ne sont -multiples d'aucun des $p$ divisant $n$ est le produit des +$\frac{p-1}{p}$ des nombres qui ne sont pas multiples de $p$, et +toutes ces propriétés sont indépendantes --- c'est essentiellement le +théorème chinois --- donc la proportion des nombres qui ne sont +multiples d'aucun des $p$ divisant $n$ est le produit des $\frac{p-1}{p}$.) -\textbf{Algorithmiquement :} \emph{lent} en général (demande de -connaître la d.f.p.). +\textbf{Algorithmiquement :} \emph{lent} en général (demande de +connaître la d.f.p.). % -\subsection{Notions de théorie des groupes} +\subsection{Notions de théorie des groupes} -Un \textbf{groupe} est un ensemble $G$ muni d'une opération binaire -$\star$ (c'est-à-dire une application $G\times G \to G$ dont on note -$g \star g'$ l'image d'un couple $(g,g')$) et d'un élément remarquable -$e$ tels que : +Un \textbf{groupe} est un ensemble $G$ muni d'une opération binaire +$\star$ (c'est-à-dire une application $G\times G \to G$ dont on note +$g \star g'$ l'image d'un couple $(g,g')$) et d'un élément remarquable +$e$ tels que : \begin{itemize} -\item Associativité de $\star$ : $x\star(y\star z) = (x\star y)\star z$ -\item Neutralité de $e$ pour $\star$ : $e\star x = x\star e = x$ -\item Existence de symétriques : pour chaque $x$, il existe un élément - noté $x'$ tel que) $x \star x' = x' \star x = e$ +\item Associativité de $\star$ : $x\star(y\star z) = (x\star y)\star z$ +\item Neutralité de $e$ pour $\star$ : $e\star x = x\star e = x$ +\item Existence de symétriques : pour chaque $x$, il existe un élément + noté $x'$ tel que) $x \star x' = x' \star x = e$ \end{itemize} Lorsque de plus la loi $\star$ est commutative ($y\star x = x\star -y$), on parle de \emph{groupe abélien} (ou commutatif). +y$), on parle de \emph{groupe abélien} (ou commutatif). -Exemples : l'addition sur les nombres réels (la loi $\star$ étant -l'addition et le neutre $e$ étant le nombre $0$), ou sur les -complexes, ou sur les entiers ; la multiplication sur les nombres -réels non nuls (la loi $\star$ étant la multiplication et le neutre -$e$ étant le nombre $1$), ou sur les réels strictement positifs, ou -sur les complexes non nuls ; la composition des isométries du plan (la -loi $\star$ étant la composition et le neutre $e$ étant l'identité). +Exemples : l'addition sur les nombres réels (la loi $\star$ étant +l'addition et le neutre $e$ étant le nombre $0$), ou sur les +complexes, ou sur les entiers ; la multiplication sur les nombres +réels non nuls (la loi $\star$ étant la multiplication et le neutre +$e$ étant le nombre $1$), ou sur les réels strictement positifs, ou +sur les complexes non nuls ; la composition des isométries du plan (la +loi $\star$ étant la composition et le neutre $e$ étant l'identité). -Contre-exemple : la multiplication sur les entiers (ou même sur les +Contre-exemple : la multiplication sur les entiers (ou même sur les entiers non nuls) \emph{ne forme pas} un groupe, faute d'inverses pour -les entiers autres que $\pm 1$. - -Généralement, un groupe est noté soit de façon multiplicative (on -écrit $xy$ au lieu de $x\star y$ et $1$ au lieu de $e$, et dans ce cas -on note $x^m$ l'élément $x\star x\star \cdots x$ avec $m$ fois $x$ et -$x^{-1}$ le symétrique de $x$, alors appelé « inverse »), soit de -façon additive (on écrit $x+y$ au lieu de $x\star y$ et $0$ au lieu -de $e$, et dans ce cas on note $mx$ l'élément $x + x + + \cdots + x$ -avec $m$ fois $x$, et $-x$ le symétrique de $x$, alors appelé -« opposé »). Très souvent on utilise une de ces deux notations de -façon implicite. La notation additive est en principe réservée aux -groupes abéliens (mais on n'en rencontrera pas de non-abéliens dans ce +les entiers autres que $\pm 1$. + +Généralement, un groupe est noté soit de façon multiplicative (on +écrit $xy$ au lieu de $x\star y$ et $1$ au lieu de $e$, et dans ce cas +on note $x^m$ l'élément $x\star x\star \cdots x$ avec $m$ fois $x$ et +$x^{-1}$ le symétrique de $x$, alors appelé « inverse »), soit de +façon additive (on écrit $x+y$ au lieu de $x\star y$ et $0$ au lieu +de $e$, et dans ce cas on note $mx$ l'élément $x + x + + \cdots + x$ +avec $m$ fois $x$, et $-x$ le symétrique de $x$, alors appelé +« opposé »). Très souvent on utilise une de ces deux notations de +façon implicite. La notation additive est en principe réservée aux +groupes abéliens (mais on n'en rencontrera pas de non-abéliens dans ce cours). \smallbreak Un \textbf{morphisme} de groupe $\psi\colon G \to G'$ est une -application qui préserve la composition ($\psi(x\star y) = \psi(x) -\star \psi(y)$), et du coupb forcément aussi l'élément neutre -($\psi(e) = e$) et les symétriques (le symétrique de $\psi(x)$ est -l'image du symétrique de $x$). Un \textbf{isomorphisme} de groupes -est un morphisme bijectif ; moralement : les groupes $G$ et $G'$ sont -abstraitement « le même » (mais éventuellement notés ou étiquetés -différemment). Attention ! On aura souvent affaire, par exemple, à -un morphisme entre un groupe noté additivement et un groupe noté -multiplicativement : dans ce cas, cela signifie $\psi(x+y) = -\psi(x)\,\psi(y)$. Exemple : l'exponentielle (de base $e$, disons) -constitue un isomorphisme entre le groupe additif des réels et le -groupe multiplicatif des réels non nuls. +application qui préserve la composition ($\psi(x\star y) = \psi(x) +\star \psi(y)$), et du coupb forcément aussi l'élément neutre +($\psi(e) = e$) et les symétriques (le symétrique de $\psi(x)$ est +l'image du symétrique de $x$). Un \textbf{isomorphisme} de groupes +est un morphisme bijectif ; moralement : les groupes $G$ et $G'$ sont +abstraitement « le même » (mais éventuellement notés ou étiquetés +différemment). Attention ! On aura souvent affaire, par exemple, à +un morphisme entre un groupe noté additivement et un groupe noté +multiplicativement : dans ce cas, cela signifie $\psi(x+y) = +\psi(x)\,\psi(y)$. Exemple : l'exponentielle (de base $e$, disons) +constitue un isomorphisme entre le groupe additif des réels et le +groupe multiplicatif des réels non nuls. L'\textbf{ordre d'un groupe} est simplement son cardinal, lorsque -celui-ci est fini. L'\textbf{ordre d'un élément} $g$ dans un groupe +celui-ci est fini. L'\textbf{ordre d'un élément} $g$ dans un groupe fini est le plus petit $m\geq 1$ tel que $g^m = 1$ (en notation -multiplicative ; en notation additive, cela s'écrirait : $mg = 0$, -i.e., un multiple de $g$) ; c'est aussi le nombre de puissances -distinctes (en notation additive : de multiples distincts) de -l'élément $g$. Lorsque $g$ est d'ordre $m$, on a $g^m = 1$ mais aussi -$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$. +multiplicative ; en notation additive, cela s'écrirait : $mg = 0$, +i.e., un multiple de $g$) ; c'est aussi le nombre de puissances +distinctes (en notation additive : de multiples distincts) de +l'élément $g$. Lorsque $g$ est d'ordre $m$, on a $g^m = 1$ mais aussi +$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$. Un \textbf{sous-groupe} $H$ d'un groupe $G$ est un sous-ensemble de -$G$ qui est lui-même un groupe pour la même opération et le même -élément neutre ; c'est-à-dire, c'est une partie $H$ de $G$ telle que +$G$ qui est lui-même un groupe pour la même opération et le même +élément neutre ; c'est-à-dire, c'est une partie $H$ de $G$ telle que $1 \in H$ et que $x,y \in H \limp xy \in H$ et que $x \in H \limp -x^{-1} \in H$ (cette dernière partie étant d'ailleurs automatique si -le groupe $G$ est fini). (Exemple : pour la multiplication, les -nombres réels strictement positifs forment un sous-groupe du groupe -des nombres réels non nuls.) - -Le sous-groupe engendré par une partie $E$ d'un groupe $G$ est le plus -petit sous-groupe contenant $E$ (c'est-à-dire l'intersection de tous -les sous-groupes de $G$ contenant $E$). On utilisera cette notion -seulement dans le cas suivant : le \emph{sous-groupe engendré par un - unique élément} $g$ de $G$ : c'est l'ensemble des puissances de $g$ -(en notation additive : multiples). L'ordre $m$ de ce sous-groupe est -l'ordre de $g$. Ce sous-groupe est isomorphe à +x^{-1} \in H$ (cette dernière partie étant d'ailleurs automatique si +le groupe $G$ est fini). (Exemple : pour la multiplication, les +nombres réels strictement positifs forment un sous-groupe du groupe +des nombres réels non nuls.) + +Le sous-groupe engendré par une partie $E$ d'un groupe $G$ est le plus +petit sous-groupe contenant $E$ (c'est-à-dire l'intersection de tous +les sous-groupes de $G$ contenant $E$). On utilisera cette notion +seulement dans le cas suivant : le \emph{sous-groupe engendré par un + unique élément} $g$ de $G$ : c'est l'ensemble des puissances de $g$ +(en notation additive : multiples). L'ordre $m$ de ce sous-groupe est +l'ordre de $g$. Ce sous-groupe est isomorphe à $\mathbb{Z}/m\mathbb{Z}$, avec $\bar k \mapsto g^k$. \smallbreak -\textbf{Théorème de Lagrange :} Dans un groupe fini, l'ordre de tout +\textbf{Théorème de Lagrange :} Dans un groupe fini, l'ordre de tout sous-groupe divise l'ordre du groupe. En particulier, l'ordre d'un -élément divise l'ordre du groupe : si $G$ est un groupe fini et $g \in +élément divise l'ordre du groupe : si $G$ est un groupe fini et $g \in G$ alors $g^{\#G} = 1$. % \subsection{Groupes cycliques} On dit qu'un groupe fini $G$ est \textbf{cyclique} lorsqu'il existe un -élément $g$ (appelé \emph{générateur} de $G$) tel que tout élément de +élément $g$ (appelé \emph{générateur} de $G$) tel que tout élément de $G$ soit de la forme $g^k$ (une puissance de $g$, en notation -multiplicative ; en notation additive, cela s'écrirait : $kg$, i.e., -un multiple de $g$), autrement dit : le sous-groupe engendré par $g$ -est $G$ tout entier. Ou encore : $G$ est cyclique de générateur $g$ -si et seulement si l'ordre de $g$ est égal à l'ordre de $G$. +multiplicative ; en notation additive, cela s'écrirait : $kg$, i.e., +un multiple de $g$), autrement dit : le sous-groupe engendré par $g$ +est $G$ tout entier. Ou encore : $G$ est cyclique de générateur $g$ +si et seulement si l'ordre de $g$ est égal à l'ordre de $G$. Le groupe \emph{additif} $\mathbb{Z}/m\mathbb{Z}$ est cyclique, avec -pour générateur $1$ (mais ce n'est pas le seul possible ! -cf. ci-dessous). Réciproquement, tout groupe cyclique est isomorphe à -$\mathbb{Z}/m\mathbb{Z}$, avec $m$ l'ordre d'un générateur $g$ (qui -est donc aussi l'ordre du groupe et ne dépend pas du générateur). -D'où une autre définition possible : un groupe cyclique $G$ [de - générateur $g$] est un groupe isomorphe à $\mathbb{Z}/m\mathbb{Z}$ -[avec $1$ correspondant à $g$]. - -Quels sont tous les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme -groupe additif !) ? Réponse : ce sont précisément les classes modulo -$m$ des entiers premiers à $m$, c'est-à-dire les inversibles de -$\mathbb{Z}/m\mathbb{Z}$ (comme anneau !). (Démonstration : si $\bar +pour générateur $1$ (mais ce n'est pas le seul possible ! +cf. ci-dessous). Réciproquement, tout groupe cyclique est isomorphe à +$\mathbb{Z}/m\mathbb{Z}$, avec $m$ l'ordre d'un générateur $g$ (qui +est donc aussi l'ordre du groupe et ne dépend pas du générateur). +D'où une autre définition possible : un groupe cyclique $G$ [de + générateur $g$] est un groupe isomorphe à $\mathbb{Z}/m\mathbb{Z}$ +[avec $1$ correspondant à $g$]. + +Quels sont tous les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme +groupe additif !) ? Réponse : ce sont précisément les classes modulo +$m$ des entiers premiers à $m$, c'est-à-dire les inversibles de +$\mathbb{Z}/m\mathbb{Z}$ (comme anneau !). (Démonstration : si $\bar a$ engendre le groupe additif $\mathbb{Z}/m\mathbb{Z}$, alors en -particulier il doit engendrer $\bar 1$, c'est-à-dire qu'on peut écrire +particulier il doit engendrer $\bar 1$, c'est-à-dire qu'on peut écrire $\bar 1 = \bar a + \bar a + \cdots + \bar a$, avec $u$ fois $\bar a$ disons, donc $\bar a \bar u = \bar 1$ dans l'anneau $\mathbb{Z}/m\mathbb{Z}$, et $\bar a$ y est bien inversible. -Réciproquement, si $\bar a \bar u = \bar 1$, et si $\bar a + \bar a + -\cdots + \bar a = 0$, avec $k$ fois $\bar a$, alors en multipliant par +Réciproquement, si $\bar a \bar u = \bar 1$, et si $\bar a + \bar a + +\cdots + \bar a = 0$, avec $k$ fois $\bar a$, alors en multipliant par $\bar u$ on a $\bar 1 + \bar 1 + \cdots + \bar 1 = 0$, soit $\bar k = -0$, donc $k$ est multiple de $m$ : ceci prouve que l'ordre de $\bar a$ -ne peut pas être plus petit que $m$.) +0$, donc $k$ est multiple de $m$ : ceci prouve que l'ordre de $\bar a$ +ne peut pas être plus petit que $m$.) Ainsi, pour $m$ entier naturel non nul et $a$ entier, il y a -équivalence entre : +équivalence entre : \begin{itemize} \item les entiers $a$ et $m$ sont premiers entre eux, -\item l'élément $\bar a$ a pour ordre (additif) $m$ dans le groupe +\item l'élément $\bar a$ a pour ordre (additif) $m$ dans le groupe $\mathbb{Z}/m\mathbb{Z}$, -\item l'élément $\bar a$ est générateur du groupe +\item l'élément $\bar a$ est générateur du groupe $\mathbb{Z}/m\mathbb{Z}$, -\item l'élément $\bar a$ est inversible dans l'anneau +\item l'élément $\bar a$ est inversible dans l'anneau $\mathbb{Z}/m\mathbb{Z}$, -\item l'élément $\bar a$ appartient au groupe +\item l'élément $\bar a$ appartient au groupe $(\mathbb{Z}/m\mathbb{Z})^\times$ des inversible de l'anneau $\mathbb{Z}/m\mathbb{Z}$. \end{itemize} En particulier, $\mathbb{Z}/m\mathbb{Z}$ admet $\varphi(m)$ -générateurs. Comme un groupe cyclique d'ordre $m$ est la même chose -que (un groupe isomorphe à) $\mathbb{Z}/m\mathbb{Z}$, on en déduit : -le nombre de générateurs de n'import quel groupe cyclique d'ordre $m$ +générateurs. Comme un groupe cyclique d'ordre $m$ est la même chose +que (un groupe isomorphe à) $\mathbb{Z}/m\mathbb{Z}$, on en déduit : +le nombre de générateurs de n'import quel groupe cyclique d'ordre $m$ est $\varphi(m)$. -Attention ! on parlera aussi, plus loin, des générateurs du groupe +Attention ! on parlera aussi, plus loin, des générateurs du groupe \emph{multiplicatif} $(\mathbb{Z}/m\mathbb{Z})^\times$ (et de la -question de savoir s'il y en a). Il ne faut pas confondre ! +question de savoir s'il y en a). Il ne faut pas confondre ! \medbreak -De façon générale, l'ordre additif de $\bar a$ dans +De façon générale, l'ordre additif de $\bar a$ dans $\mathbb{Z}/m\mathbb{Z}$ vaut exactement $m/\pgcd(a,m)$. % -\subsection{Théorème d'Euler} +\subsection{Théorème d'Euler} -Si $m$ est un entier naturel non nul et $a$ un entier premier à $m$, +Si $m$ est un entier naturel non nul et $a$ un entier premier à $m$, alors \[ a^{\varphi(m)} \equiv 1 \pmod{m} \] -Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$ -a un ordre qui d'après Lagrange doit diviser l'ordre du groupe, -i.e. $\varphi(m)$. - -\textbf{Attention !} ne pas confondre l'ordre (« additif ») d'un -élément du groupe additif $\mathbb{Z}/m\mathbb{Z}$ et l'ordre -(« multiplicatif ») d'un élément du groupe multiplicatif -$(\mathbb{Z}/m\mathbb{Z})^\times$. Exemple : quel est l'ordre de $2$ -dans $\mathbb{Z}/7\mathbb{Z}$ ? (réponse : $7$ car $2+2+2+2+2+2+2 = -0$ dans $\mathbb{Z}/7\mathbb{Z}$ et qu'on ne trouve pas $0$ avant) ; -et dans $(\mathbb{Z}/7\mathbb{Z})^\times$ ? (réponse : $3$ car +Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$ +a un ordre qui d'après Lagrange doit diviser l'ordre du groupe, +i.e. $\varphi(m)$. + +\textbf{Attention !} ne pas confondre l'ordre (« additif ») d'un +élément du groupe additif $\mathbb{Z}/m\mathbb{Z}$ et l'ordre +(« multiplicatif ») d'un élément du groupe multiplicatif +$(\mathbb{Z}/m\mathbb{Z})^\times$. Exemple : quel est l'ordre de $2$ +dans $\mathbb{Z}/7\mathbb{Z}$ ? (réponse : $7$ car $2+2+2+2+2+2+2 = +0$ dans $\mathbb{Z}/7\mathbb{Z}$ et qu'on ne trouve pas $0$ avant) ; +et dans $(\mathbb{Z}/7\mathbb{Z})^\times$ ? (réponse : $3$ car $2\times 2\times 2 = 1$ dans $(\mathbb{Z}/7\mathbb{Z})^\times$ et qu'on ne trouve pas $1$ avant). -Pour que l'ordre multiplicatif d'un élément $x$ dans -$\mathbb{Z}/m\mathbb{Z}$ soit défini, il faut (et il suffit) que cet -élément $x$ soit dans $(\mathbb{Z}/m\mathbb{Z})^\times$ (car c'est lui +Pour que l'ordre multiplicatif d'un élément $x$ dans +$\mathbb{Z}/m\mathbb{Z}$ soit défini, il faut (et il suffit) que cet +élément $x$ soit dans $(\mathbb{Z}/m\mathbb{Z})^\times$ (car c'est lui le groupe multiplicatif), et dans ce cas l'ordre additif vaut -forcément $m$ car $x$ est un générateur du groupe cyclique +forcément $m$ car $x$ est un générateur du groupe cyclique $\mathbb{Z}/m\mathbb{Z}$. \smallbreak -Cas particulier du théorème d'Euler : le « petit théorème de - Fermat » : si $p$ est premier, alors $a^{p-1} \equiv 1 \pmod{p}$ -lorsque $a$ n'est pas multiple de $p$ ; donc, pour tout entier $a$ on +Cas particulier du théorème d'Euler : le « petit théorème de + Fermat » : si $p$ est premier, alors $a^{p-1} \equiv 1 \pmod{p}$ +lorsque $a$ n'est pas multiple de $p$ ; donc, pour tout entier $a$ on a \[ a^p \equiv a \pmod{p} \] -Ceci fournit une condition \emph{nécessaire} mais non suffisante pour +Ceci fournit une condition \emph{nécessaire} mais non suffisante pour qu'un nombre soit premier. % -\subsection{Éléments primitifs} +\subsection{Éléments primitifs} Soit $m$ un entier naturel non nul. On dit que $g \in -(\mathbb{Z}/m\mathbb{Z})^\times$ est (un résidu) \textbf{primitif} +(\mathbb{Z}/m\mathbb{Z})^\times$ est (un résidu) \textbf{primitif} (modulo~$m$) lorsqu'il engendre $(\mathbb{Z}/m\mathbb{Z})^\times$ -(comme groupe abélien multiplicatif) --- ce qui entraîne que +(comme groupe abélien multiplicatif) --- ce qui entraîne que $(\mathbb{Z}/m\mathbb{Z})^\times$ est cyclique. -Autrement dit, $g^{\varphi(m)}=1$ est optimal : dire que $g$ est -primitif modulo $m$ signifie que son ordre multiplicatif est +Autrement dit, $g^{\varphi(m)}=1$ est optimal : dire que $g$ est +primitif modulo $m$ signifie que son ordre multiplicatif est exactement $\varphi(m)$ (et pas un autre diviseur de $\varphi(m)$). -Exemple : les puissances de $\bar 2$ modulo $9$ sont : $\bar 2,\bar -4,\bar 8,\bar 7,\bar 5,\bar 1$ ; il y en a bien $\varphi(9)=6$ donc -$2$ est primitif modulo $9$. +Exemple : les puissances de $\bar 2$ modulo $9$ sont : $\bar 2,\bar +4,\bar 8,\bar 7,\bar 5,\bar 1$ ; il y en a bien $\varphi(9)=6$ donc +$2$ est primitif modulo $9$. \smallbreak -\textbf{Attention !} Ne pas confondre : +\textbf{Attention !} Ne pas confondre : \begin{itemize} -\item $\mathbb{Z}/m\mathbb{Z}$ (groupe \emph{additif}, d'élément -neutre $0$) est d'ordre $m$ et est \emph{toujours} cyclique (avec pour -générateurs au moins $1$ et $-1$, et tous les éléments de +\item $\mathbb{Z}/m\mathbb{Z}$ (groupe \emph{additif}, d'élément +neutre $0$) est d'ordre $m$ et est \emph{toujours} cyclique (avec pour +générateurs au moins $1$ et $-1$, et tous les éléments de $(\mathbb{Z}/m\mathbb{Z})^\times$). \item $(\mathbb{Z}/m\mathbb{Z})^\times$ (groupe \emph{multiplicatif}, -d'élément neutre $1$) est d'ordre $\varphi(m)$ et est \emph{parfois} -cyclique (auquel cas ses générateurs s'appellent éléments +d'élément neutre $1$) est d'ordre $\varphi(m)$ et est \emph{parfois} +cyclique (auquel cas ses générateurs s'appellent éléments \emph{primitifs} et il y en a $\varphi(\varphi(m))$). \end{itemize} \medbreak -\textbf{Théorème :} +\textbf{Théorème :} \begin{itemize} \item Si $p$ est un nombre premier impair, alors $(\mathbb{Z}/p\mathbb{Z})^\times$ est cyclique, i.e., il existe des - éléments primitifs modulo $p$. (Il en existe exactement + éléments primitifs modulo $p$. (Il en existe exactement $\varphi(p-1)$.) \item Si $p$ est un nombre premier impair et $r\geq 2$, alors $(\mathbb{Z}/p^r\mathbb{Z})^\times$ est cyclique, i.e., il existe - des éléments primitifs modulo $p^r$. (Il en existe exactement - $\varphi(p^{r-1}(p-1))$.) \emph{Mieux} : $g$ est primitif modulo + des éléments primitifs modulo $p^r$. (Il en existe exactement + $\varphi(p^{r-1}(p-1))$.) \emph{Mieux} : $g$ est primitif modulo $p^r$ si et seulement si il l'est modulo $p^2$. \item Si $p=2$ et $1\leq r\leq 2$, alors $(\mathbb{Z}/2^r\mathbb{Z})^\times$ est trivialement cyclique. \item Si $p=2$ et $r \geq 3$, alors - $(\mathbb{Z}/2^r\mathbb{Z})^\times$ \emph{n'est pas} cyclique : il - est produit d'un groupe cyclique d'ordre $2$ engendré par $-1$ et - d'un groupe cyclique d'ordre $2^{r-2}$ engendré par $5$ (l'ordre - maximal possible d'un élément est $2^{r-2}$). + $(\mathbb{Z}/2^r\mathbb{Z})^\times$ \emph{n'est pas} cyclique : il + est produit d'un groupe cyclique d'ordre $2$ engendré par $-1$ et + d'un groupe cyclique d'ordre $2^{r-2}$ engendré par $5$ (l'ordre + maximal possible d'un élément est $2^{r-2}$). \end{itemize} % -\section{Polynômes} +\section{Polynômes} -\subsection{Définition, structure d'anneau et degré} +\subsection{Définition, structure d'anneau et degré} -Soit $k$ un anneau commutatif quelconque (par exemple : $\mathbb{Z}$), -typiquement un corps (exemples importants : $\mathbb{F}_p = +Soit $k$ un anneau commutatif quelconque (par exemple : $\mathbb{Z}$), +typiquement un corps (exemples importants : $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ ou bien $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$). -Un \textbf{polynôme} en $t$ à coefficients dans $k$ est une somme -formelle $f = a_0 + a_1 t + a_2 t^2 + \cdots$ avec $a_i \in k$ où -\emph{seul un nombre fini} des $a_i$ est non nul (sinon on parle de -\textbf{série formelle}). Autrement dit, on peut écrire $f = a_0 + -a_1 t + \cdots + a_n t^n$ pour un certain $n$ (et si on impose $a_n -\neq 0$, ceci définit $n$, qui s'appellera alors le degré de $f$). +Un \textbf{polynôme} en $t$ à coefficients dans $k$ est une somme +formelle $f = a_0 + a_1 t + a_2 t^2 + \cdots$ avec $a_i \in k$ où +\emph{seul un nombre fini} des $a_i$ est non nul (sinon on parle de +\textbf{série formelle}). Autrement dit, on peut écrire $f = a_0 + +a_1 t + \cdots + a_n t^n$ pour un certain $n$ (et si on impose $a_n +\neq 0$, ceci définit $n$, qui s'appellera alors le degré de $f$). -\textbf{Opérations :} +\textbf{Opérations :} \begin{itemize} -\item Addition : terme à terme ($c_i = a_i+b_i$). -\item Multiplication : « produit de Cauchy » en développant +\item Addition : terme à terme ($c_i = a_i+b_i$). +\item Multiplication : « produit de Cauchy » en développant formellement ($c_i = \sum_{j=0}^{j=i} a_j b_{i-j}$). \end{itemize} Si $k$ est un anneau commutatif, alors $k[t]$ aussi. -\textbf{Degré} d'un polynôme : $\deg f =$ le plus grand $i$ tel que -$a_i \neq 0$ (le degré du polynôme nul est question de convention). -On peut donc écrire un polynôme de degré $\leq N$ comme $a_0 + \cdots -+ a_N t^N$ ; si $a_N = 1$ on dit que $f$ est \textbf{unitaire}. Plus -généralement, le coefficient $a_{\deg f}$ s'appelle \emph{coefficient - dominant} de $f$. +\textbf{Degré} d'un polynôme : $\deg f =$ le plus grand $i$ tel que +$a_i \neq 0$ (le degré du polynôme nul est question de convention). +On peut donc écrire un polynôme de degré $\leq N$ comme $a_0 + \cdots ++ a_N t^N$ ; si $a_N = 1$ on dit que $f$ est \textbf{unitaire}. Plus +généralement, le coefficient $a_{\deg f}$ s'appelle \emph{coefficient + dominant} de $f$. -\textbf{Propriétés} du degré : +\textbf{Propriétés} du degré : \begin{itemize} -\item $\deg (f+g) \leq \max(\deg f, \deg g)$ (avec égalité si $\deg f +\item $\deg (f+g) \leq \max(\deg f, \deg g)$ (avec égalité si $\deg f \neq \deg g$) -\item $\deg (fg) = \deg f + \deg g$ (dès que $k$ est \emph{intègre}, +\item $\deg (fg) = \deg f + \deg g$ (dès que $k$ est \emph{intègre}, en particulier sur un corps) \end{itemize} -Si $k$ est un anneau commutatif intègre, alors $k[t]$ aussi. +Si $k$ est un anneau commutatif intègre, alors $k[t]$ aussi. -Attention, $k[t]$ n'est jamais un corps ! (Car $t$ n'a pas d'inverse +Attention, $k[t]$ n'est jamais un corps ! (Car $t$ n'a pas d'inverse pour la multiplication.) \medbreak -À souligner : \emph{analogie} importante entre les polyômes, notamment -dans $\mathbb{F}_p[t]$, et l'écriture en base $p$ des entiers. -Différence importante : pas de retenue pour les polynômes. +À souligner : \emph{analogie} importante entre les polyômes, notamment +dans $\mathbb{F}_p[t]$, et l'écriture en base $p$ des entiers. +Différence importante : pas de retenue pour les polynômes. -Complexité des opérations : cf. entiers. +Complexité des opérations : cf. entiers. % -\subsection{Opérations spécifiques aux polynômes} +\subsection{Opérations spécifiques aux polynômes} -\textbf{Évaluation} de polynômes : si $f = a_0 + \cdots + a_N t^N$ et -$x$ est dans $k$ ou $k[t]$ (ou plus généralement une « $k$-algèbre »), -on définit $f(x) = a_0 + \cdots + a_N x^N$. +\textbf{Évaluation} de polynômes : si $f = a_0 + \cdots + a_N t^N$ et +$x$ est dans $k$ ou $k[t]$ (ou plus généralement une « $k$-algèbre »), +on définit $f(x) = a_0 + \cdots + a_N x^N$. -Cas particulier : \textbf{composition} : si $g \in k[t]$, on note -$f\circ g$ plutôt que $f(g)$. +Cas particulier : \textbf{composition} : si $g \in k[t]$, on note +$f\circ g$ plutôt que $f(g)$. \medbreak -\textbf{Racines :} si $f(x) = 0$ avec $x \in k$, on dit que $x$ est -une \emph{racine} du polynôme $f$. +\textbf{Racines :} si $f(x) = 0$ avec $x \in k$, on dit que $x$ est +une \emph{racine} du polynôme $f$. -\textbf{Attention :} On peut très bien avoir $f(x) = 0$ pour tout $x +\textbf{Attention :} On peut très bien avoir $f(x) = 0$ pour tout $x \in k$ sans pour autant que $f$ soit nul (e.g., $f = t^p - t$ dans $\mathbb{F}_p[t]$). (Mais on va voir que si $k$ est un corps, le nombre de racines de $f$ -dans $k$ est inférieur ou égal au degré de $f$.) +dans $k$ est inférieur ou égal au degré de $f$.) \medbreak -\textbf{Dérivée :} si $f = a_0 + a_1 t + \cdots + a_N t^N$ alors $f' = +\textbf{Dérivée :} si $f = a_0 + a_1 t + \cdots + a_N t^N$ alors $f' = a_1 + 2 a_2 t + \cdots + N a_N t^{N-1}$. -\textbf{Attention :} On peut avoir $f'=0$ sans avoir $f$ constant +\textbf{Attention :} On peut avoir $f'=0$ sans avoir $f$ constant (e.g., $f = t^p$ dans $\mathbb{F}_p[t]$). -\textbf{Dérivées successives :} $f^{(i+1)} = (f^{(i)})'$ pour $i \in +\textbf{Dérivées successives :} $f^{(i+1)} = (f^{(i)})'$ pour $i \in \mathbb{N}$. % -\subsection{Polynôme interpolateur} +\subsection{Polynôme interpolateur} Dans cette section, soit $k$ un \emph{corps} et $f \in k[t]$. \medskip -\textbf{Fait fondamental :} lorsque deux polynômes de degré $\leq N$ -coïncident en (au moins) $N+1$ points, ils sont égaux ; de façon -équivalente, si un polynôme de degré $\leq N$ s'annule en $\geq N+1$ -points, alors c'est le polynôme nul. +\textbf{Fait fondamental :} lorsque deux polynômes de degré $\leq N$ +coïncident en (au moins) $N+1$ points, ils sont égaux ; de façon +équivalente, si un polynôme de degré $\leq N$ s'annule en $\geq N+1$ +points, alors c'est le polynôme nul. -Réciproquement, si $a_0,\ldots,a_N \in k$ sont deux à deux distincts, +Réciproquement, si $a_0,\ldots,a_N \in k$ sont deux à deux distincts, et $b_0,\ldots,b_N\in k$ sont quelconques, alors \[ \sum_{i=0}^N b_i \frac{\prod_{j\neq i}(t-a_j)}{\prod_{j\neq i}(a_i-a_j)} \] -(\emph{polynôme interpolateur de Lagrange}) est un polynôme de -degré $\leq N$ prenant en $a_i$ la valeur $b_i$. D'après ce qu'on -vient de dire, c'est \emph{le} seul polynôme de degré $\leq N$ prenant -en chaque $a_i$ la valeur $b_i$. +(\emph{polynôme interpolateur de Lagrange}) est un polynôme de +degré $\leq N$ prenant en $a_i$ la valeur $b_i$. D'après ce qu'on +vient de dire, c'est \emph{le} seul polynôme de degré $\leq N$ prenant +en chaque $a_i$ la valeur $b_i$. -Ceci permet de reconstruire un polynôme à partir de ses valeurs en +Ceci permet de reconstruire un polynôme à partir de ses valeurs en suffisamment de points. % -\subsection{Division euclidienne de polynômes} +\subsection{Division euclidienne de polynômes} Sauf mention du contraire, $k$ est maintenant un \textbf{corps}. \smallskip -\textbf{Division euclidienne} analogue à celle des entiers : +\textbf{Division euclidienne} analogue à celle des entiers : Si $f\in k[t]$ et $g\in k[t]$ est \emph{non nul}, -il existe un unique couple $(q,r)$ tel que : +il existe un unique couple $(q,r)$ tel que : \begin{itemize} \item $q \in k[t]$, -\item $r \in k[t]$ est (nul ou) de degré $\deg r < \deg g$ et +\item $r \in k[t]$ est (nul ou) de degré $\deg r < \deg g$ et \item $f = gq + r$. \end{itemize} \medbreak -\textbf{Algorithme « naïf »} de division euclidienne : procéder par -puissances \emph{décroissantes} : +\textbf{Algorithme « naïf »} de division euclidienne : procéder par +puissances \emph{décroissantes} : -Soit $f = a_N t^N + \cdots + a_0$ et $g = b_D t^D + \cdots + b_0$ où -$b_D \neq 0$ (donc $\deg g = D$) : +Soit $f = a_N t^N + \cdots + a_0$ et $g = b_D t^D + \cdots + b_0$ où +$b_D \neq 0$ (donc $\deg g = D$) : \begin{itemize} -\item si $N