summaryrefslogtreecommitdiffstats
path: root/exercices.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2011-10-24 15:39:14 +0200
committerDavid A. Madore <david+git@madore.org>2011-10-24 15:42:06 +0200
commit2c0256cb192f4579ba7ae9c4d57886a5af93c043 (patch)
treee040dbbb928416ead98defa0a531683a509f6788 /exercices.tex
parent78ff1da4ae114bd54763eb0faa054dc7c5be59d8 (diff)
downloadinfmdi720-2c0256cb192f4579ba7ae9c4d57886a5af93c043.zip
infmdi720-2c0256cb192f4579ba7ae9c4d57886a5af93c043.tar.gz
infmdi720-2c0256cb192f4579ba7ae9c4d57886a5af93c043.tar.bz2
Re-encode as utf-8.
Diffstat (limited to 'exercices.tex')
-rw-r--r--exercices.tex276
1 files changed, 139 insertions, 137 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 $300$ et à $169$ modulo $305$.
\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 $6$ dans le tableau ci-dessus : on a $5^6 \equiv
\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 $10$ de $2^{5\,000\,000}$ ?
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}
%