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 +++++++++++++++++++++++++++++----------------------------- 1 file changed, 139 insertions(+), 137 deletions(-) (limited to 'exercices.tex') 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} % -- cgit v1.2.3