Arithmétique

Introduction

Tout le monde, ou presque, a déjà rencontré le chiffre de Jules César, l'empereur romain popularisé dans les bandes dessinées d'Astérix & Obélix. C'est certainement le système de chiffrement le plus simple, le plus connu, et le moins sûr…

Pour transmettre ses messages à ses généraux de manière secrète, Jules César les codait.*(*) on dit chiffrer dans le langage de la cryp­to­gra­phie Il rem­pla­çait chaque lettre du message par celle placée \(k\) positions plus loin dans l'ordre al­pha­bé­ti­que en re­ve­nant au début de l'alphabet si nécessaire.

La figure ci-dessous explicite ce système de chiffrement à l'aide de deux disques concentriques sur lesquels sont inscrites les 26 lettres de l'al­pha­bet dans l'ordre alphabétique et dans le sens horaire. Le disque intérieur contient les lettres en clair et le disque extérieur les lettres chiffrées. Les deux disques sont initialement synchronisés, i.e. les lettres en vis-à-vis sont identiques. Puis on fait tourner le disque extérieur de \(k\) positions dans le sens anti-horaire. Cette représentation est plus pratique qu'une table de cor­res­pon­dan­ce, car changer de décalage \(k=\,\) revient simp­le­ment à faire une rotation du disque extérieur pour obtenir la nou­vel­le cor­res­pon­dan­ce.

Chiffrement de César pour un décalage de \(k=\,\). La lettre A est chiffrée en .

Saisissez votre message en clair dans la boite ci-dessous et validez une fois terminé (vous pouvez également modifier la clef de chiffrement \(k\) dans la boite de saisie plus haut).

Message clair :
Message chiffré :

Le déchiffrement du message est aussi simple, il suffit de faire tourner le disque extérieur de \(k\) po­si­tions dans le sens horaire à partir de deux disques synchrones.

Soit \(k\in\N\). Démontrez que le chiffrement de César avec un décalage circulaire de \(\def\alphabet{{\mathscr A}}k\) lettres est une bi­jec­tion \(e_k:\alphabet\rightarrow\alphabet\) où \(\alphabet\) est l'alphabet latin \({\alphabet}:=\{A,B,C,\ldots,Y,Z\}.\) Si on munit \({\alphabet}\) de l'ordre alphabétique, l'application \(e_k\) est-elle un morphisme d'ensembles or­don­nés ?
Le message chiffré suivant a été obtenu à l'aide du chiffrement de César. Déchiffrez le en trou­vant la clé secrète \(k\) :
OAYNUQZPQFQZFMFUHQEMHQLHAGERMUFQEBAGDFDAGHQDW

La quantité secrète que seul César et ses généraux connaissaient est bien sûr le décalage \(k\) utilisé, il constitue la clef secrète. Un tel système est appelé chiffrement à clé secrète. Il est évident que le chif­fre­ment de César n'est pas sûr dès que le texte chiffré comporte quelques lettres (il est en revanche inviolable si le message ne contient qu'une seule lettre). Même si elle est fastidieuse, sa cryptanalyse*(*) Tech­ni­ques mises en œuvre pour dé­chif­frer un mes­sa­ge dont on ne con­naît pas la clef. peut se faire à la main, en tentant les différents décalages \(k\) possibles. On peut faire mieux en cherchant la lettre la plus fréquente du message chiffré et supposer qu'il s'agit du chiffré de la lettre \(E\). En effet, la lettre \(E\) est la plus fréquente (de la langue française) et les chiffrés ont la même fréquence d'apparition que les clairs puisqu'il s'agit d'une bijection. Une fois cette lettre trouvée, la clef \(k\) est la distance qui sépare \(E\) de cette lettre.

Aujourd'hui les systèmes de chiffrement à clef secrète utilisés sont bien plus robustes et bien plus complexes à cryptanalyser. Néanmoins tous ont le même défaut, il faut partager la clef secrète avec les destinataires légitimes avant de leur transmettre des messages chiffrés. Si la transmission manuelle des clés était de mise à l'époque de Jules César, la dématérialisation des données et les transmissions électroniques d'aujourd'hui s'accomodent mal de méthodes aussi rudimentaires. Il faut donc disposer d'un canal de transmission sécurisé pour transmettre les clés, mais dans ce cas pourquoi ne pas transmettre le message en clair via ce canal puisqu'il est sûr ?

Il faut alors trouver un moyen de transmettre des clefs secrètes sur un canal non sécurisé. Cela peut semb­ler impossible, et pourtant ce problème a été résolu à la fin des années 1970. L'un des premiers protocoles de chiffrement à clé publique proposé fut rsa, acronyme de ses concepteurs, Ronald Rivest, Adi Shamir et Leonard Adleman. Il est toujours utilisé intensivement aujourd'hui. L'objectif de ce chapitre est de comprendre comment ces chercheurs ont pu réaliser ce tour de force. Pour cela, il faut connaître quelques résultats élémentaires (mais rarement triviaux) en ari­thmé­ti­que. L'ari­thmé­ti­que est la branche des mathématiques qui étudie les propriétés des nombres ra­tion­nels. Ces propriétés sont principalement liées aux interactions entre les deux lois de composition internes, l'addition et la multiplication ainsi que la relation d'ordre naturel sur l'ensemble \(\Z\).

Les groupes quotients de \({\mathbb Z}\)

Nous reprenons l'étude des groupes entamée au chapitre Groupes à travers un cas particulier fondamental, le groupe additif \((\Z,+)\).

Divisibilité, nombres premiers

Nous avons défini la relation de divisibilité sur l'ensemble des entiers naturels \(\N\), cette relation s'étend à l'ensemble des entiers relatifs.

Soit \((a,b)\in\Z^2\). On dit que \(a\) divise \(b\) ou que \(a\) est un diviseur de \(b\) ou en­co­re que \(b\) est un multiple de \(a\), ce que l'on note \(a\mid b\) si et seulement si \begin{equation} \label{eq:divisibilité} \exists c\in {\Z}\ \ ac=b. \end{equation}

Par exemple, \(3\mid15\) et \(5\mid15\). Cette relation binaire est réflexive, en effet \(a.1=a\). Elle est également transitive puisque si \(a\mid b\), il existe \(x\in\Z\) tel que \({\color{#FF8}ak}={\color{#FF8}b}\) et si \({\color{#FF8}b}\mid c\), il existe \(l\in\Z\) tel que \({\color{#FF8}b}l=c\), donc \(({\color{#FF8}ak})l=a(kl)=c\) soit \(a\mid c.\) On qualifie parfois une telle relation de préordre. En revanche elle n'est pas symétrique puisque \(2\mid 4\) mais \(4\not\mid 2\), donc ce n'est pas une relation d'équivalence sur \(\Z\). Ce n'est pas non plus une relation d'ordre sur \(\Z\), con­trai­re­ment à la di­vi­si­bi­li­té dans \(\N\). La divisibilité dans \(\Z\) n'est pas antisymétrique, en effet, pour tout entier naturel \(n\not = 0\), \(n\mid(-n)\) et \((-n)\mid n\) et pourtant \(n\not = (-n)\).

Déterminez les entiers naturels \(n\) tels que \(n\mid n+8\).
Soit \(n\in\N\) tel que \(n\mid n+8\). Par définition de la relation de divisibilité, il existe un entier naturel \(k\) tel que \(kn=n+8\), autrement dit tel que \(n(k-1)=8\) donc \(n\mid 8\). Il existe \(4\) diviseurs de \(8\), les entiers \(1\), \(2\), \(4\) et \(8\).
Démontrez les assertions suivantes :
  1. \(\forall(a,b,c)\in\Z^3\quad a\mid b\ \Rightarrow\ a\mid bc\),
  2. \(\forall(a,b,c)\in\Z^3\quad (a\mid b)\ \text{et}\ (a\mid c)\ \Rightarrow a\mid (b+c)\),
  3. \(\forall(a,a',b,b')\in\Z^4\quad (a\mid a')\ \text{et}\ (b\mid b')\ \Rightarrow ab\mid a'b'\),
  4. \(\forall(a,b)\in\Z^2\ \forall n\in\N\quad a\mid b\ \Rightarrow\ a^n\mid b^n\).

On définit la valeur absolue d'un entier relatif \(k\), que l'on note \(\def\abs#1{{|\,#1\,|}}\abs{k}\), comme le maximum de l'en­semb­le \(\{-k,k\}\) pour la relation d'ordre naturel définie sur \(\Z\) par \(x\leq y\Leftrightarrow y-x\in\N\).

Le théorème qui suit est central en ari­thmé­ti­que. Il est très intuitif puisqu'il s'agit de partager \(a\) bonbons entre \(b\) amis. C'est un résultat très profond utilisé au sein de nombreuses démonstrations.

Soit \(a\) et \(b\) deux entiers relatifs tels que \(b\not=0\). Alors, il existe un unique couple \((q,r)\in\Z\times\N\) tel que \begin{equation} \label{eq:diveuclidienne} a=bq+r\quad\text{et}\quad 0\leq r < \abs{b}. \end{equation} Les entiers \(q\) et \(r\) sont appelés respectivement le quotient et le reste de la division euc­li­dien­ne de \(a\) par \(b\).
Si \(a=0\), le couple \((q,r):=(0,0)\) convient. On suppose donc que \(a\not=0\). Si \(b > 0\), la partie \(\{n\in\Z\mid nb > a\}\) de \(\Z\) n'est pas vide car \(\Z\) est archimédien et elle est minorée par \(-\abs{a}\) car \(-\abs{a}b\leq a\). Elle admet donc un plus petit élément \(p\) et dans ce cas le couple \((q,r):=(p-1,a-b(p-1))\) est solution de \((\ref{eq:diveuclidienne}).\) Si \(b < 0\), le couple \((a,b')\) avec \(b':=-b\) admet un couple \((q,r)\) qui satisfait \((\ref{eq:diveuclidienne})\) d'après l'étude que nous venons de mener. Dans ce cas \((-q,r)\) convient pour le couple \((a,b)\).

Il reste à montrer l'unicité. Supposons que \((a,b)\) admettent deux couples \((q,r)\) et \((q',r')\) qui satisfont \((\ref{eq:diveuclidienne})\), soit \begin{align*} a&=bq+r& 0&\leq r < \abs{b},\\ \text{et}\quad a&=bq'+r'& 0&\leq r' < \abs{b},\\ \text{d'où}\ \ {\color{#88F}r'-r}&=b(q-q') & -\abs{b} &< {\color{#88F}r' -r} < \abs{b}. \end{align*} On en déduit que \(-\abs{b} < b(q-q') < \abs{b}\) et donc en prenant la valeur absolue que \(0\leq \abs{b}\abs{q-q'} < \abs {b}\). Comme \(b\not=0\) on en tire que \(0\leq\abs{q-q'} < 1\) et on conclut avec \(\abs{q-q'}=0\) d'où \(q=q'\) impliquant \(r=r'\).
Attention, si l'on applique le théorème au couple \((a,b):=(8,3)\) on obtient le quotient \(q=2\) et le reste \(r=2\), mais pour le couple \((a,b):=(-8,3)\) on a le quotient \(q=-3\) et le reste \(r=1\).
Déterminez les entiers naturels \(n\) tels que leur division euclidienne par \(3\) donne un quotient égal au double du reste.
Soit \(n\in\N\). Le théorème de la division euclidienne nous fournit un couple \((q,r)\) tel que \(n=3q+r\) et \(0\leq r < 3\) et l'hypothèse de l'énoncé \(q=2r\). On en déduit que \(n=7r\) avec \(3\) restes possibles \(r\in\{0,1,2\}\), soit les trois solutions \(n\in\{0,7,14\}\).
Quel(s) est/sont le(s) entier(s) naturel(s) \(n\) tels que les quotients de la division euc­li­dien­ne de \(n\) par \(65\) et par \(79\) sont identiques et les restes respectifs sont \(63\) et \(7\) ?
On réalise deux divisions euclidiennes de l'entier naturel \(n\), la première par \(65\) et la seconde par \(79\), avec pour quotients le même entier \(q\) et les restes fournis par l'énoncé : \begin{align*} n&=65q+63\\ n&=79q+7\\ \end{align*} Par transitivité de l'égalité, on en déduit que \(65q+63=79q+7\) soit \(14q=56\) et donc \(q=4\). Finalement \(n=323\).
La somme des âges (non-nuls) de trois frères est égal à \(39\), l'ainé a deux fois l'âge du benjamin (le plus jeune donc). Quel est l'âge des trois frères ? Indication : ne pas faire une étude de cas, mais utiliser la division euc­li­dien­ne en remarquant que l'âge du cadet est égal à \(C+r\) si \(q\) désigne l'âge du cadet.
On peut modéliser aisément le problème avec trois entiers naturels \(A\), \(B\) et \(C\) codant l'âge de l'aîné, du benjamin et du cadet respectivement. Ces entiers doivent donc satisfaire le système d'équations et d'inéquation suivant : \begin{align*} A+B+C&=39\\ A&=2B\\ B\leq C & < A \end{align*} Notons que nous avons interprété l'énoncé conformément à l'acception du français, puisque l'énoncé utilise l'article défini singulier le pour parler de l'aîné, ceci sous-entend que \(A > B\), mais aurait mérité une précision afin de lever toute ambiguïté. De la même manière, on est le cadet de quelqu'un (c'est une notion relative), autrement dit on peut être à la fois le cadet et le benjamin, d'où \(B\leq C\) plutôt que \(B < C\), mais là encore le sujet aurait mérité une précision.

En remplaçant \(A\) par \(2B\) dans la première égalité, on obtient \begin{equation} \label{eq:troisf} 3B+C=39. \end{equation} La première démarche qui vient à l'esprit est de faire un étude de cas mais il faut réaliser que si les valeurs numériques étaient plus grandes l'étude de cas par cette voie serait très fastidieuse. Si l'on fait la division euclidienne de \(C\) par \(B\), i.e. \(C=q.B+r\), on a nécessairement \(q=1\) et \(r > 0\). En effet si \(q\geq 2\) alors l'inégalité stricte \(C < A\) n'est plus satisfaite et d'autre part si \(r=0\) alors \(C=B\) et la première équation donne \(4B=39\) or \(39\) n'est pas divisible par \(4\). On remplace dans \((\ref{eq:troisf})\) pour obtenir \begin{equation} \label{eq:troisff} 39=4B+r. \end{equation} Cette dernière égalité invite à considérer la division euclidienne de \(39\) par \(4\) et de voir \(B\) comme le quotient et \(r\) comme le reste. Dans ce cas le théorème de la division euclidienne nous donne une solution unique \(B=9\) et \(r=3\) (puisque \(0\leq r=3 < 4\)). Cependant, ce n'est pas l'unique solution au problème (ce qui n'a rien de contradictoire avec l'unicité de la solution fournie par le théorème de la division euclidienne que nous venons de considérer). Si l'on considère la division euclidienne de \(39\) par \(B\), alors c'est \(4\) qui est le quotient et tous les couples \((B,r)\) qui satisfont \((\ref{eq:troisff})\) et \(0\leq r < B\) conviennent d'après le théorème de la division euclidienne. On sait que \(0 < r < B\), on en déduit les inégalités \begin{equation*} 5B > 39 > 4B. \end{equation*} et donc \(B\) est compris entre le quotient de la division euclidienne de \(39\) par \(4\) et le quotient de la division euclidienne de \(39\) par \(5\), c'est-à-dire \(8 \leq B \leq 9\) et on obtient finalement les deux triplets \((A,B,C)\) solutions du problème : \((16,15,8)\) et \((18,12,9)\).

Revenons sur les entiers naturels et par­ti­cu­liè­re­ment sur les nombres premiers. Sont-ils nombreux ? Comment les calculer ?

L'ensemble des nombres premiers est dénombrable.
Montrons le par l'absurde. Supposons qu'il existe un nombre fini \(n\) de nombres premiers et notons les \(p_1,p_2,\ldots,p_n\). On calcule : \begin{equation} p:=1+\prod_{i=1}^np_i. \end{equation} Pour tout \(i\in\llbracket 1,\,n\rrbracket \), le reste de la division euclidienne de \(p\) par \(p_i\) est égal à \(1\), autrement dit \(\forall i\in\llbracket 1,\,n\rrbracket \ p_i\not\mid p\), donc \(p\) est un nombre premier différent de tous les \(p_i\) ce qui est absurde.

Pour trouver des nombres premiers, Eratosthène*(*) Eratosthène était un savant grec, à la fois mathématicien, géo­gra­phe, ast­ro­no­me et poète et qui di­ri­geait la gran­de bi­blio­thè­que d'Ale­xan­drie deux siècles et demi avant jc. Il avait, entre autres, estimé la cir­con­fé­ren­ce de la Ter­re. a proposé une méthode simple et élégante qui porte aujourd'hui son nom, le crible d'Eratosthène. Le principe est le suivant. On se donne un entier \(N > 1\) arbitraire et on constitue initialement la liste de tous les entiers compris entre \(1\) et \(N\). L'al­go­ri­thme va éliminer (cribler) tous les nombres de cette liste qui ne sont pas premiers. On ini­tia­li­se le processus en criblant le nombre 1 car il n'est pas premier. On cherche ensuite le prochain nombre \(p\) de la liste qui n'est pas criblé, à savoir 2 et on crible tous ses multiples \(kp\) pour \(k > 1\). On re­com­men­ce en cherchant le prochain nombre \(p\) qui n'est pas criblé dans la liste, c'est-à-dire 3, et on crible ses multiples \(kp\) pour \(k > 1\), etc. jusqu'à ce que \(p^2 > N\) :

Crible(N)
ENTRÉE: un entier naturel N
SORTIE: une liste de booléens EstPremier[1:N] telle que
        (EstPremier[p]) ⇔ (p premier)

EstPremier[1:N] ← N*[VRAI]
EstPremier[1] ← FAUX
p ← 1
TANT QUE (p2 ≤ N):
   p ← p + 1
   TANT QUE (p2 ≤ N) ET (NON EstPremier[p]):
      p ← p + 1
   k ← 2
   TANT QUE (k*p ≤ N):
      EstPremier[k*p] ← FAUX
      k ← k + 1
RENVOYER EstPremier

Voici l'illustration de cet algorithme qui calque la méthode manuelle employée par Eratosthène en biffant les valeurs entières dans une table. Saisissez la valeur*(*) \(10 \leq N\leq 200.\) de l'entier \(N:=\).

Crible d'Eratosthène pour la valeur \(N=\) .

Les nombres premiers qui apparaissent en jaune à la fin du crible sont les nombres premiers \({\color{#FF8}p}\) utilisés dans la boucle qui crible leurs multiples (instructions #13 à #15).

Soit \(n\) un entier naturel non-nul. Démontrez que pour trouver tous les diviseurs \(d\) de \(n\), on peut se contenter de tester les valeurs de l'intervalle \(\ab{2}{\lceil\sqrt{n}\rceil}\) dans l'ordre croissant. Démontrez qu'à la sortie de la boucle TANT QUE (p2 ≤ N), le nombre \(p\) est un nombre premier.

Soit (\(k_i)_{i\in\llbracket 1,\,\ell\rrbracket }\) une séquence croissante d'entiers naturels (i.e. l'application \(k:\llbracket 1,\,\ell\rrbracket \rg\N\) définie par \(i\mapsto k_i\) est croissante). Si l'on peut écrire un entier naturel \(n\) sous la forme du produit

\begin{align*} n=\prod_{i=1}^{\ell}k_i, \end{align*}

alors on dit que \((k_i)_{i\in\llbracket 1,\,\ell\rrbracket }\) est une décomposition en produit de facteurs croissants de \(n\). Une telle décomposition existe toujours puisque la séquence constitué dU seul entier \(n\) fait l'affaire. Un entier naturel peut admettre plusieurs décompositions en produit de facteurs croissants :

\begin{align*} 18&=18,\\ &=3\times 6,\\ &=2\times3\times 3,\\ &=2\times 9. \end{align*} En revanche, si l'on suppose que la séquence n'est constituée que de nombres premiers, on a à la fois l'existence et l'unicité.
Tout entier naturel \(n\geq 2\) se dé­com­po­se de ma­niè­re unique en produit de facteurs premiers croissants.
Si \(n\) est un nombre premier, il est sa propre décomposition, supposons donc que \(n\) ne soit pas un nombre premier. Dans ce cas l'ensemble \(\{d\in\, ]1,n[\ \mid\ d\mid n\}\) des diviseurs stricts de \(n\) est une partie non-vide de \(\N\), elle admet donc un plus petit élément \(p\) d'après la première propriété d'un ensemble naturel. Cet entier \(p\) est nécessairement premier sans quoi on pourrait écrire \(p=ab\) avec \(1 < a < p\) or si \(p\mid n\) nécessairement \(a\mid n\), ce qui contredit que \(p\) est le plus petit diviseur de \(n\). Notons ce nombre premier \(p_1\). On peut donc écrire \(n=p_1n_1\) avec \(n_1 < n\). On recommence le même raisonnement avec \(n_1\), et on obtient par récurrence une suite d'entiers naturels non-nuls strictement dé­crois­san­te qui est nécessairement finie, d'où le résultat sur la décomposition.

Montrons l'unicité de cette décomposition. Supposons qu'il existe des entiers admettant plusieurs dé­com­po­si­tions en produits de facteurs premiers croissants et soit \(n\) le plus petit d'entre eux. On peut donc écrire \begin{equation*} n=\prod_{i=1}^kp_i\quad\text{et}\quad n=\prod_{i=1}^{\ell}q_i. \end{equation*} Montrons dans un premier temps que \(\forall (i,j)\in\llbracket 1,\,k\rrbracket \times\ab{1}{\ell}\), \(p_i\not=q_j\). Par l'absurde, s'il existe \((i,j)\) tel que \(p_i=q_j\), alors l'entier \(n/p_i=n/q_j\), qui est strictement inférieur à \(n\), admettrait lui aussi deux dé­com­po­si­tions distinctes, ce qui est absurde puisque \(n\) est le plus petit.

Dans un second temps, \(k\geq 2\) et \(\ell\geq 2\) donc \(n \geq p_1^2\) et \(n \geq q_1^2\) or \(p_1\not=q_1\) donc \(n > p_1q_1\). Mais \(p_1\mid n\) et \(q_1|n\) donc \(p_1q_1\mid n\) autrement dit \(q_1\) divise l'entier \(\frac{n}{p_1}\) dont la décomposition est \(p_2p_3\ldots p_k\) donc \(q_1\) est égal à l'un des nombres premiers \(p_i\), ce qui est contradictoire.

L'algorithme naïf qui permet de décomposer un nombre entier \(n\) de taille raisonnable en produit de facteurs premiers croissants consiste à diviser \(n\) par tous les nombres premiers qui sont inférieurs à sa racine carrée (cf. exercice). Il faut pour cela disposer de la liste de ces nombres premiers. Pour construire cette liste, le crible d'Eratosthène est suffisant. Si vous avez correctement programmé ce crible, vous pourrez vérifier qu'il y a 168 nombres premiers inférieurs à \(1.000\) et que le plus grand est \(997\). Son carré vaut \(994\,009\), c'est la borne*(*) Si vous saisis­sez une valeur plus grande, elle se­ra réduite modulo ce nom­bre. que nous nous sommes fixée ici : la décomposition en produit de facteurs premiers croissants de l'entier \(n=\;\) est :

Attention, la rapidité avec laquelle notre script réalise la décomposition de l'entier \(N\) n'est qu'ap­pa­ren­te. Nous verrons dans le cours d'Algorithmique que cet algorithme est inef­fi­ca­ce.

On note \((p_i)_{i\in\N^*}\) la suite croissante des nombres premiers, i.e. \(p_1=2\), \(p_2=3\), etc. Soit \(n\in\N\) et \(n\geq 1\). On définit \(\rho_n:=1+\prod_{i=1}^np_i\). Quelle est la plus petite valeur de \(n\) telle que \(\rho_n\) n'est pas un nombre premier ? Quel est la décomposition en produit de facteurs premiers de \(\rho_n\) ?

Nous arrêterons là nos investigations sur les nombres premiers pour la pre­miè­re année mais une multitude d'autres questions se posent. Par exemple, comment sont-ils répartis ? Peut-on les calculer avec une formule ? Est-il facile de déterminer si un nombre est premier ?

Congruences

Soit \(n\in\N\). Dans la suite, on note \(n\Z\) l'ensemble des multiples de \(n\) défini par \begin{equation} n\Z:=\{nz\mid z\in\Z\}. \end{equation}

Le groupe \((\Z,+)\) admet pour seuls sous-groupes ceux constitués par les ensembles \(n\Z\) pour tout entier naturel \(n\).
D'après le théorème de caractérisation des sous-groupes, \((n\Z,+)\) est un sous-groupe de \((\Z,+)\) si et seulement si\(n\Z\) est stable pour l'addition, \(0\in n\Z\) et que pour tout élément \(k\) de \(n\Z\) sont opposé \(-k\) appartient lui aussi à \(n\Z\). L'addition de deux multiples de \(n\) est un multiple de \(n\), \(n\Z\) est donc une partie stable pour l'addition. L'entier \(0\in n\Z\), puisque \(0=n.0\) et si \(k\in n\Z\), alors il existe \(z\in\Z\) tel que \(k=nz\), par conséquent \((-k)=n(-z)\), ce qui montre que \((-k)\in n\Z\).

La réciproque est plus délicate. Il faut montrer que tout sous-groupe de \((\Z,+)\) est de la forme \(n\Z\). Soit \(H\) un sous-groupe de \(\Z\). S'il est réduit à \(H=\{0\}\), alors \(H=0\Z\), sinon il contient au moins un élément non-nul et son opposé, donc au moins un entier strictement positif. L'ensemble \(H\cap\N^*\) est donc une partie non-vide de \(\N\) et admet alors un plus petit élément \(n\) (cf. première propriété d'un ensemble naturel). Comme \(\{n\}\subseteq H\), le sous-groupe de \(\Z\) engendré par \(n\), c'est-à-dire \(n\Z\) vérifie \(n\Z\subseteq H\). Il reste à montrer que \(H\subseteq n\Z\). Soit \(x\in H\), le théorème de la division euclidienne nous donne \(x=qn+r\) avec \(q\in\Z\) et \(0\leq r < n.\) Comme \(x\in H\) et \(-qn\in H\), on déduit \(r\in H\), mais \(n\) est le plus petit entier non-nul de \(H\) et \(r < n\), donc \(r=0\) et finalement \(x\in n\Z.\)

Soit \(n\in\N\). Démontrez que \(n\Z\) est un ensemble au plus dénombrable.

Rappelons que les relations d'équivalence compatibles avec une loi de composition interne sur un groupe \((G,+)\) sont nécessairement de la forme \(y-x\in H\) où \(H\) est un sous-groupe normal de \(G\) (cf. théorème).*(*) La loi de groupe est ici notée ad­di­ti­ve­ment, le sy­mé­tri­que est donc no­té com­me un op­po­sé \(-x\) au lieu d'un in­ver­se \(x^{-1}\). Deux entiers relatifs \(x\) et \(y\) sont dit congrus modulo \(n\) si leur différence est un multiple de \(n,\) ce que l'on note \(x\equiv y\pmod n.\)

Soit \(n\in\N\). La relation de congruence modulo n définie sur \(\Z\) par \begin{equation} \label{eq:congruence} x\equiv y\!\!\pmod n\ \Leftrightarrow\ y-x\in n\Z \end{equation} est une relation d'équivalence compatible avec l'addition dans \(\Z\).
En effet le groupe \((\Z,+)\) est un groupe commutatif, donc tous ses sous-groupes \(n\Z\) sont normaux.

On peut donc quotienter le groupe \((\Z,+)\) par \(n\Z\), le quotient \((\Z/n\Z,+)\) héritant de la loi quotient additive de \(\Z\). Notons que si deux entiers relatifs \(x\) et \(y\) sont congrus modulo \(n\), on écrit \(x\equiv y\pmod n\) alors que si ce sont deux éléments de \(\Z/n\Z\) qui sont congrus modulo \(n\) alors \(x=y\).

Soit \(n\in\N\). Le groupe quotient \((\Z/n\Z,+)\) est appelé groupe des en­tiers relatifs modulo n.
Le premier janvier 2000 était un samedi. Quel jour de la semaine était le 275-ème jour de l'année 2000 ?
Le compas d'un bateau à la dérive tourne de \(7°\) dans le sens horaire toutes les 8 minutes. Quelle direction indique le compas après 3 jours, 2 heures et 32 minutes si la direction initiale était de 23° ?
Soit \(n\in\N\). Si \(n > 0\), le groupe quotient \((\Z/n\Z,+)\) est un groupe cyclique d'ordre \(n\). Si \(n=0\), c'est un groupe monogène isomorphe à \(\Z\).
Soit \(\varphi_n:\Z\rightarrow\Z/n\Z\) la surjection canonique. On a \[\forall k\in\Z\quad \varphi_n(k)=k\varphi_n(1),\] ceci prouve que \(\varphi_n(1)\) est un générateur de \((\Z/n\Z,+)\) qui est donc un groupe monogène. Si \(n=0\), la relation d'équivalence \((\ref{eq:congruence})\) est tout simplement l'égalité, donc \(\Z/0\Z\) est isomorphe à \(\Z\). Sinon tout élément \(X\in\Z/n\Z\) est l'image par \(\varphi_n\) d'un unique élément de l'ensemble \(\{0,1,2,\ldots,n-1\}\), c'est le reste commun à toutes les divisions euclidiennes par \(n\) des entiers de la classe \(X\). La restriction de \(\varphi_n\) à \(\{0,1,2,\ldots,n-1\}\) est donc une bijection et \(\Z/n\Z\) a donc pour cardinal \(n\).
Les générateurs du groupe \((\Z/n\Z,+)\) pour \(n\geq 1\), sont les classes des entiers \(k\) modulo \(n\) tels que \(1 \leq k < n\) avec \(k\) et \(n\) premiers entre eux.
Si \(g\) est un générateur du groupe additif \((\Z/n\Z,+)\), tous les éléments du groupe sont des multiples de \(g\) donc \(1\) en particulier. Il existe alors un entier \(k\) tel que \(k.g=1\) ce qui prouve que \(g\) est inversible. Réciproquement, si \(g\) est un élément inversible de \(\Z/n\Z\), alors pour tout \(x\in\Z/n\Z\), l'entier \(k:=xg^{-1}\) satisfait \(kg=x\) ce qui prouve que \(g\) est un générateur du groupe additif \((\Z/n\Z,+)\).

D'après la preuve du théorème précédent, les éléments de \(\Z/n\Z\) sont donc les images \(\overline{k}=\varphi_n(k)\) des \(n\) pre­miers entiers naturels. Souvent par abus de langage, on écrira que \(\Z/n\Z=\{0,1,2,\ldots,n-1\}\) en omettant la barre sur chaque entier qui signifie qu'il s'agit d'une classe d'équivalence. Cette confusion est sans danger précisément parce que la relation de congruence est compatible avec l'ad­di­tion. Autrement dit, quand on additionne deux classes d'équivalence pour la loi additive quotient, il suffit d'additionner les entiers correspondants et de calculer si nécessaire le reste de la division euclidienne par \(n\) pour retrouver un représentant dans l'ensemble \(\{0,1,2,\ldots,n-1\}\).

On construit aisément la table d'addition du groupe cyclique \(\Z/n\Z\). Pour \(n=\,\) on obtient la table suivante (les générateurs du groupe sont distingués en jaune) :

Table d'addition du groupe \(\Z/\)\(\Z\). Ses générateurs sont en jaune.

Ainsi dans \(\Z/6\Z\), pour calculer \(\overline{4}+\overline{5}\), il suffit d'additionner \(4+5=9\) et de calculer le reste de la division euclidienne de \(9\) par \(6\) pour obtenir \(3\).

Le théorème suivant est très important, il dit en substance que les seuls groupes monogènes sont les groupes \(\Z\) ou \(\Z/n\Z\).

Tout groupe monogène \(G\) est commutatif. S'il est infini, il est isomorphe à \((\Z,+)\), s'il est fini de cardinal \(n\), il est isomorphe à \((\Z/n\Z,+)\) et donc cyclique.
Soit \(a\) un générateur de \(G\) (on note le groupe multiplicativement). Donc tout élément de \(g\) est de la forme \(a^p\) avec \(p\in\Z\). Comme \(a^{p+q}=a^pa^q\), l'application \(f:\Z\rightarrow G\) définie par \(p\mapsto a^p\) est un morphisme surjectif de groupes. Le groupe \(G\) est donc isomorphe au quotient \(\Z/\text{Ker}(f)\) or \(\text{Ker}(f)\) est un sous-groupe de \(\Z\) donc nécessairement de la forme \(k\Z\).

Si \(G\) est infini, \(\Z/\text{Ker}(f)\) est infini, ce qui entraîne que \(k=0\) et assure l'injectivité de \(f\) qui est donc un isomorphisme de \(\Z\) sur \(G\). Si \(G\) est fini d'ordre \(n\), \(\Z/\text{Ker}(f)\) a pour ordre \(n\) ce qui impose que \(k=n\) et par conséquent que \(G\) est isomorphe à \(\Z/n\Z\). Ainsi \(G=\{a^0,a¹,\ldots,a^{n-1}\}\) et \(n\) est le plus petit entier \(m\) strictement positif tel que \(a^m=e\) l'élément neutre de \(G\).

Pour finir, \(G\) étant isomorphe à un groupe commutatif, il est également commutatif.

On rappelle que l'ordre d'un élément \(a\) d'un groupe fini \(G\) est l'ordre du sous-groupe monogène \(\text{gr}(a)\) de \(G\) qu'il engendre. Le théorème suivant n'est rien d'autre que le théorème de Lagrange.

Soit \(G\) un groupe fini. Tout élément de \(G\) est d'ordre fini et son ordre divise celui du groupe \(G\).

Exemple : d'après ce théorème nous savons que l'ordre de chaque entier de \(0\) à \(9\) divise \(9\) dans \(\Z/9\Z\). Cette proposition nous dit que cet ordre n'est autre que \(9\) pour ceux qui sont premiers avec \(9\), à savoir les entiers \(1,\) \(2,\) \(4,\) \(5,\) \(7,\) et \(8.\) Calculons l'ordre des trois autres valeurs, \(0\), \(3\), et \(6\). Le sous-groupe additif engendré par \(0\) est le singleton \(\{0\}\), il est donc d'ordre \(1\). Le sous-groupe additif engendré par \(3\) est l'ensemble \(\{3,6,0\}\), il est d'ordre \(3\). Le sous-groupe additif engendré par \(6\) est le même que celui engendré par \(3\).

Calculez l'ordre du sous-groupe de \(\Z/16\Z\) engendré par \(6\).
Soit \(G\) est un groupe fini d'ordre \(n\) et d'élément neutre \(e\), alors \begin{equation} \forall a\in G\quad a^n=e. \end{equation}
Notons \(r\) l'ordre de \(a\) dans \(G\), donc \(a^r=e\) mais le théorème nous dit que \(r\mid n\) donc il existe \(q\in\N\) tel que \(rq=n\), donc \(a^n=a^{rq}=(a^r)^q=e^q=e.\)
Tout groupe \(G\) d'ordre \(p\) premier est cyclique et donc commutatif, il est en­gen­dré par tout élément \(a\in G\setminus\{e\}\).
Soit \(r\) l'ordre d'un élément \(a\in G\setminus\{e\}\). Comme \(a\not=e\), on a \(r > 1\) et on sait d'après le théorème que \(r\mid p\), or \(p\) est premier donc \(r=p\) et \(\text{gr}(a)=G\).

Soit \(n\in\N^*\). Alors \(\forall(a,b,c,d)\in\Z^4\), on a \begin{equation} \begin{cases} a\equiv b\pmod n&\\ c\equiv d\pmod n& \end{cases} \Rightarrow \begin{cases} a+c\equiv b+d\pmod n\\ \phantom{a+}ac\equiv bd\pmod n \end{cases} \end{equation}
Démontrez cette proposition.
On note \({\alphabet}:=\{A,B,\ldots,Z\}\) l'alphabet latin muni de l'ordre alphabétique. Vérifiez que l'application \(f:\Z/26\Z\rightarrow\alphabet\) définie par \(f(i):=(i+1)\text{-ème lettre de}\ {\alphabet}\) est un isomorphisme d'ensembles or­don­nés ce qui permet d'identifier \({\alphabet}\) et \(\Z/26\Z\) (on suppose que les représentants de \(\Z/26\Z\) sont les entiers de l'intervalle \(\ab{0}{25}.\)) Exprimez le chiffrement de César avec un décalage circulaire de \(k\) lettres à l'aide d'une application \(e_k:\Z/26\Z\rightarrow\Z/26\Z\). Montrez qu'il s'agit d'une permutation de \({S}(\Z/26\Z).\) Combien d'orbites existe-t-il suivant \(e_k\) selon la valeur de \(k\) ? Quelle est la permutation inverse \(e_k^{-1}\) ?
L'application \(e_k\) est une injection puisque les images de deux entiers distincts sont des lettres distinctes. C'est une surjection car toute lettre de l'alphabet a un antécédent qui est sa position dans la séquence des \(26\) lettres rangées dans l'ordre croissant, c'est donc une bijection. C'est un morphisme puisque si \(i \leq j\), la \(i\)ème lettre de l'alphabet est inférieure à la \(j\)-ème lettre de l'alphabet. L'application réciproque est également un morphisme pour les mêmes raisons.

Si \(k\in\N\) est un entier naturel, le chiffrement de César est à présent représenté par l'ap­pli­ca­tion \(e_k\) définie par \[e_k(x):=x+k\] où l'addition est celle du groupe \((\Z/26\Z,+)\). Montrons que c'est un bijection. Soit \(x\) et \(y\) dans \(\Z/26\Z\) tels que \(e_k(x)=e_k(y)\), alors \begin{align*} x+k&=y+k\\ (x+k)+(-k)&=(y+k)+(-k)&&\qquad\text{\(k\) est symétrisable pour \(+\)}\\ x+(k+(-k))&=y+(k+(-k))&&\qquad\text{associativité de \(+\)}\\ x+0&=y+0&&\qquad\text{\(k\) et \((-k)\) sont symétriques pour \(+\)}\\ x&=y&&\qquad\text{\(0\) élément neutre pour \(+\)} \end{align*} L'application est également surjective, en effet soit \(y\in\Z/26\Z\), alors \(x:=y+(-k)\) est un antécédent de \(y\) puisque \(e_k(y+(-k))=(y+(-k)+k=y\). C'est donc une permutation des élé­ments du groupe \((\Z/26\Z,+)\).

Si \(k\equiv 0\pmod{26}\), alors \(e_k\) est la permutation identité et on sait que toutes les orbites sont des singletons, il y en a donc \(26\).

Si \((k,26)=1\), alors \(k\) engendre le groupe additif \((\Z/26\Z,+)\), i.e. \[\forall x\in\Z/26\Z\ \exists l\in\N\ kl=x.\] Mais \(kl=e_k^l(0)\) donc tous les entiers \(x\in\Z/26\Z\) appartiennent à l'orbie de \(0\), il n'y a donc qu'une seule orbite pour cette permutation.

Les seuls entiers qui ne sont pas premiers avec 26 sont \(k=2\) et \(k=13\). Si \(k=2\), l'orbite de \(0\) contient toute les valeurs paires et l'orbite de \(1\) toutes les valeurs impaires, il y a donc \(2\) orbites de longueur \(13\). Si \(k=13\), il y a \(13\) orbites de taille \(2\), les paires \(\{i,i+13\}\) pour tout \(i\in\ab{0}{12}\).

Les anneaux \({\mathbb Z}/n{\mathbb Z}\)

Structure d'anneau.

L'ensemble \(\Z\) est muni de deux lois de composition internes, l'addition et la multiplication dont les propriétés lui confèrent une structure d'anneau.

On appelle anneau tout triplet \((A,+,\times)\) où \(+\) et \(\times\) sont des lois de com­po­si­tion internes dites addition et multiplication qui satisfont les propriétés suivantes :
  1. \((A,+)\) est un groupe commutatif dont l'élément neutre est noté \(0\).
  2. \((A,\times)\) est un magma associatif et unifère dont l'élément neutre est noté \(1\).
  3. La multiplication est distributive sur l'addition.
Si la multiplication est commutative, l'anneau est dit commutatif. Si tout élément non nul est symétrisable pour la multiplication*(*) Con­di­tion sup­plé­men­tai­re équi­va­len­te à \((A\setminus\{0\},\times)\) est un grou­pe puis­que ce mag­ma est sup­po­sé as­so­cia­tif et uni­fè­re. alors l'anneau est appelé un corps.

Nous savons déjà d'après l'étude menée sur \((\Z,+)\) et \((\Z,\times)\) dans les précédents chapitres qu'il s'agit d'un anneau commutatif. Le triplet \((\R,+,\times)\) est également un anneau commutatif et même un corps puisque tout réel non-nul admet un inverse.

Le triplet \((\Z,+,\times)\) est un anneau commutatif.

Nous ne démontrerons pas les règles de calcul bien connues du lecteur depuis le lycée sur l'anneau \(\Z\) (règle des si­gnes, \(0.x=x.0=0\), etc.) Nous avons déjà vu la formule du binôme de Newton au chapitre Combinatoire.

Quand nous avons étudié la relation de divisibilité, dans \(\N\) ou dans \(\Z\), nous avons remarqué que tous les entiers sont des diviseurs de \(0\) puisque \(\forall a\in\Z\ a.0=0\). Dans le contexte des anneaux, on déroge à la définition générale pour \(0\) car il y joue un rôle particulier :

Dans un anneau commutatif \(A\), on appelle diviseur de 0 tout élément \(a\) non-nul de \(A\) tel qu'il existe un élément \(b\) non-nul de \(A\) tels que \begin{equation} a\,b=0. \end{equation} Un anneau sans diviseur de \(0\) est dit intègre.

Dans un anneau intègre, comme \(\Z\) par exemple, on a donc

\begin{equation} ab=0\Rightarrow (a=0)\wedge(b=0). \end{equation} Nous serons confrontés à des anneaux qui ne sont pas intègres dans la suite du chapitre.
Soit \((A,+,\times)\) un anneau. Le couple \((A^\times,\times)\) formé du sous-ensemble \(A^\times\) des inversibles de \(A\) et de la loi induite est un groupe appelé groupe des inversibles de \(A\).

En effet, la multiplication dans un anneau \(A\) est associative et on sait (cf. cette proposition) que le produit de deux éléments inversibles est inversible, donc \(A^\times\) est stable pour la multiplication. L'élé­ment neutre 1 est inversible, son inverse est lui-même et l'inverse \(x^{-1}\) de \(x\) est in­ver­si­ble (c'est \(x\)) donc \(x^{-1}\in A^\times\), finalement \((A^\times,\times)\) est un groupe.

Pour le corps \((\R,+,\times)\), on a \(\R^\times=\R\setminus\{0\}\). Pour l'anneau \((\Z,+,\times)\), on a \(\Z^\times=\{-1,1\}\).

Idéaux et anneaux quotients

Nous nous sommes intéressés à la structure de groupe additif de \(\Z\), nous avons montré que tous ses sous-groupes sont de la forme \((n\Z,+)\) et qu'ils sont tous normaux puisque le groupe \((\Z,+)\) est com­mu­ta­tif. Cela nous a permis de construire le groupe additif quotient \((\Z/n\Z,+)\). La question qui se pose à présent concerne la loi multiplicative, le groupe quotient \((\Z/n\Z,+)\) peut-il hériter également de la mul­ti­pli­ca­tion de \(\Z\) pour en faire un anneau ?

Nous verrons que la réponse est oui si ce groupe est stable pour la multiplication par n'importe quel élément de l'anneau. La méthodologie pour y arriver sera la même que celle que nous avons menée dans le chapitre Groupes. L'objectif est encore une fois de munir l'ensemble quotient d'une structure qui assure que la surjection canonique soit un morphisme, mais cette fois le morphisme doit respecter les deux struc­tu­res, additive et multiplicative. Pour ne pas alourdir inutilement les éc­ri­tu­res, on note de la même façon les lois additives et multiplicatives d'anneaux distincts :

Soit \((A,+,\times)\) et \((A',+,\times)\) deux anneaux. Une application \(f:A\rg A'\) est appelée morphisme d'anneaux si et seulement si elle satisfait les trois assertions suivantes :
  1. \(\forall(x,y)\in A^2\quad f(x+y)=f(x)+f(y)\),
  2. \(\forall(x,y)\in A^2\quad f(xy)=f(x)f(y)\),
  3. \(f(1_A)=1_{A'}\).
où \(1_A\) et \(1_{A'}\) désignent les éléments neutres respectifs de \(A\) et \(A'\) pour la mul­ti­pli­ca­tion.

La première condition indique que \(f\) est un morphisme du groupe additif \((A,+)\) de l'anneau \(A\). Pour qu'une partie \(B\subseteq A\) munie des lois induites par celles de \(A\) constitue elle aussi un anneau, il faut que \((B,+)\) soit un sous-groupe de \((A,+)\) stable pour la multiplication et qui contient \(1_A\). Ainsi le seul sous-anneau de \(\Z\) est nécessairement \(\Z\) lui-même puisque \((\Z,+)\) est le seul sous-groupe de \((\Z,+)\) qui contient \(1\).

On obtient aisément des résultats similaires à ceux que nous avons obtenus pour les sous-groupes d'un groupe et les morphisme de groupes. Ainsi, si \(f:A\rg A'\) est un morphisme d'anneaux, et \(B\) et \(B'\) sont respectivement des sous-anneaux de \(A\) et \(A'\), alors \(f^{-1}(B')\) et \(f(B)\) sont des sous-anneaux de \(A\) et \(B\) respectivement. D'autre part, l'intersection de sous-anneaux d'un anneau est encore un anneau, on peut donc définir le sous-anneau engendré par une partie \(B\) quelconque d'un anneau \(A\) comme l'intersection de tous les sous-anneaux de \(A\) qui contiennent \(B\).

On appelle idéal à gauche (resp. idéal à droite) d'un anneau \(A\) toute partie \(I\subseteq A\) qui satisfait les deux conditions suivantes :
  1. \((I,+)\) est un sous-groupe de \((A,+)\),
  2. \(\forall a\in A\ \ \forall i\in I\ \ ai\in I\ \ (\text{resp.}\ ia\in I).\)
Une partie qui est à la fois un idéal à gauche et à droite est appelé idéal bilatère.

La deuxième condition exprime que le sous-groupe additif est stable pour la multiplication (à gauche ou/et à droite) par un élément de l'anneau tout entier. Dans un anneau commutatif, comme \(\Z\) par exemple, tout idéal est nécessairement bilatère. Nous connaissons les sous-groupes additifs de \(\Z\), ce sont les ensembles du type \(n\Z:=\{nz\mid z\in\Z\}\), au­tre­ment dit l'ensemble des multiples de \(n\). Si l'on multiplie un multiple d'un entier \(n\) par n'importe quel entier, on obtient toujours un multiple de \(n\), autrement dit la condition 2 est toujours satisfaite, donc

Les idéaux bilatères de \(\Z\) sont les ensembles \(n\Z\).
Soit \(f:A\rg A'\) un morphisme d'anneaux et \(I'\) un idéal bilatère de \(A'.\) Alors \(f^{-1}(I')\) est un idéal bilatère de \(A\) qui contient le noyau \(\text{Ker}(f)\) qui est lui-même un idéal bi­la­tè­re de \(A\). Soit \(I\) un idéal bilatère de \(A\), alors \(f(I)\) est un idéal bilatère du sous-anneau \(f(A)\) de \(A'\) et donc un idéal bilatère de \(A'\) si \(f\) est surjectif.
Montrons la première partie du théorème, la preuve de la seconde partie est analogue. Notons \(I:=f^{-1}(I')\). L'élément neutre \(0_{A'}\) de \(A'\) appartient nécessairement à \(I'\) puisque \(I'\) est un sous-groupe additif de \(A'\). D'autre part, si \(f:X\rg Y\) est une application et \(U\subseteq V\) sont deux parties de \(Y\), alors \(f^{-1}(U)\subseteq f^{-1}(V)\), or \(\text{Kerf}(f)=f^{-1}(0)\) donc \(\text{Ker}(f)\subseteq I\). Puisque \(f\) est un morphisme de groupes et que \(I'\) est un sous-groupe de \((A',+)\), \(I\) est donc un sous-groupe de \((A,+)\).

Soit \((a,x)\in A\times I\), on a \(f(ax)=f(a)f(x)\), mais \(f(x)\in I'\) donc \(f(ax)\in I'\) puisque \(I'\) est stable par la multiplication d'un élément de \(A'\) et ainsi \(ax\in I\). On obtient de la même façon que \(xa\in I\), ainsi \(I\) est bien un idéal bilatère de \(A\). En particulier \(\text{Ker}(f)=f^{-1}(\{0_{A'}\})\) est un idéal bilatère puisque \(\{0_{A'}\}\) est un idéal bilatère de \(A'\).

Les groupes quotients \((\Z/n\Z,+)\) ont été obtenus à l'aide des seules relations d'équivalences \(\rel\) compatibles avec l'addition, à savoir celles qui satisfont \(x{\rel}x'\iff x-x'\in n\Z\) où \((n\Z,+)\) est un sous-groupe (nécessairement normal) de \((\Z,+)\). Mais cette relation est-elle compatible avec la mul­ti­pli­ca­tion, c'est-à-dire satisfait-elle la proposition

\[\forall y\in A\quad x{\rel}x'\then xy{\rel}x'y~?\]

La réponse est affirmative puisque si \(x-x'\in n\Z\), alors il existe \(z\in\Z\) tel que \(x-x'=nz\) et donc \(xy-x'y=n(yz)\) donc \(xy{\rel}x'y\). On peut donc munir \(\Z/n\Z\) de la loi quotient \(\times\) héritée de \(\Z\).

Soit \(n\in\N\). La relation d'équivalence définie sur \(\Z\) par \(x-y\in n\Z\) est com­pa­ti­ble avec les lois \(+\) et \(\times\) de l'anneau \(\Z\) faisant de \((\Z/n\Z,+,\times)\) un anneau commutatif pour les lois quotients appelé anneau des entiers modulo \(n\).

La surjection canonique \(\varphi:\Z\rg\Z/n\Z\) est donc non seulement un morphisme additif, mais également un morphisme d'anneaux.

Le noyau \(\text{Ker}(\varphi)\) est l'ensemble \(n\Z\) des multiples de \(n\).
On a \(\text{Ker}(\varphi)=\{x\in\Z\mid \overline{x}=\overline{0}\}\) et par définition \(\overline{x}=\overline{0}\) si et seulement s'il existe \(k\in\Z\) tel que \(x-0=kn\), soit si \(x\) est un multiple de \(n\).
Soit \(n\in\N\). Démontrez qu'un entier \(x\in\Z\) est un multiple de \(n\) si et seulement si le reste de la division euclidienne de \(n\) par \(x\) est nul.

On peut construire à présent la table de multiplication de \(\Z/n\Z\). Pour \(n=\,\) on obtient la table ci-dessous. Les valeurs nulles sont en rouge pour mettre en évidence les diviseurs de 0. D'autre part, les éléments du groupe des inversibles \((\Z/n\Z)^\times\) de \(\Z/n\Z\) (que nous étudierons plus bas) sont distingués en jaune) :

Table de multiplication du groupe \(\Z/\)\(\Z\). Les éléments du groupe des inversibles sont en jaune.
Comment lire dans la table de multiplication de \(\Z/n\Z\) si un élément \(x\in\Z/n\Z\) est inversible ? Dans ce cas, comment trouver son inverse ? Quel est l'inverse de 7 modulo 25 ? Quel est l'inverse de 11 modulo 26 ?
Soit \(k\) un entier naturel impair. Démontrez que \begin{equation} \label{eq:sommepu} \forall n\in\N\setminus\{0\}\quad {\color{#FF8}\sum_{i=0}^ni^k}\quad\text{est divisible par}\ \frac{n(n+1)}{2} \end{equation} Indication : en notant \(\color{#FF8}S(n,k)\) la somme de la proposition \((\ref{eq:sommepu})\) calculez \(S(n,k)+S(n,k)\) dans \(\Z/n\Z\) en appariant les termes \(i^k\) et \((n-i)^k\) puis en appariant les termes \(i^k\) et \((n-i+1)^k\).
On écrit la somme \(S(n,k)\) une première fois dans le sens croissant des indices et une autre dans le sens décroissant avant de sommer : \begin{equation*} \begin{matrix} S(n,k) &=& \color{#FF8}0^k & + & \color{#FF8}1^k & + & \cdots & + & \color{#FF8}(n-1)^k & + & \color{#FF8}n^k\\ S(n,k) &=& \color{#88F}n^k & + & \color{#88F}(n-1)^k & + & \cdots & + & \color{#88F}1^k & + & \color{#88F}0\\ 2S(n,k)&=& \underbrace{{\color{#FF8}0^k} + {\color{#88F}n^k}}_{\equiv 0\pmod n} & + & \underbrace{{\color{#FF8}1^k} + {\color{#88F}(n-1)^k}}_{\equiv 0\pmod n} & + & \cdots & + & \underbrace{{\color{#FF8}(n-1)^k} + {\color{#88F}1^k}}_{\equiv 0\pmod n} & + & \underbrace{{\color{#FF8}n^k} + {\color{#88F}0^k}}_{\equiv 0\pmod n} \end{matrix} \end{equation*} Mais dans \(\Z/n\Z\), \((n-i)^k=(-i)^k\) et si \(k\) est impair, on a \((-i)^k=-(i^k)\), donc \(2S(n,k)=0\) dans \(\Z/n\Z\) ce qui prouve que \(n|2S(n,k)\). On refait le même raisonnement mais cette fois en regroupant les termes \(i^k\) et \((n-i+1)^k\) pour prouver que \((n+1)\mid 2S(n,k)\) et donc que \(n(n+1)\mid 2S(n,k)\) soit \[ \frac{n(n+1)}{2}\mid \sum_{i=0}^ni^k. \]

Application: critères de divisibilité.

Bien que cette pratique soit devenue désuète, à tort, nous allons étudier la preuve par 9. Soit \(n\in\N\), \(x\) et \(y\) deux éléments de \(\Z\) et \(\varphi\) la surjection canonique de \(\Z\) sur \(\Z/n\Z\). Comme \(\varphi\) est un morphisme d'anneaux, on a \begin{align*} \varphi(x+y)&=\varphi(x)+\varphi(y),\\ \varphi(xy)&=\varphi(x)\varphi(y). \end{align*} Autrement dit le reste modulo \(n\) d'une somme (ou d'un produit) doit être égal à la somme des restes (ou le produit des restes). C'est donc une condition nécessaire (mais pas suffisante). Prenons par exemple \(n=2\) et observons la proposition suivante : \begin{equation} \label{eq:sample} 121+4195=4327. \end{equation} Elle est fausse bien sûr, et l'argument le plus simple pour s'en convaincre est que la somme de deux nombres impairs est un nombre pair, or ici le résultat est impair. Transportons ce calcul dans \(\Z/2\Z\) via la surjection canonique que nous noterons \(\varphi_2\) : \begin{align*} \varphi_2(121)+\varphi_2(4195)&=\varphi_2(4237)\\ 1+1&=1\\ {\color{red}0}&{\color{red}\;=1}\\ \end{align*} On aurait pu faire de même avec n'importe quelle autre valeur de \(n\), par exemple \(n=13\), \begin{align*} \varphi_{13}(121)+\varphi_{13}(4195)&=\varphi_{13}(4237)\\ 4+9&=12\\ {\color{red}0}&{\color{red}\;=12}\quad\text{car}\ 4+9\equiv 0\ \text{mod}\ 13. \end{align*}

Le lecteur perspicace fera deux objections. La première est que détecter une erreur de calcul en le plongeant dans \(\Z/13\Z\) semble encore plus fastidieux que de refaire ce calcul puisqu'il faut calculer le reste de la division euclidienne par 13, ce qui n'est pas aisé à faire de tête. La seconde est que si la vérification d'un calcul dans \(\Z/2\Z\) est beaucoup plus simple, elle manque singulièrement de fiabilité. En effet pour tout triplet \((x,y,z)\) de valeurs paires (resp. impaires) dans \(\Z\) l'équation \(x+y=z\) se traduira toujours par \(0+0=0\) (resp. \(1+1=1\)) et laisse passer beaucoup (c'est un eu­phé­mi­sme) de faux calculs dans les mailles grossières de ce filet.

Continuons malgré tout. Les multiples représentations des nombres sont étudiées dans un cours d'informatique générale ou d'architecture des ordinateurs de première année, nous supposons donc que le lecteur connaît quelques ru­di­ments sur la question. Notre système de numération permet de représenter un entier naturel à l'aide de chiffres. Quand on écrit \(a=2305\) en base 10, ceci se traduit par

\[ a=2.10^{3}+3.10^{2}+0.10^1+5.10^0, \]

Et plus généralement un entier \(a\) de \(k+1\) chiffres en base \(B\) s'écrit

\[ a=\sum_{i=0}^ka_iB^i. \]

Si \(\varphi_n\) désigne la surjection canonique de \(\Z\) dans \(\Z/n\Z\), on a nécessairement

\begin{equation} \label{eq:modulon} \varphi_n(a)=\sum_{i=0}^k\varphi_n(a_i)\left(\varphi_n(B)\right)^i. \end{equation}

Posons \(n:=B-1\), alors le reste de la division euclidienne de \(B\) par \(n\) est \(1\) puisque \(B=1.(B-1)+1\), donc \(\varphi_{n}(B)=1\). D'autre part, \begin{equation} \varphi_n(a_i)= \begin{cases} a_i&\text{si}\ a_i < n.\\ {\color{green}0}&\text{si}\ a_i=n.\\ \end{cases} \end{equation} mais le calcul de la somme dans \((\ref{eq:modulon})\) se faisant modulo \(n\), ont peut différer la réduction à \(0\) pour les chiffres \(a_i=n\) après l'addition :

\begin{equation} \varphi_n(a)=\sum_{i=0}^ka_i. \end{equation}

Concrètement, il suffit de faire la somme modulo \(n\) des chiffres qui constituent le nombre (en évitant, si on veut aller plus vite, les valeurs égales à \(n\)), pour calculer son reste modulo \(n.\) Reprenons l'exemple \((\ref{eq:sample})\) en base \(B=10\) pour laquelle \(n=9\) :

\begin{align*} \varphi_{9}(121)+\varphi_{9}(41{\color{green}9}5)&=\varphi_{9}(4237)\\ (1+2+1)+(4+1+{\color{green}0}+5)&=(4+2+3+7)\\ 14&=16\\ {\color{red}5}&{\color{red}\;=7}\\ \end{align*}

Notons que le même procédé d'invalidation du calcul pour l'égalité \(121+4195=4325\) aurait échoué puisque \(4+3+2+5\equiv 5\ \text{mod}\ 9\) alors que le bon résultat est \(4316\). La preuve par \(9\) ne permet donc pas de prouver qu'une opération a été effectuée correctement mais de prouver parfois qu'elle est fausse.

Un enseignant du collège donne des multiplications de deux nombres de 2 chiffres à ses élèves, et tire ces nombres au hasard. Quelle est la probabilité qu'un élève détecte son erreur de calcul avec la preuve par 9, s'il se trompe sur un seul chiffre du résultat ?
Retrouvez les critères de divisibilité d'un nombre (écrit en base \(10\)) par \(5\) et par \(10\) en vous inspirant des calculs précédents. Trouvez de la même façon les critères de divisibilité par \(3\), \(7\) et \(11\).
Formalisez le chiffrement de César sur l'anneau quotient \(\Z/26\Z\).

Algorithme d'Euclide, identité de Bézout

PGCD, algorithme d'Euclide.

Soit \(z\in\Z\). On note \(D_z:=\{d\in\Z\such d\mid z\}\) l'ensemble des diviseurs de \(z\). Il est clair que \(D_z=\Z\iff z=0\). On se donne deux entiers relatifs \(a\) et \(b\) et on veut étudier leurs diviseurs communs, autrement dit l'intersection \(D:=D_a\cap D_b\), dans le cas où l'un des deux entiers n'est pas nul, sans quoi \(D_a\cap D_b=\Z\).

L'ensemble \(D\cap\N\) n'est pas vide puisque \(1\mid a\) et \(1\mid b\). D'autre part, supposons que \(a\neq 0\), sinon on fait le même raisonnement avec \(b\), alors \(D\cap\N\) est majoré par \(\abs{a}\) puisque \(D_a\) est majoré par \(\abs{a}\) et \(D\) est inclus dans \(D_a\). L'ensemble \(D\cap\N\) est une partie non-vide et majorée de \(\N\), elle admet donc un plus grand élément :

Soit \(a\) et \(b\) deux entiers relatifs tels que \(a\neq 0\) ou \(b\neq 0\). Alors \(a\) et \(b\) admettent un plus grand commun diviseur, noté pgcd\((a,b)\) ou plus simplement \((a,b)\) quand aucune confusion n'est possible. Si \((a,b)=1\), les entiers \(a\) et \(b\) sont dits premiers entre eux.

Comme nous l'avons vu, si \(a=b=0\) l'ensemble des diviseurs commun de \(a\) et \(b\) est l'ensemble \(\Z\) tout entier qui n'admet pas de plus grand élément. On convient en général de poser la convention \((0,0):=0\).

Vérifiez que \(\forall a\in\Z\setminus\{0\}\ \ (a,0)=a\) et que \(\forall a\in\Z\ \ (a,1)=1\).

Si \(a\) et \(b\) sont deux entiers relatifs, comment calculer leur pgcd \((a,b)\) ? On vérifie facilement que \((a,b)=(\abs{a},\abs{b}),\) on peut donc ramener cette question au calcul du pgcd de deux entiers naturels. Une première idée est de les décomposer en produit de facteurs premiers pour trouver tous leurs diviseurs communs dont le produit répond bien sûr à la question.

Calculons (, ) de cette manière. Leurs factorisations sont :

On en déduit que () = . Malheureusement, la décomposition d'un entier en produit de fac­teurs premiers avec l'algorithme de division naïf est particulèrement coûteuse, nous ne l'avons pro­gram­mé ici que pour des valeurs de \(a\) et \(b\) très petites.

Pour décomposer un entier \(n\) en produit de facteurs premiers, nous avons effectué autant de divisions euclidiennes qu'il y avait de nombres premiers inférieurs ou égaux à sa racine. Cette approche n'a de sens que si l'on connaît tous ces nombres premiers, mais comment faire si \(n\) est un nombre arbitrairement grand et dépasse possiblement la capacité de notre table ? L'idée la plus simple est de con­ti­nuer les divisions euclidiennes avec tous les nombres impairs supérieurs à \(p\) (et toujours in­fé­rieurs ou égaux à \(\sqrt{n}\)). On fait évidemment plus de divisions que né­ces­sai­re. On peut donc estimer asymptotiquement (c'est-à-dire quand \(n\rg +\infty\)) que le nombre de divisions euclidiennes à réaliser pour fac­to­ri­ser \(n\) dans le pire des cas (quand il est premier) est égal à \(\frac{\sqrt{n}}{2}\).

Si l'on se souvient que la partie entière \(\lfloor x\rfloor\) d'un nombre réel est l'unique entier \(\nu\) tel que \(\nu\leq x < \nu+1\), on peut démontrer que le nombre \(k\) de chiffres dans la rep­ré­sen­ta­tion en base \(b\) d'un entier naturel \(n\) est donné par \[k=1+\lfloor\log_b n\rfloor.\] Autrement dit si l'on exprime \(n\) en fonction de \(k\), on a \(b^k \leq n < b^{k+1}-1\), on en déduit que \[ {\color{88F}\frac{b^{\frac{k}{2}}}{2}} \leq \frac{\sqrt{n}}{2} < \frac{b^{\frac{k+1}{2}}}{2} \] Le nombre de divisions euclidienne est donc exponentiel en la moitié du nombre de chiffres de l'entier \(n.\) D'autre part, nous avons fait abstraction du coût du calcul d'une division euclidienne qui mériterait lui aussi notre attention. Toutes ces ques­tions relèvent des enseignements d'algorithmique.

On peut calculer le pgcd de deux entiers sans connaître leurs décompositions en produits de facteurs premiers. C'est Euclide*(*) Mathématicien grec qui vécut 300 ans avant jc. qui décrivit la première fois comment procéder.

Soit \(a\) et \(b\) deux entiers naturels tels que \(a\geq b\). Alors \begin{equation} \label{eq:pgcd} (a,b)=(a-b,b). \end{equation}
Montrons que l'ensemble \(D(a,b)\) des diviseurs communs à \(a\) et \(b\) est égal à l'ensemble \(D(a-b,b)\) des diviseurs communs à \(b\) et \(a-b\).

Soit \(d\in D(a,b)\), montrons que \(d\in D({\color{#88F}b,a-b})\). Si \(d\in D(a,b)\), alors \(d\mid a\) et \(\color{#88F}d\mid b\) et il existe alors deux entiers naturels \(h\) et \(k\) tels que \(dh=a\) et \(dk=b\). On en déduit que \(d(h-k)=a-b\) et \(\color{#88F}d\mid(a-b)\), autrement dit que \(d\in D(a-b,b)\).

Réciproquement soit \(d\in D(b,a-b)\), montrons que \(d\in D({\color{#FF8}a,b})\). Si \(d\in D(b,a-b)\), alors \(\color{#FF8}d\mid b\) et \(d\mid (a-b)\) et il existe alors deux entiers naturels \(h\) et \(k\) tels que \(dh=b\) et \(dk=a-b\). On en déduit que \(d(h+k)=a\) au­tre­ment dit que \(\color{#FF8}d\mid a\), donc \(d\in D(a,b)\).
Soit \(a\) et \(b\) deux entiers naturels. Alors \begin{equation} \label{eq:pgcdbis} (a,b)=(b,r) \end{equation} où \(r\) est le reste de la division euclidienne de \(a\) par \(b\).
Si \(a < b\), alors le reste de la division euclidienne de \(a\) par \(b\) est égal à \(a\), or \((a,b)=(b,a)\), le résultat est donc vrai. Sinon d'après le théorème de la division euclidienne, il existe un unique couple \((q,r)\in\N^2\) tel que \(a=qb+r\) avec \(0\leq r < b\). On en déduit que si \(k\in\ab{1}{q-1}\) alors \(a-kb\geq b\), autrement dit que l'on peut appliquer \(q\) fois de suite le théorème pour obtenir \((a,b)=(a-qb,b)=(r,b).\)

L'identité \((\ref{eq:pgcdbis})\) suggère un algorithme du calcul pgcd de deux entiers \(a\) et \(b\) plus efficace que de répéter des soustractions (l'algorithme d'Euclide). Il suffit d'appliquer une seule division euclidienne à chaque étape jusqu'à ce que le reste soit nul, le quotient de la dernière division fournit le résultat :

PGCD(a,b)
ENTRÉE: deux entiers naturels a, b
SORTIE: le PGCD (a,b)

TANT QUE (b > 0):
   t ← b
   b ← a MOD b
   a ← t
RENVOYER a

Notons que si \(a < b\), le premier passage dans la boucle échange les valeurs de \(a\) et \(b\) ce qui évite de les comparer avant d'entrer dans la boucle.

Pour les entiers \(a=\;\) et \(b=\;\), cet algorithme effectue et fournit le résultat suivant (les quotients et restes des divisions euclidiennes successives sont éga­le­ment af­fi­chés) :

Et en anticipant sur la version étendue de cet algorithme qui sera étudiée plus loin, on ob­tient un couple \((u,v)=\,\) solution de l'identité de Bézout :

.

Puisque nous avons recalé la décomposition en produits de facteurs premiers pour le calcul du pgcd parce que l'algorithme était exponentiel en le nombre de chiffres de \(a\), il faut s'intéresser à l'efficacité de l'algorithme d'Euclide. On montre (en algorithmique) que le nombre de divisions euclidiennes est proportionnel au logarithme de \(a\) (en supposant que \(a \geq b\)), donc linéaire en le nombre de chiffres de \(a\).

Cet algorithme ne se limite pas aux éléments de l'anneau \(\Z\) mais fonctionne également avec des polynômes à coefficients dans un corps. Notons que cet al­go­ri­thme repose sur une succession de divisions euclidiennes, ceci suppose que l'on dispose également d'un algorithme effectif pour réaliser ces divisions. L'algorithme étudié au collège n'est peut-être pas le plus efficace. Toutes ces questions sur l'effectivité et l'efficacité des calculs sont étudiées dans les enseignements d'al­go­ri­thmi­que.
Calculez le pgcd de \(231\) et \(182\) avec l'algorithme d'Euclide.
Montrez qu'il n'existe pas d'entiers naturels \(a\) et \(b\) tels que leur somme est égale à \(101\) et dont le pgcd est égal à \(3\).
Pour un examen, on a réparti 367 étudiants dans 9 salles de même capacité en remplissant chaque salle avant d'en ouvrir une autre. Quelle était la capacité des salles et combien d'étudiants composeront dans la dernière salle d'examen ?
La suite de Fibonacci est un suite d'entiers naturels récurrente de premiers termes \(F_0:=0\) et \(F_1:=1\) et définie par la relation \begin{equation} \forall n\in\N\quad F_{n+2}:=F_{n+1}+F_n. \end{equation} Montrez que cette suite est strictement croissante. Calculez la division euclidienne de \(F_n\) par \(F_{n-1}\). Que vaut le quotient ? Qu'en déduisez-vous sur l'algorithme d'Euclide ?
Écrivez une fonction PGCD(a,b) en Python qui renvoie le pgcd des deux entiers naturels \(a\) et \(b\) passés en paramètres en appliquant l'algorithme vu plus haut.

Identité de Bézout

Un idéal \(I\) d'un anneau commutatif \((A,+,\times)\) est dit principal s'il est engendré par un unique élément, i.e. s'il existe \(a\in A\) tel que \(aA=I.\) Un anneau dont tous les idéaux sont principaux est dit principal.
L'anneau \(\Z\) est un anneau principal.
Nous savons que les idéaux de \(\Z\) sont du type \(n\Z\).
Soit \(a\) et \(b\) deux entiers naturels. Alors \begin{equation} \label{eq:incldiv} a\Z\subseteq b\Z\ \iff\ b\mid a. \end{equation}
Montrons que la condition est nécessaire. Si \(a\Z\subseteq b\Z\), \(a\in b\Z\) donc il existe \(k\in\Z\) tel que \(a=kb\) soit \(b\mid a\). Montrons qu'elle est suffisante. Si \(b\mid a\) alors il existe \(k\in\Z\) tel que \(kb=a\) et si \(x\in a\Z\), il existe \(h\) tel que \(x=ha\) donc \(x=(hk)b\) ce qui prouve que \(x\in b\Z\).

Si \(I\) et \(J\) désignent deux idéaux d'un anneau commutatif \(A\), on appelle idéal somme de \(I\) et \(J\), que l'on note \(I+J\), l'intersection de tous les idéaux de \(A\) qui contiennent toutes les sommes \(au+bv\) où \((a,b)\in I\times J\) et \((u,v)\in A^2\). Comme les idéaux de \(\Z\) sont du type \(n\Z\), l'idéal somme \(a\Z+b\Z\) est le plus petit idéal qui contient les sommes du type \(au+bv\) puisque les éléments de ces idéaux de \(\Z\) sont déjà des multiples de \(a\) et \(b\).

Soit \(a\) et \(b\) deux entiers naturels. On a \begin{equation} \label{eq:sommeid} a\Z+b\Z=(a,b)\Z. \end{equation}
Comme l'anneau \(\Z\) est principal, l'idéal somme est nécessairement de la forme \(d\Z\). Nous allons montrer que \(d=(a,b)\). Comme \(a\in a\Z+b\Z\) et \(b\in a\Z+b\Z\), le lemme précédent nous dit que \(d\mid a\) et \(d\mid b\), donc \(d\) est un diviseur commun à \(a\) et \(b\). Il nous reste à montrer que c'est le plus grand. Soit \(e\) un diviseur commun à \(a\) et \(b\), montrons que \(e\mid d\). Le lemme montre que \(a\Z\subseteq e\Z\) et \(b\Z\subseteq e\Z\). Mais \(e\Z\) étant un idéal de \(\Z,\) c'est en particulier un sous-groupe additif de \(\Z\), il est donc stable pour l'addition. Ainsi, si \(a\Z\subseteq e\Z\) et \(b\Z\subseteq e\Z\), on a \(\forall (h,k)\in \Z\times \Z\) \(ah+bk\in e\Z\) et donc \(a\Z+b\Z\subseteq e\Z\). On applique une fois de plus le lemme pour conclure que \(e\mid d\).
Soit \((a,b,d)\in\Z^2\times\N\). Alors il existe deux entiers re­la­tifs \(u\) et \(v\) qui satisfont l'identité de Bézout \begin{equation} \label{eq:Bézout} au+bv=d, \end{equation} si et seulement si \((a,b)\mid d\).
Montrons que c'est une condition nécessaire. Soit \(u\) et \(v\) sont deux entiers relatifs, alors par définition \((au+bv)\) appartient à l'idéal somme \(a\Z+b\Z\) et donc à l'idéal \((a,b)\Z\) d'après l'égalité \((\ref{eq:sommeid})\) du lemme. S'ils satisfont l'identité de Bézout \((\ref{eq:Bézout})\), alors \(d\in(a,b)\Z\) ce qui se traduit par \((a,b)\mid d\).

Montrons que c'est une condition suffisante. Supposons que \((a,b)\mid d\), montrons qu'il existe un couple d'entiers relatifs \((u,v)\) qui satisfont l'identité de Bézout \((\ref{eq:Bézout})\). Si \((a,b)\mid d\), on sait d'après l'équivalence \((\ref{eq:incldiv})\) que \(d\Z\subseteq (a,b)\Z\) ou encore \(d\Z\subseteq a\Z+b\Z\) après l'égalité \((\ref{eq:sommeid})\) du lemme, ce qui prouve que \(d\) s'écrit sous la forme \(au+bv\).

Notons que le théorème n'affirme pas que le couple solution \((u,v)\) est unique, nous y reviendrons. À quoi peut servir l'identité de Bézout ? Une première réponse est fournie par le corollaire sui­vant qui établit un nouveau critère pour déterminer si deux nombres sont premiers entre eux.

Deux entiers relatifs \(a\) et \(b\) sont premiers entre eux si et seulement s'il existe deux entiers relatifs \(u\) et \(v\) tels que \begin{equation} \label{eq:bezout1} au+bv=1. \end{equation}

Une conséquence très importante de ce corollaire est de fournir un moyen de calculer l'inverse d'un élé­ment \(x\) de \((\Z/n\Z)^\times\). On peut bien sûr s'appuyer sur la table de multiplication et chercher où se trouve la valeur \(1\) sur la ligne d'entrée \(x\), mais même en ne faisant que la moitié des opérations grâce à la commutativité de \(\Z/n\Z\), cela en nécessite \(\frac{n^2}{2}\). Nous verrons à la dernière section que la cryptographie fait un usage immodéré de cet anneau modulaire pour des entiers \(n\) qui comportent plus de 600 chiffres*(*) Ce n'est pas une co­quil­le, il s'agit bien d'en­tiers \(n\) proches de \(10^{616}\). en base 10, et la mémoire de tous les ordinateurs de la planète réunie ne suffirait pas à contenir cette table de mul­ti­pli­ca­tion.

Un couple qui satisfait \((\ref{eq:bezout1})\) permet de calculer l'inverse d'un élément \(x\in(\Z/n\Z)^\times\). En effet, soit \(x\) un entier premier avec \(n\), condition nécessaire et suffisante pour que \(x\) admette un inverse. C'est là que le corollaire entre en scène, si \(x\) est premier avec \(n\), on sait qu'il existe un couple \((u,v)\) tel que \(xu+nv=1\) et donc \begin{equation} xu\equiv 1\ (\text{mod}\ n). \end{equation} Autrement dit, l'entier \(u\) est l'inverse de \(x\) dans \(\Z/n\Z\). Mais nous n'avons fait que re­pous­ser le problème. L'identité de Bézout et son corollaire sont des théorèmes existentiels et pas des théorèmes constructifs, ils ne fournissent pas d'algorithmes pour construire le couple \((u,v)\). Heureusement, il en existe.

En supposant qu'un ordinateur est capable de calculer \(10^9\) éléments de la table de multiplication de \(\Z/n\Z\) par seconde, combien de temps faudrait-il pour calculer cette table pour \(n=10^{616}\) ? NB. Toute vie humaine devrait cesser sur notre planète d'ici 2 à 3 milliards d'années.

Algorithme d'Euclide étendu

D'après l'identité de Bézout \((\ref{eq:Bézout})\), l'équation n'a de solution que si \((a,b)\mid d\) et en particulier si \(d=(a,b)\). Si nous déterminons un couple \((u,v)\in\Z^2\) tel que \(au+bv=(a,b)\), alors pour tout entier \(d\) multiple de \((a,b)\), le couple \((u\frac{d}{(a,b)},v\frac{d}{(a,b)})\) satisfera l'identité de Bézout \begin{equation} a(u\frac{d}{(a,b)})+b(v\frac{d}{(a,b)})=d \end{equation}

C'est en observant attentivement la construction du pgcd avec l'algorithme d'Euclide que l'on peut construire un couple \((u,v)\) qui satisfait \(au+bv=(a,b)\). Observons la suite des divisions euclidiennes effectuées pour obtenir \((192,57)=\boxed{3}\) en précisant leurs quotients et leurs restes :

\begin{align} \notag 192&=57\,.\,{\color{#88F}3} + {\color{#FF8}21}\\ \notag57&=21\,.\,{\color{#88F}2} + {\color{#FF8}15}\\ \notag21&=15\,.\,{\color{#88F}1} + {\color{#FF8}6}\\ \label{eq:box1}15&=6\,.\,{\color{#88F}2} + {\color{#FF8}3}\\ \notag 6&=\boxed{3}\,.\,{\color{#88F}2} + {\color{#FF8}0} \end{align}

Isolons les restes dans chacune de ces identités (sauf la dernière où il est nul). C'est donc l'avant dernier reste \((\ref{eq:box1})\) qui fournit le pgcd \(\boxed{3}\) :

\begin{align} \notag 192\,.\,{\color{#F62}1} + 57\,.\,{\color{#88F}(-3)} &= 21\\ \notag57\,.\,{\color{#F62}1} + 21\,.\,{\color{#88F}(-2)} &= 15\\ \label{eq:box2}21\,.\,{\color{#F62}1} + 15\,.\,{\color{#88F}(-1)} &= \boxed{6}\\ \label{eq:box3}15\,.\,{\color{#F62}1} + \boxed{6}\,.\,{\color{#88F}(-2)} &= 3 \end{align}

On reconnaît ici autant d'identités de Bézout avec leurs solutions \(({\color{#F62}u},{\color{#88F}v})\) respectives. L'idée est de faire remonter la valeur \(3\) jusqu'à la première égalité à l'aide de simples additions et multiplications. En multipliant l'égalité \((\ref{eq:box2})\) par le coefficient \({\color{#88F}v=-2}\) de l'entier \(\boxed{6}\) dans l'égalité \((\ref{eq:box3})\), on obtient un nouveau système :

\begin{align} \notag 192\,.\,{\color{#F62}1} + 57\,.\,{\color{#88F}(-3)} &= 21\\ \notag57\,.\,{\color{#F62}1} + 21\,.\,{\color{#88F}(-2)} &= 15\\ \label{eq:box4}21\,.\,{\color{#F62}(-2)} + 15\,.\,{\color{#88F}2} &= \boxed{6\,.\,(-2)}\\ \label{eq:box5}15\,.\,{\color{#F62}1} + \boxed{6\,.\,{\color{#88F}(-2)}} &= 3\\ \end{align}

On additionne alors les deux dernières égalités \((\ref{eq:box4})\) et \((\ref{eq:box5})\) pour éliminer \(\boxed{6\,.\,(-2)}\) de part et d'autre du résultat pour obtenir l'identité de Bézout \((\ref{eq:box6})\)  :

\begin{align} \notag 192\,.\,{\color{#F62}1} + 57\,.\,{\color{#88F}(-3)} &= 21\\ \notag57\,.\,{\color{#F62}1} + 21\,.\,{\color{#88F}(-2)} &= \boxed{15}\\ \label{eq:box6}21\,.\,{\color{#F62}(-2)} + \boxed{15}\,.\,{\color{#88F}3} &= 3 \end{align}

Et on fait remonter ainsi \(3\) de proche en proche :

\begin{align} \notag 192\,.\,{\color{#F62}1} + 57\,.\,{\color{#88F}(-3)} &= 21\\ \notag57\,.\,{\color{#F62}3} + 21\,.\,{\color{#88F}(-6)} &= \boxed{15\,.\,3}\\ 21\,.\,{\color{#F62}(-2)} + \boxed{15\,.\,{\color{#88F}3}} &= 3 \end{align}

Soit

\begin{align} \notag 192\,.\,{\color{#F62}1} + 57\,.\,{\color{#88F}(-3)} &= \boxed{21}\\ \notag 57\,.\,{\color{#F62}3} + \boxed{21}\,.\,{\color{#88F}(-8)} &= 3\\ \end{align}

Et donc

\begin{align} \notag 192\,.\,{\color{#F62}(-8)} + 57\,.\,{\color{#88F}24} &= \boxed{21\,.\,(-8)}\\ \notag 57\,.\,{\color{#F62}3} + \boxed{21\,.\,{\color{#88F}(-8)}} &= 3\\ \end{align}

Pour obtenir finalement

\begin{align} \notag 192\,.\,{\color{#F62}(-8)} + 57\,.\,{\color{#88F}(27)} &= 3\\ \end{align}

Notons \((q_i)_{i\in\llbracket 1,\,n\rrbracket }\) les \(n\) premiers quotients des \(n+1\) divisions euclidiennes qui ont été effectuées suc­ces­si­ve­ment pour calculer \((a,b)\). Alors le couple solution de la \(i\)-ème identité de Bézout cor­res­pon­dan­te est égal à \((1,-q_i)\). Dans notre exemple, on avait \[(q_1,q_2,q_3,q_4)=(3,2,1,2).\]

Chaque remontée du pgcd consiste en une multiplication et une addition de l'identité de Bézout précédente, modifiant du coup les valeurs du couple solution de cette identité. Notons \((u,v)\) le couple qui va décrire successivement les couples solutions de ces \(n\) identités de Bézout en partant de la dernière. On pose initialement \((u,v):=(0,1)\). Pour obtenir le couple solution de la dernière identité, on vérifie facilement qu'il suffit d'appliquer la règle de réécriture \(R_{\color{#FF8}n}\) suivante :

\begin{equation} \label{eq:regle} R_{\color{#FF8}n}:\qquad(u,v)\lf (v,u-q_{\color{#FF8}n}v). \end{equation}

Soit pour notre exemple \((u,v)\lf(1,0-2.1)=(1,-2)\) (cf. identité \((\ref{eq:box1})\)). Puis on recommence en appliquant successivement les règles \(R_{n-1}\), \(R_{n-2}\), etc. jusqu'à \(R_1\). En conclusion, l'algorithme d'Euclide étendu consiste dans un premier temps à appliquer l'algorithme d'Euclide aux entiers \(a\) et \(b\) pour construire la séquence des quotients \((q_i)_{i\in\llbracket 1,\,n\rrbracket }\) des divisions euclidiennes successives, puis dans un deuxième temps à appliquer les règles de réécritures \(R_{i}\) au couple \((u,v)\lf(0,1)\) pour \(i\) allant de \(n\) à \(1\).

Notons que la liste \(Q\) de l'algorithme ci-dessous contient tous les quotients, y compris le dernier pour lequel le reste est nul, la remontée se fait donc à partir de l'avant dernier quotient ici.

PGCD-Etendu(a,b)
ENTRÉE: deux entiers relatifs a, b
SORTIE: un couple d'entiers relatifs (u,v) tel que au+bv = PGCD(a,b)

Q ← []
TANT QUE (b > 0):
   t ← b
   Q ← Q + [a DIV b]
   b ← a MOD b
   a ← t
i ← #Q - 2
u ← 0
v ← 1
TANT QUE (i > 0):
   t ← u
   u ← v
   v ← t - Q[i] * v
   i ← i - 1
RENVOYER (u,v)

Le théorème suivant exprime la succession de réécritures \((\ref{eq:regle})\) en termes plus proche du langage ma­thé­ma­ti­que classique, à savoir un produit matriciel. L'annexe en fin de chapitre fournit le minimum vital sur les matrices pour comprendre l'énoncé de ce théorème.

Vérifiez qu'appliquer la règle de réécriture \(R_i\) (cf. \((\ref{eq:regle})\)) au couple \((u,v)\) équivaut à remplacer le couple \((u,v)\) par le résultat du produit matriciel suivant : \[\begin{pmatrix} 0 & 1\\ 1 & -q_i \end{pmatrix} \times \begin{pmatrix} u\\ v \end{pmatrix}. \]

Nous admettrons le théorème suivant dont nous avons donné les grandes lignes de la preuve. Cette fois, il s'agit d'un théorème constructif qui exprime d'une autre façon l'algorithme d'Euclide étendu.

Soit \((a,b,d)\in\Z^2\times\N\) et \((q_i)_{i\in\llbracket 1,\,n\rrbracket }\) la séquence des quotients successifs avec restes non-nuls des divisions euclidiennes de l'algorithme d'Euclide. Alors le couple \((u,v)\) suivant est solution de l'identité de Bézout : \begin{equation} (u,v):=\left[ \prod_{i=1}^n \begin{pmatrix} 0&1\\ 1&-q_i \end{pmatrix} \right] \begin{pmatrix} 0\\ \frac{d}{(a,b)} \end{pmatrix} \end{equation}
Calculez un couple \((u,v)\) solution de l'identité de Bézout pour les couples d'entiers relatifs suivants : \((2018,1789)\), \((-300,157)\) et \((1515,1984)\).
Calculez l'inverse de \(7\) modulo \(2018\) et l'inverse de \(451\) modulo \(1236\).
Un chef de chantier essaie d'organiser la construction d'une villa dans le Var. Il doit faire intervenir deux artisans le même jour. Le premier n'est disponible qu'un jour sur 6, l'autre une fois tous les 11 jours. Le chef de chantier a pu rencontrer le premier artisan le lundi 12 mars et le second le mercredi 14 mars. Quel jour doit-il leur donner rendez-vous pour leur faire effectuer les travaux le plus tôt possible ?

Equation diophantienne \(ax+by=c\)

Les équations diophantiennes sont des équations polynomiales dont les inconnues sont cherchées dans \(\Z\) ou éventuellement \(\Q\). Elles jouent un rôle important en cryptologie.

Exemple : considérons l'équation à trois inconnues \begin{equation} \label{eq:Fermat} x^n+y^n=z^n. \end{equation} étudiée par Fermat*(*) Fermat était un ma­thé­ma­ti­cien et un ma­gis­trat fran­çais du 17ème siècle. admet une infinité de solutions dans \(\Z\) pour \(n=1\) puisqu'il simplement d'une addition. Pour \(n=2\), le triplet \((x,y,z):=(3,4,5)\) est une solution que les maçons connaissent par­fai­te­ment puisqu'elle leur permet de construire des murs à angles droits sans mètre ni équerre. En effet l'égalité \begin{equation} \label{eq:macon} 3^2+4^2=5^2 \end{equation} prouve qu'un triangle de côtés de longueurs \(3\) et \(4\) et d'hypothénuse \(5\) est nécessairement rectangle d'après la réciproque du théorème de Pythagore. Fermat conjectura en 1637 que l'équation \((\ref{eq:Fermat})\) n'ad­met­tait aucune solution dans \(\Z\) si \(n > 2\). Il a fallu attendre 1994 pour que le mathématicien anglais Andrew Wiles prouve enfin cette conjecture.

Expliquez comment un maçon peut s'assurer qu'un mur est à angle droit sans disposer d'une équerre ni d'un mètre en s'appuyant sur l'égalité \((\ref{eq:macon})\) ?

Nous serons moins ambitieux ici, et nous nous intéresserons à des équations à deux inconnues \(x\) et \(y\) de la forme

\begin{equation} \label{eq:diolin} ax+by=c \end{equation}

où \((a,b,c)\in\Z^3\) et où les solutions \((x,y)\) sont cherchées dans \(\Z\times\Z\). On reconnaît bien sûr la forme de l'identité de Bézout et on sait d'après le théorème de Bézout qu'il faut nécessairement que \((a,b)\mid c\) sans quoi il n'y a pas de solutions. Supposons donc que \((a,b)\mid c\). L'algorithme d'Euclide étendu nous fournit alors un couple \((u,v)\) solution de l'équation \begin{equation*} au+bv=(a,b) \end{equation*} Il suffit de multiplier cette équation par \(\frac{c}{(a,b)}\) pour obtenir \begin{equation} a\frac{c}{(a,b)}u+b\frac{c}{(a,b)}v=c. \end{equation} Et ainsi le couple \((x,y):=(\frac{c}{(a,b)}u,\frac{c}{(a,b)}v)\) est solution de l'équation \((\ref{eq:diolin})\).

Soit \(a\), \(b\) et \(c\) trois entiers relatifs et \((x,y)\) une solution de l'équation diophantienne \((\ref{eq:diolin})\). Alors \(\forall k\in\Z\) le couple \begin{equation} \label{eq:allsol} \left(x-k{b \over (a,b)}, y+k{a \over (a,b)}\right) \end{equation} est également solution de l'équation \((\ref{eq:diolin})\).
Il suffit de remplacer ces deux valeurs dans l'expression \((\ref{eq:diolin})\) pour s'en con­vainc­re. Autrement dit, si l'on a un couple solution, on en a un infinité.

Théorèmes de Gauss, Euler, Fermat

Nous avons vu que tous les éléments de \(\Z/n\Z\) n'étaient pas nécessairement inversibles. On peut donc se demander s'il existe un moyen de reconnaître ceux qui le sont sans avoir à calculer la table de multiplication. Tous les théorèmes qui vont suivre tournent autour de ces questions et du sous-ensemble \((\Z/n\Z)^\times\) des éléments inversibles de \(\Z/n\Z\) qui constitue un groupe multiplicatif.

Soit \(n\in\N^*\) et \(x\in\Z/n\Z\) avec \(x\not=0\). Les trois propositions suivantes sont équivalentes :
  1. L'entier \(x\) est inversible, soit \(x\in (\Z/n\Z)^\times\),
  2. L'entier \(x\) n'est pas un diviseur de 0, soit \(\forall y\in\Z/n\Z\ \ x.y=0\Rightarrow y = 0\),
  3. L'entier \(x\) est premier avec \(n\) soit \((x,n)=1\).
Montrons que \((1)\Rightarrow(2)\). Si \(x\) est inversible et que \(x.y=0\), alors \(x^{-1}.x.y=x^{-1}.0=0\), soit \(y=0\). Montrons que \((2)\Rightarrow(3)\) par contraposition. Si \((x,n) > 1\), alors il existe \(k\in\Z\setminus\{-1,1\}\) et \(x',n')\in\Z^2\) tels que \(k.x'\mid x\) et \(k.n'=n\). Donc \(k.n'x'=x.n'\) soit \(n.x'=x.n'\) d'où \(x.n'\equiv 0\ (\text{mod}\ n)\), ce qui prouve que \(x\) est un diviseur de \(0\). Montrons que \((3)\Rightarrow(1)\). D'après le corollaire du théorème de Bézout, si \((x,n)=1\), il existe un couple \((u,v)\) tel que \(xu+nv=1\) ce qui entraîne que \(xu\equiv 1\ (\text{mod}\ n)\), autrement dit que \(u\) est l'inverse de \(x\) dans \(\Z/n\Z\).
Soit \(n\in\N^*\). L'anneau commutatif \(\Z/n\Z\) est intègre si et seulement si \(n\) est un nombre premier \(p\). Dans ce cas \(\Z/p\Z\) est un corps.
Si \(n\) est premier, tous les entiers \(x\) tels que \(0 < x < n\) sont premiers avec \(n\) et donc inversibles. Donc si \(x.y=0\) alors \(x^{-1}.x.y=0\) et \(y\) est égale à \(0\). Il n'y a donc pas de diviseurs de 0. Inversement si \(n\) n'est pas premier, il s'écrit \(n=pq\) avec \(0 < p < n\) et \(0 < q < n\) et on a donc bien deux entiers \(p\) et \(q\) tels que \(p.q\equiv 0\ \text{mod}\ n\).
Soit \((a,b,c)\in\Z^3\). Si \(a\) est premier avec \(b\) et divise le produit \(bc,\) alors \(a\) divise \(c\) : \begin{equation} \big(((a,b)=1)\,\wedge\,(a\mid bc)\big)\ \Rightarrow\ \big(a\mid c\big). \end{equation}
Si \((a,b)=1\), alors d'après identité de Bézout il existe un couple \((u,v)\) tel que \(au+bv=1\) soit \(auc+bvc=c\). Comme \(a\mid bc\) alors \(a\mid bvc\) et donc \(a\mid(auc+bvc)\) soit \(a\mid c\).

Une première application du théorème de Gauss est de montrer que si \(p\) est un nombre premier, alors les coefficients binomiaux \(\binom{p}{k}\) sont tous divisibles par \(p\) pour \(k\in\ab{1}{p-1}\). En effet, on a \begin{equation*} \binom{p}{k}=\frac{p!}{k!(p-k)!}, \end{equation*} d'où \begin{equation*} p!={\color{#88F}k!(p-k)!\binom{p}{k}}, \end{equation*} mais puisque \(p\) divise \(p!\), il divise le membre droit de l'égalité ci-dessus. Mais \(p\) est premier avec \(h!(p-h)!\) pour tout \(k\in\ab{1}{p-1}\), le théorème de Gauss permet de conclure. Un corollaire important (le lemme d'Euclide) en découle immédiatement :

Soit \((a,b)\in\Z^2\) et \(p\) un nombre premier. Si \(p\) divise le produit \(ab\) alors \(p\) divise \(a\) ou \(p\) divise \(b\) : \begin{equation} \big(p\mid ab\big)\ \Rightarrow \big((p\mid a)\ \vee\ (p\mid b)\big). \end{equation}

D'après ce théorème, on sait que le groupe \((\Z/n\Z)^\times\) des inversibles de \(\Z/n\Z\) est constitué des classes des entiers premiers avec \(n\). C'est un groupe fini, son ordre est donc le nombre d'entiers non-nuls inférieurs à \(n\) et premiers avec \(n\).

La fonction \(\varphi:\N^*\rightarrow\N\) définie par \[\varphi(n)=\#(\Z/n\Z)^\times.\] est appelée indicatrice d'Euler.*Leonhard Euler était un mathématicien Suisse du 18ème siècle. D'après l'étude précédente, on sait que \(\varphi(n)\) est le nombre d'entiers de l'intervalle \(\llbracket 1,\,n\rrbracket \) premiers avec \(n\).

L'étude des propriétés du groupe multiplicatif \((\Z/n\Z)^{\times}\) est difficile, nous ne l'aborderons pas en première année en tant que tel, si ce n'est implicitement dans la dernière section. Notons simplement que dans le cas où \(n\) est premier, ce groupe est cyclique mais il n'est pas aisé de trouver des générateurs de ce groupe en général.

Soit \(n\) et \(a\) deux entiers tels que \(n > 0\) et \((a,n)=1\). Alors \begin{equation}\label{eq:ideuler} a^{\varphi(n)}\equiv 1\pmod n. \end{equation}
Soit un entier strictement positif et \(a\) un entier premier avec \(n\). Considérons l'application \(f:(\Z/n\Z)^\times\rg(\Z/n\Z)^\times\) définie par \(x\mapsto ax\). Comme \((a,n)=1\), l'entier \(a\) admet un inverse \(a^{-1}\) et l'équation \(ax=ax'\) devient \(a^{-1}ax=a^{-1}ax'\) ce qui entraîne \(x=x'\). L'application \(f\) est donc injective et par conséquent bijective (cf. théorème). On peut alors procéder à une réindexation pour écrire \begin{align*} {\color{#88F}\prod_{x\in (\Z /n\Z )^{\times }}x} &=\prod_{x\in (\Z /n\Z )^{\times }}ax\\ &=\left(\prod_{x\in (\Z /n\Z )^{\times }}a\right)\left(\prod_{x\in (\Z /n\Z )^{\times }}x\right)\\ &=a^{|(\Z /n\Z )^{\times }|}\left(\prod_{x\in (\Z /n\Z )^{\times }}x\right)\\ &=a^{\varphi(n)}\left({\color{#88F}\prod_{x\in (\Z /n\Z )^{\times }}x}\right) \end{align*} Le produit d'éléments inversibles étant inversible, il suffit de multiplier les deux côtés de la dernière égalité par l'inverse de ce produit pour conclure.
Soit \(p\) un nombre premier et \(a\) un entier relatif qui n'est pas mul­ti­ple de \(p\). Alors \begin{equation} a^{p-1}\equiv 1\pmod p. \end{equation}
Puisque \(p\) est premier, tous les entiers naturels non-nuls strictement inférieurs à \(p\) ont premiers avec \(p\), il y en \(p-1\) donc \(\varphi(p)=p-1\).
Ce dernier résultat s'énonce de manière équivalente : Si \(p\) est un nombre premier et \(a\) est un entier quelconque, alors \(a^p-a\) est un multiple de \(p\). On peut démontrer ce théorème comme un résultat autonome et non pas comme une conséquence du théorème d'Euler et ceci de plusieurs façons.
Soit \(p\) un entier naturel tel que \(p\geq 2\), \(A\) un alphabet fini de cardinal \(a\) et \(M\) l'ensemble des mots définis sur \(A\) de longueur \(n\) et qui contiennent au moins deux symboles distincts. Vérifiez que \begin{equation} \#M=a^n-a. \end{equation}

Soit \(s\in\ab{0}{n-1}\). On définit la fonction \(\rho_s:A^n\rg A^n\) dite de permutation circulaire de \(s\) positions par

\begin{equation} \label{eq:circ} \rho_s(u_0u_1\ldots u_{n-1}):=u_{s}u_{s+1}\ldots u_{n-1}u_0u_1\ldots u_{s-1}. \end{equation}

Par exemple \(\textit{arc}=\rho_1(\textit{car})\). Démontrez que si \(p\) est un nombre premier alors \(\rho_s(u)=u\) où \(u=u_0u_1\ldots u_{n-1}\) si et seulement si \(s=0\) ou alors tous les symboles de \(u\) sont égaux. En déduire que les \(p\) permutés circulaires d'un mot \(u\in M\) sont tous distincts. Indication : déduire de \((\ref{eq:circ})\) que \(\forall i\in\ab{0}{p-1}\) et \(\forall k\in\N\), \(u_{i+ks\pmod p}=u_i\) puis utilisez la proposition qui affirme que tout nombre entier non-nul engendre le groupe additif \((\Z/p\Z,+)\).

Démontrez ensuite que la relation binaire définie sur \(M\) par \(u{\rel}v\) si et seulement s'il existe \(s\in\ab{1}{p-1}\) tel que \(v=\rho_s(u)\) est une relation d'équivalence et que toute classe d'équivalence est de cardinal \(p\). En utilisant le principe des Bergers pour la surjection canonique, montrez que \(p\mid \#M\).

Le théorème des restes chinois

Que se passe-t-il si on mélange les congruences ? Une bande de \(17\) pirates possède un trésor en pièces d'or. Ils projettent de le partager et de donner le reste au cuisinier chinois qui recevrait \(3\) piè­ces. Au moment du partage, comme de bien entendu, les pirates se querellent et \(6\) sont tués. Un nou­veau partage donnerait \(4\) pièces au cuisinier. Mais l'affaire se gâte de nouveau car une tempête fait chavirer leur bâteau et il ne reste que 6 pirates et leur butin ainsi que le (chanceux) cuisinier qui re­ce­vrait alors 5 pièces d'or. Quel butin pourra récupérer le cuisinier s'il empoisonne les 6 autres sur­vi­vants ?

Si l'on note \(n\) la valeur du butin en nombre de pièces d'or, ce problème se traduit par le système de cong­gruen­ces suivant : \begin{equation} \label{eq:butin} \begin{cases} n\equiv 3\ (\text{mod}\ 17)\\ n\equiv 4\ (\text{mod}\ 11)\\ n\equiv 5\ (\text{mod}\ 6)\\ \end{cases} \end{equation}

On vérifie facilement que si l'on se donne une famille d'anneaux \((A_i)_{i\in I}\) et que l'on munit \(A\), l'en­semb­le produit des \(A_i\), des lois produits, alors \((A,+,\times)\) est un anneau, de surcroît commutatif si tous les \(A_i\) le sont. On l'appelle l'anneau produit des \(A_i\). Chacune des projections \(p_i\) est un mor­phis­me d'an­neaux surjectif.

Ici nous allons considérer une famille \((n_i)_{i\in\ab{1}{k}}\) de \(k\) entiers naturels non-nuls et premiers entre eux pour constituer la famille \((\Z/n_i\Z)_{i\in\ab{1}{k}}\) et l'anneau produit. Le théorème des restes chinois montre que cet anneau produit est isomorphe à l'anneau \(\Z/n\Z\) si \(n\) désigne le produit des \(n_i\), autrement dit on peut calculer indifféremment sur des entiers modulo \(n\) ou sur le \(k\)-uplet des restes modulo \(n_i\) de cet entier.

Soit \((n_i)_{i\in\llbracket 1,\,k\rrbracket })\) une famille de \(k\) entiers naturels non-nuls et premiers entre eux et soit \(n\) leur produit. L'application \begin{align} \label{eq:isoprod} \phi:\Z/n\Z&\longrightarrow (\Z/n_1\Z)\times(\Z/n_2\Z)\times\cdots\times(\Z/n_k\Z)\\ \notag x&\longmapsto (x\ \text{mod}\ n_1,\;x\ \text{mod}\ n_2,\ldots,\;x\ \text{mod}\ n_k), \end{align} est un isomophisme d'anneaux.
On vérifie facilement que \(\phi\) est un morphisme d'anneaux. D'autre part, les deux ensembles ont même cardinal puisque le cardinal du produit cartésien est le produit des cardinaux (cf. ce corollaire). Il suffit de démontrer que \(\phi\) est injectif pour prouver qu'il est bijectif, autrement dit il suffit ici de prouver que son noyau est réduit à \(\{0\}\) (cf. ce théorème). Un élément \(x\in\Z/n\Z\) a pour image le \(k\)-uplet \((0,0,\ldots,0)\) s'il est un multiple de chacun des \(n_i\), autrement dit s'il est multiple de leur produit puisque les \(n_i\) sont premiers entre eux.

Si les entiers \(n_i\) ne sont pas premiers entre eux, il ne s'agit plus que d'une injection et un \(k\)-uplet \((r_i)_{i\in\ab{1}{k}}\) n'admet un antécédent que si \((n_i,n_j)\mid(r_i-r_j)\) pour tout couple \((i,j)\in\ab{1}{k}^2\).

Soit \((n_i)_{i\in\llbracket 1,\,k\rrbracket }\) une famille de \(k\) entiers naturels non-nuls et premiers entre eux et \(n\) leur produit. Alors pour toute famille \((r_i)_{i\in\llbracket 1,\,k\rrbracket )}\) d'entiers de \(\Z/n\Z\), le système d'équations \begin{equation} \label{eq:resteschinois} \forall i\in\llbracket 1,\,k\rrbracket \quad x\equiv r_i\ (\text{mod}\ n_i) \end{equation} admet une unique solution dans \(\Z/n\Z\).
Il n'y a rien à prouver, le corollaire exprime simplement le fait que l'isomorphisme étant une bijection, tout élément de l'ensemble d'arrivée admet un unique antécédent.

Ce que nous cherchons quand nous voulons résoudre un système de congruences comme le problème du cuisinier chinois \((\ref{eq:butin})\) c'est l'isomorphisme réciproque \(\phi^{-1}\) de l'isomorphisme \(\phi\) pour calculer \(\phi^{-1}(3,4,5)\) et le théorème que nous venons d'établir ne fournit aucun moyen effectif de le calculer.

Notons \(\tilde{n_{i}}:=n/n_i\). Cet entier est premier avec \(n_i\) puisque les \(n_i\) sont premiers entre eux, il est donc inversible modulo \(n_i\) (cf. ce théorème). On calcule alors son inverse en appliquant l'algorithme d'Euclide étendu pour obtenir les deux coefficients \((u,v)\) de l'identité de Bézout :

\begin{align} \tilde{n_{i}}.u+n_i.v=1. \end{align}

et on réduit modulo \(n_i\) ce qui nous donne

\begin{align} \tilde{n_{i}}.u\equiv 1\ (\text{mod}\ n_i). \end{align}

donc \(u\) est l'inverse modulo \(n_i\) de \(\tilde{n_i}\), on le note \(\mu_i\). On définit alors l'entier

\begin{equation} x:=\sum_{i=1}^k{\color{#F44}\tilde{n_i}}.{\color{#88F}\mu_i}.r_i\ (\text{mod}\ n). \end{equation}

Il nous reste à vérifier que cet entier \(x\) est bien solution de l'équation \((\ref{eq:resteschinois})\). Si l'on calcule modulo \(n_i\) seul le terme \(\mu_i.\tilde{n_i}.r_i\) d'indice \(i\) est non-nul puisque tous les autres termes de cette somme sont des multiples de \(n_i\). Or \(\mu_i.\tilde{n_i}.r_i=r_i\) puisque \(\mu_i.\tilde{n_i}\equiv 1\ \text{mod}\ n_i\).

Nous allons enfin savoir quel est le montant de ce butin que va récupérer le cuisinier chinois… On ré­ca­pi­tu­le :

\begin{align*} n&=17.11.6=1\,122,\\ n_1&={\color{#FF8}17} & {\color{#F44}\tilde n_1}&=11.6={\color{#F44}66} & r_1&=3,\\ n_2&={\color{#FF8}11} & {\color{#F44}\tilde n_2}&=17.6={\color{#F44}102} & r_2&=4,\\ n_3&={\color{#FF8}6} & {\color{#F44}\tilde n_3}&=17.11={\color{#F44}187} & r_3&=5. \end{align*}

Il suffit d'utiliser le programme plus haut pour nous fournir les 3 couples \(({\color{#88F}u},v)\) de l'identité de Bézout pour les trois calculs de pgcd \(({\color{#F44}66},{\color{#FF8}17})\), \(({\color{#F44}102},{\color{#FF8}11})\) et \(({\color{#F44}187},{\color{#FF8}6})\) : \begin{align*} {\color{#F44}66}.{\color{#88F}8}+{\color{#FF8}17}.(-31)&\equiv 1\ (\text{mod}\ n) &\Rightarrow& & {\color{#88F}\mu_1}&={\color{#88F}8},\\ {\color{#F44}102}.{\color{#88F}4}+{\color{#FF8}11}.(-37)&\equiv 1\ (\text{mod}\ n) &\Rightarrow& & {\color{#88F}\mu_2}&={\color{#88F}4},\\ {\color{#F44}187}.{\color{#88F}1}+{\color{#FF8}6}.(-31)&\equiv 1\ (\text{mod}\ n) &\Rightarrow& & {\color{#88F}\mu_1}&={\color{#88F}1}. \end{align*} Et on peut calculer le butin \(x\) : \begin{align*} x&:={\color{#F44}66}.{\color{#88F}8}.3 + {\color{#F44}102}.{\color{#88F}4}.4 + {\color{#F44}187}{\color{#88F}1}.5\\ &= 4\,151,\\ &\equiv \boxed{785}\ (\text{mod}\ 1\,122). \end{align*}

Nous admettrons le corollaire suivant :

Soit \((n_i)_{i\in\llbracket 1,\,k\rrbracket }\) une famille de \(k\) entiers naturels non-nuls et premiers entre eux et \(n\) leur produit. Soit \(\phi\) l'isomorphisme définit en \((\ref{eq:isoprod})\). Alors \((\Z/n\Z)^\times\) est isomorphe à \begin{equation} \prod_{i\in\ab{1}{k}}(\Z/n_i\Z)^\times. \end{equation}
Soit \(n\in\N\) et \(\prod_{i=1}^kp_i^{r_i}\) sa décomposition en produit de facteurs premiers crois­sants. Alors \begin{equation} \varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right). \end{equation}
Par définition, l'indicateur d'Euler est le nombre d'entiers \(p\) premiers avec \(n\) tels que \(1\leq p\leq n\). Le corollaire 2 montre que \begin{equation*} \varphi(n)=\prod_{i=1}^k\varphi(p_i^{r_i}). \end{equation*} Un entier \(p\) tel que \(1\leq p < p_i^{r_i}\) n'est pas premier avec \(p_i^{r_i}\) si et seulement s'il est multiple de \(p_i,\) autrement dit sous la forme \(mp_i.\) On a donc \(mp_i \leq p_i^{r_i}\), soit \(m \in\ab{1}{p^{r_i-1}}\). Finalement \begin{align*} \varphi(n)&=\prod_{i=1}^k\left(p_i^{r_i}-p_i^{r_i-1}\right),\\ &=\prod_{i=1}^kp_i^{r_i}\left(1-\frac{1}{p_i}\right),\\ &=n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right),\\ &=n\prod_{\scriptstyle p\ \text{premier}\atop\scriptstyle p\mid n}\left(1-\frac{1}{p}\right). \end{align*}
Alice et Bob surveillent un examen de I23 qui se déroule de 14h00 à 17h00. Alice s'est couchée trop tard la veille et somnole quelques secondes toutes les 28 minutes tandis que Bob regarde sa montre tous les quarts d'heure car les surveillances d'examens l'ennuient. Les étudiants ont vu Alice bailler à 14h08 la première fois, alors que Bob a regardé sa montre dès 14h02.
  1. Si \(t\) désigne le temps écoulé en minutes depuis le début de l'épreuve, quelle congruence satisfait \(t\) pour correspondre aux moments d'inattention d'Alice ? de Bob ?
  2. Justifiez, sans faire de calculs, l'existence de solutions au système de congruences ci-dessus.
  3. À quelle(s) heure(s) les étudiants peuvent-ils espérer communiquer entre-eux sans être remarqués par les deux surveillants ?

Le protocole RSA

Le protocole RSA est une application ingénieuse du théorème d'Euler. Bob veut envoyer un message secret à Alice et ils procèdent de la manière suivante : Alice choisit deux nombres premiers \(p\) et \(q\) (avec des centaines de chiffres) et calcule leur produit \(n:=p\,q\). Elle choisit alors un entier \(e\) dont le nombre de chiffres est sensiblement le même que celui de \(n\) et qui doit être premier avec \(\varphi(n)\). Puisque \(p\) et \(q\) sont des nombres premiers, il est aisé de vérifier que \(\varphi(n)=(p-1)(q-1)\). Alice construit ensuite l'inverse de \(d\) modulo \(\varphi(n)\), c'est-à-dire l'entier \(d\) tel que \begin{equation}\label{eq:inverses} e\,d\equiv 1\pmod{\varphi(n)}. \end{equation} Elle divulgue alors sa clé publique \((n,\,e)\) et cache sa clé secrète \((p,\, q,\, d)\). Bob encode tout d'abord son message sous forme de nombre entier \(x\) tel que \(0\leq x < n\) (il suffit par exemple de considérer l'entier \(x\) dont la décomposition en base deux est la suite des bits des codes utf-8 des lettres composant le texte). Si la chaîne de caractères est trop longue pour satisfaire \(x < n\), on la segmente en sous-chaînes plus courtes et on applique le processus que nous allons étudier à chacune des sous-chaînes.

Bob calcule alors le reste de la division euclidienne de \(x^e\) par \(n\) : \begin{equation}\label{eq:encryption} y\equiv x^{e}\ (\text{mod}\ n). \end{equation} et envoie \(y\) à Alice.

Alice retrouve le message initial en calculant \(y^d\ (\text{mod}\ n)\), soit \(x^{ed}\ (\text{mod}\ n)\) grâce à (\ref{eq:encryption}). D'après l'équation (\ref{eq:inverses}), il existe un entier \(k\) tel que \(ed=k\,\varphi(n)+1\) donc

\begin{align*} x^{ed} &\equiv x\,.\,x^{k\,\varphi(n)} \ (\text{mod}\ n)\\ &\equiv x\,.\,{\left(x^{\varphi(n)}\right)}^k\ (\text{mod}\ n)\\ &\equiv x\,.\,1^k\ (\text{mod}\ n)\quad\text{d'après (\ref{eq:ideuler})}\\ &\equiv x\ (\text{mod}\ n). \end{align*}

Ce protocole pose un grand nombre de problèmes algorithmiques. Le premier est de pouvoir réaliser des opérations avec des nombres entiers de plusieurs centaines de chiffres, une simple calculatrice ne peut évidemment pas le faire. Comment trouver des nombres premiers \(p\) et \(q\) aussi grands ? Comment calculer des puissances de nombres entiers aussi grandes ? Ce protocole est-il sûr ? Ces questions seront abordées en algorithmique et en cryptographie.

Malgré le développement d'algorithmes particulièrement efficaces, tous ces calculs restent malgré tout coûteux. Ce protocole est généralement utilisé, non pas pour chiffrer un message, mais pour transmettre une clef d'un protocole à clef secrète beaucoup moins gourmand en calculs. Ainsi Bob transmet une clef secrète \(k\) à Alice via le protocole à clef public rsa et tous les deux vont utiliser un autre protocole, à clef secrète cette fois, qui utilise la clef \(k\) pour chiffrer les messages.

Annexe : matrices

Le calcul matriciel désigne l'ensemble des techniques de calcul pour réaliser les opérations usuelles sur les applications linéaires définies sur des espaces vectoriels de dimension finie.

Pour ceux qui n'auraient pas encore rencontré de matrice \(\ell\times c\) où \((\ell,c)\in\N^2\), il s'agit en première approche d'une simple famille \(M\) d'éléments d'un anneau indexée par un produit d'intervalles \(\ab{1}{\ell}\times\ab{1}{c}\). Au lieu de représenter les éléments notés \(M_{(i,j)}\) ou encore \(M[i][j]\) de cette liste en séquence, on les représente dans une table de \(\ell\) lignes et \(c\) colonnes. La \(i\)-ème ligne contient la liste de tous les éléments de premier indice \(i\), la \(j\)-ème colonne contient la liste de tous les éléments de deuxième indice \(j\) (nous avons placé les indices en lieu et place des éléments de la matrice) : \begin{align*} M=\begin{pmatrix} (1,1) & (1,2) & \cdots & (1,{\color{#88F}j}) & \cdots & (1,c)\\ (2,1) & \cdots & & {\color{#88F}\vdots} & & (2,c) \\ (3,1) & \cdots& & {\color{#88F}\vdots} & & \vdots\\ \vdots & & & {\color{#88F}\vdots} & & \\ ({\color{#FF8}i},1) &{\color{#FF8}\cdots} &{\color{#FF8}\cdots} & ({\color{#FF8}i},{\color{#88F}j}) & {\color{#FF8}\cdots} & ({\color{#FF8}i},c)\\ \vdots & & & {\color{#88F}\vdots} & & \vdots \\ (\ell,1) &\cdots & & (\ell,{\color{#88F}j}) & \cdots & (\ell,c) \end{pmatrix} \end{align*}

La structure matricielle est plus pratique qu'une simple étagère de rangement, on peut ad­di­tion­ner et multiplier des ma­tri­ces et même multiplier des matrices par des nombres.

Pour l'addition c'est très simple, il faut que les matrices aient exactement le même nombre de lignes et de colonnes et il suffit d'additionner les \(\ell\times c\) éléments de chaque matrice terme-à-terme, par exemple : \begin{align*} \begin{pmatrix} 1&2\\ -5&1 \end{pmatrix} + \begin{pmatrix} -1&1\\ 2&3 \end{pmatrix} = \begin{pmatrix} 1-1&2+1\\ -5+2&1+3 \end{pmatrix} = \begin{pmatrix} 0&3\\ -3&4 \end{pmatrix} . \end{align*} Pour la multiplication, c'est plus compliqué car on peut multiplier des matrices \(G\) et \(D\) de di­men­sions différentes. On note \(\ell_g\) et \(c_g\) (resp. \(\ell_d\) et \(c_d\)) le nombre de lignes et de colonnes de la matrice \(G\) (resp. \(D\)). Il faut que \(c_g=\ell_d\) et la matrice résultat \(R:=G\times D\) contiendra \(\ell_g\) lignes et \(c_d\) colonnes. Le terme \(R[i][j]\) s'obtient en faisant le produit scalaire de la ligne \(i\) par la colonne \(j\), c'est-à-dire la somme des produits terme-à-terme des éléments de ces deux sous-listes dans le sens de lecture, par exemple \[(1,2,3).(2,-3,4)=1.2+2.(-3)+3.4=8.\]

Exemple : \begin{align*} \begin{pmatrix} \color{#88F}1&\color{#88F}0\\ -5&1\\ 2&-1 \end{pmatrix} \times \begin{pmatrix} -1&\color{#FF8}1\\ 2&\color{#FF8}3 \end{pmatrix} = \begin{pmatrix} (1,0).(-1,2) & {\color{#88F}(1,0)}.{\color{#FF8}(1,3)}\\ (-5,1).(-1,2) & (-5,1).(1,3)\\ (2,-1).(-1,2) & (2,-1).(1,3) \end{pmatrix} = \begin{pmatrix} -1&\boxed{1}\\ 7&-2\\ -4&-1 \end{pmatrix} . \end{align*} Le terme d'index \((\color{#88F}1,{\color{#FF8}2})\) de la matrice résultat est le produit scalaire de la ligne 1 de la matrice à gauche avec la colonne 2 de la matrice à droite. La multiplication d'une matrice \(M\) de dimension \(\ell\times c\) par un nombre fournit une matrice de même dimension dont chaque terme est le produit par ce nombre du terme correspondant de la matrice \(M\). Par exemple : \begin{equation*} (-2).\begin{pmatrix} 2 & 0\\ -1 & 4 \end{pmatrix} =\begin{pmatrix} -4 & 0\\ 2 & -8 \end{pmatrix}. \end{equation*} On a en particulier \begin{align*} \begin{pmatrix} a & b\\ c & d \end{pmatrix} \times \begin{pmatrix} a' & b'\\ c' & d' \end{pmatrix} &= \begin{pmatrix} aa'+bc' & ab'+bd'\\ ca'+dc' & cb'+dd' \end{pmatrix},\\ \begin{pmatrix} a & b\\ c & d \end{pmatrix} \times \begin{pmatrix} u\\ v \end{pmatrix} &= \begin{pmatrix} au+bv\\ cu+dv \end{pmatrix}. \end{align*}

Le cours d'algèbre linéaire de la deuxième année présentera ces notions calculatoire en détail.

Travaux pratiques

En séance

On rappelle que le quotient (resp. le reste) de la division euclidienne de \(a\) par \(b\) s'écrit a // b (resp. a % b) en Python.

Écrivez une fonction Chiffrer(clair,clef) en Python qui renvoie le chiffré du texte clair avec le chiffrement de César suivant la clef donnée. Indication : utilisez les fonctions ord et chr qui renvoient respectivement le code d'un symbole et le symbole associé à un code. On supposera que le texte clair est exclusivement constitué de majuscules. Comment utiliser cette même fonction pour déchiffrer un texte ?
Écrivez une fonction Cribler(N) en Python qui réalise le crible d'Eratosthène sur les entiers inférieurs à une valeur \(N\) saisie par l'utilisateur et renvoie la liste des nombres premiers inférieurs ou égaux à \(N\) (sous forme de tuple). Quel est le 2018-ème nombre premier ?
Écrivez une fonction Factoriser(N) en Python qui renvoie la liste croissante des facteurs premiers de \(N\) sous forme de tuple.
Écrivez un script Table(n,op) en Python qui renvoie la table d'addition (resp. de multiplication) si op == "+" (resp. op == "*") de \(\Z/n\Z\) sous forme de tuple de tuples. Vous utiliserez la procédure suivante pour les afficher :
def AfficheTable(T):
   for ligne in T:
      for x in ligne:
         print(str(x).rjust(3),end='')
      print()     
Écrivez une fonction mod9(N) en Python qui calcule l'image d'un entier naturel dans \(\Z/9\Z\) en utilisant le critère de divisibilité par \(9\) et pas la division euclidienne par \(9\).
Écrivez une fonction Euclide(a,b) en Python script qui renvoie un couple \((u,v)\) solution de l'identité de Bézout pour \(d:=(a,b)\) en utilisant l'algorithme d'Euclide étendu.

Compléments hors séance

Le langage Python dispose du type int qui code des entiers de taille arbitrairement grande. Écrivez un script qui réalise le chiffrement rsa. Vous écrirez une fonction Chiffrer(x,e,n) et une fonction Dechiffrer(y,d,n).