Arithmétique
\(\def\lf{\leftarrow}\def\rg{\rightarrow}\def\iff{\Leftrightarrow}\def\rel#1{\,{\mathscr #1}\,}\def\N{{\mathbb N}}\def\Z{{\mathbb Z}}\def\Q{{\mathbb Q}}\def\R{{\mathbb R}}\)

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.

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\}.\) On suppose que \(\alphabet\) est muni de l'ordre al­pha­bé­ti­que \(\preceq\). On considère la bijection \(f:[1,n]\rightarrow\alphabet\) définie par \[f(i):=i\text{-ème lettre de l'alphabet.}\] Montrez qu'il s'agit d'un isomorphisme d'ensembles ordonnés. En identifiant \(\alphabet\) à l'intervalle \([1,26]\), montrez que le chiffrement de César avec un décalage circulaire de \(k\) lettres est une permutation de \(\def\Sn{{\mathfrak S}}\Sn_{26}\), Quelle est sa dé­com­po­si­tion en produit de cycles à supports disjoints ?
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.

Soient \((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{#FF0}ak}={\color{#FF0}b}\) et si \({\color{#FF0}b}\mid c\), il existe \(l\in\Z\) tel que \({\color{#FF0}b}l=c\), donc \(({\color{#FF0}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é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\).

Soient \(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 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'\).
La somme des âges (non-nuls) de trois frères est égal à \(39\), l'ainé a deux fois l'âge du cadet. Quel est l'âge des trois frères ? Indication : ne pas faire une étude de cas, mais utiliser la division euclidienne en remarquant que l'âge du frère intermédiaire est égal à \(q+r\) si \(q\) désigne l'âge du cadet.

Ce théorème extrêmement intuitif (après tout, il ne s'agit que de partager \(a\) bonbons avec \(b\) amis) est un résultat très profond utilisé au sein de nombreuses démonstrations. C'est un théorème central en ari­thmé­ti­que. Mais 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.
Par l'absurde. Supposons qu'il existe un nombre fini \(n\) de nombres premiers, 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[1,n]\), le reste de la division euclidienne de \(p\) par \(p_i\) est égal à \(1\), autrement dit \(\forall i\in[1,n]\ 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'algorithme va éliminer (cribler) tous les nombres de cette liste qui ne sont pas premiers. On initialise 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 ← 2
TANT QUE (p2 ≤ N): 
   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
RETOURNER 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{#FF0}p}\) utilisés dans la boucle qui crible leurs multiples (instructions #13 à #15).

Démontrez qu'à la sortie de la boucle de la ligne 9, le nombre \(p\) est un nombre premier. Pourquoi peut-on arrêter la boucle dès que \(p^2 > N\) ?
Écrivez un programme Python qui réalise le crible d'Eratosthène sur les entiers inférieurs à une valeur \(N\) saisie par l'utilisateur. Quel est le 2018-ème nombre premier ?

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

\begin{align*} n=\prod_{i=1}^{k}n_i, \end{align*}

alors on dit que \((n_i)_{i\in[1,k]}\) est une décomposition en produit de facteurs croissants de \(n\). Une telle décomposition existe toujours, il suffit de prendre la séquence constitué du seul entier \(n\) si \(n > 1\) et de considérer la séquence vide pour \(n=1\) puisque par convention, le produit d'une famille vide est toujours égal à l'élément neutre pour la loi multiplicative considérée, donc 1 ici. Notons qu'un entier naturel peut admettre plusieurs décompositions en produit de facteurs croissants :

\begin{align*} 18&=3\times 6,\\ &=2\times3\times 3,\\ &=2\times 9. \end{align*}
Tout entier naturel \(n\) se dé­com­po­se de ma­niè­re unique en produit de facteurs premiers croissants.
C'est vrai pour \(n=1\) car par convention le produit vide est égal à \(1\) et si \(n\) est premier, il n'y a rien à prouver. Supposons donc que \(n\) ne soit pas un nombre premier. Dans ce cas l'ensemble des diviseurs de \(n\) \[\{d\in]1,n[\ \mid\ d\mid 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[1,k]\times[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. 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\) ?
Écrivez un programme Python qui décompose un nombre entier saisi par l'utilisateur en produit de facteurs premiers croissants.

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}

Les sous-groupes de \((\Z,+)\) sont formés par les ensembles \(n\Z\).
D'après la caractérisation des sous-groupes, pour montrer que \((n\Z,+)\) est un sous-groupe de \((\Z,+)\), il suffit de montrer que \(n\Z\) est une partie stable pour l'addition, que \(0\in n\Z\) et que l'opposé \((-k)\) d'un élément \(k\in n\Z\) appartient à \(n\Z\). L'addition de deux entiers multiples de \(n\) est encore un multiple de \(n\), \(n\Z\) est donc une partie stable pour l'addition. L'entier \(0\in n\Z\), puisque \(0=n.0\). D'autre part, si \(k\in n\Z\), c'est qu'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 lui ou son opposé est strictement positif, donc \(H\) contient des entiers strictement positifs. L'ensemble \(H\cap\N^*\) est donc une partie non-vide de \(\N\) et admet donc un plus petit entier d'après la première propriété ca­rac­té­ris­ti­que d'un ensemble naturel, on le note \(n\). Comme \(\{n\}\subseteq H\), le sous-groupe de \(\Z\) engendré par \(n\), c'est-à-dire \(n\Z\) vérifie \(n\Z\subseteq H\).

Pour tout \(x\in H\), montrons que \(x\in n\Z\). La division euclidienne nous donne \(x=qn+r\) avec \(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 de \(H\), or \(r < n\) donc \(r=0\) et \(x\in n\Z.\) Fi­na­le­ment \(H\subseteq 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.\)

Soit \(n\in\N\). La relation de congruence modulo n définie sur \(\Z\) par \begin{equation} \label{eq:congruence} \big(x\equiv y\ (\text{mod}\ n)\big)\ \Leftrightarrow\ \big(y-x\in n\Z.\big) \end{equation}

est 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 additive sur \(\Z\).

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. Utilisez la division euclidienne pour calculer quel jour de la semaine était le 273-ème jour de cette année.
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\) et \((k,n)=1\), i.e. tels que \(k\) et \(n\) sont 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\).

Écrivez un programme Python qui dresse la table d'addition de \(\Z/n\Z\) en demandant la saisie de l'entier \(n\) à l'utilisateur. 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.

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\).

D'après ce théorème nous savons que l'ordre de chaque entier de \(0\) à \(9\) divise \(9\) dans \(\Z/9\Z\). La proposition 9 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.

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 composition 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*(*) Donc si \((A\setminus\{0\},\times)\) est un groupe puisqu'il est déja as­so­cia­tif et unifè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} Si \(A\) n'admet pas de diviseurs de \(0\) il est dit anneau intègre.

Nous serons confronté à des anneaux qui ne sont pas intègres dans la suite du chapitre. Dans un anneau intègre, comme \(\Z\) par exemple, on a

\begin{equation} ab=0\Rightarrow (a=0)\wedge(b=0). \end{equation}
Dans un anneau \((A,+,\times)\), l'ensemble des éléments inversibles est stable pour la multiplication, c'est un groupe dont l'élément neutre est \(1\), on le note \(A^\times\) et on l'appelle groupe des inversibles de l'anneau \(A\).

En effet, la multiplication dans un anneau \(A\) est associative et on sait (cf. Proposition 2) 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 :

Soient \((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 multiplication.

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) 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'\).

Nous savons que les groupes quotients \((\Z/n\Z,+)\) ont été obtenus comme quotient de \(\Z\) pour les seules relations d'équivalences compatibles avec l'addition, à savoir \(x\rel{R}x'\iff x-x'\in n\Z\) où \((n\Z,+)\) est un sous-groupe (nécessairement normal) de \((\Z,+)\). Cette relation est-elle compatible avec la mul­ti­pli­ca­tion ? C'est-à-dire

\[\forall y\in A\quad x\rel{R}x'\overset{?}{\Rightarrow} xy\rel{R}x'y.\]

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{R}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 à présent un morphisme d'anneaux.

Le noyau \(\text{Ker}(\varphi)\) est l'ensemble \(n\Z\) des multiples de \(n\).
On a \(\text{Kef}(\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 générateurs 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 gé­né­ra­teurs de son 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 ?
Écrivez un programme Python qui dresse la table de multiplication de \(\Z/n\Z\) et affiche les éléments de \(\Z/n\Z^\times\) en demandant la saisie de l'entier \(n\) à l'utilisateur.

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} Ce calcul est faux bien sûr, et l'argument le plus simple pour s'en convaincre est que la somme de deux nombres pairs 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. \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\\ 0&=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 plongeant ce calcul 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.

Les multiples représentations des nombres sont étudiées dans un cours d'informatique générale 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\) est la surjection canonique de \(\Z\rg\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\). 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 tous les nombres \(a_i\) vérifient \(0\leq a_i < B\), donc le reste de la division euclidienne de \(a_i\) par \(n\) est égal à \(a_i\), soit \(\varphi_n(a_i)=a_i.\) L'égalité \((\ref{eq:modulon})\) devient

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

Il suffit donc de faire la somme modulo \(n\) des chiffres qui constituent le nombre pour calculer son reste modulo \(n\). Reprenons l'exemple \((\ref{eq:sample})\) en base \(B=10\) :

\begin{align*} \varphi_{10}(121)+\varphi_{10}(4195)&=\varphi_{10}(4237)\\ ({\color{#88F}1+2+1})+(4+1+9+5)&=(4+2+3+7)\\ 4+19&=16\\ 4+10&=7\\ 4+1&=7\\ 5&=7. \end{align*}

Notons que le même procédé de vérification pour l'égalité \(123+4195=4237\) (on a remplacé 121 par 123) aurait échoué puisque \({\color{#88F}1+2+3}\equiv 6\ \text{mod}\ 10\). La preuve par 9 ne permet pas de prouver qu'une opération a été effectuée correctement mais permet parfois de prouver 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\).
Écrivez un script en Python qui réalise le chiffrement de César. Indication : utilisez les fonctions ord et chr. Quelles sont les propriétés mathématiques de ces deux fonctions ?

Algorithme d'Euclide, identité de Bezout

PGCD, algorithme d'Euclide.

Donnons nous \(a\) et \(b\) deux entiers relatifs dont l'un au moins n'est pas nul, nous supposerons qu'il s'agit de \(a\). L'ensemble \(D_a\) des diviseurs de \(a\) est majoré par \(\abs{a},\) et son intersection avec \(D_b\) est l'ensemble de diviseurs de \(b\) (qui peut-être égal à \(\Z\) si \(b=0\)) est incluse dans \(D_a\) et admet donc \(\abs{a}\) pour majorant. D'autre part \(D_a\cap D_b\not=\varnothing\) puisque \(1\mid a\) et \(1\mid b\), il admet donc un plus grand élément.

Soient \(a\) et \(b\) deux entiers relatifs dont l'un au moins n'est pas nul. Le plus grand commun diviseur de \(a\) et \(b\) est 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.

Notons que l'on ne peut définir le pgcd de deux entiers relatifs nuls, puisque l'ensemble de leurs diviseurs commun est \(\Z\) tout entier et il n'admet pas de plus grand élément mais 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ée ici que parce que les valeurs de \(a\) et \(b\) sont 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 continuer 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écessaire. 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 représentation 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 questions 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.

Soient \(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{#FF0}a,b})\). Si \(d\in D(b,a-b)\), alors \(\color{#FF0}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{#FF0}d\mid a\), donc \(d\in D(a,b)\).
Soient \(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\). Mais \(r=a-qb\), donc \(q\) est l'unique entier tel que \(0\leq a-qb < b\), c'est par conséquent le plus grand à satisfaire ces inégalités. Autrement dit \(\forall i\in[1,q[\), \(a-ib \geq b\). On peut donc appliquer \(q\) fois le théorème successivement pour obtenir \((a,b)=(a-qb,b)=(r,b).\)

L'identité \((\ref{eq:pgcdbis})\) suggère un algorithme pour calculer le pgcd de deux entiers \(a\) et \(b.\) Il suffit de l'appliquer jusqu'à ce que le reste de la division euclidienne soit nul, le quotient de cette dernière division constitue alors 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
RETOURNER a

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 un peu plus bas, on ob­tient un couple \((u,v)=\,\) solution de l'identité de Bezout :

.

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.
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 le 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 Bezout

Un idéal \(I\) d'un anneau commutatif \((A,+,\times)\) est appelé idéal principal de \(A\) s'il existe \(n\in A\) tel que \(aA=I\). Si tous les idéaux d'un anneau sont principaux, l'anneau est appelé anneau principal.
L'anneau \(\Z\) est un anneau principal.
Nous savons que les idéaux de \(\Z\) sont du type \(n\Z\).
Soient \(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\).

Soient \(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\).
Soient \((a,b,d)\in\Z^2\times\N\). Alors il existe deux entiers re­la­tifs \(u\) et \(v\) qui satisfont l'identité de Bezout \begin{equation} \label{eq:Bezout} au+bv=d, \end{equation} si et seulement si \((a,b)\mid d\).
Montrons que c'est une condition nécessaire. Soient \(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 Bezout \((\ref{eq:Bezout})\), 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 Bezout \((\ref{eq:Bezout})\). 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. Mais à quoi peut servir l'identité de Bezout ? Une première réponse est fournie par le corollaire suivant dont la preuve est immédiate :

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}

C'est donc un nouveau critère pour déterminer si deux nombres sont premiers entre eux, reste à savoir s'il est plus simple à mettre en œuvre que le calcul du pgcd. Il y a une autre conséquence très importante de ce corollaire sur le calcul modulaire, le calcul d'un inverse modulo \(n\), c'est-à-dire 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. Comment calculer l'inverse de \(x\) ? On peut bien sûr s'appuyer sur la table de multiplication, et chercher où se trouve la valeur \(1\) sur la ligne \(x\). Mais même en ne faisant que la moitié des calculs parce que \(\Z/n\Z\) est commutatif, il faut tout de même \(\frac{n^2}{2}\) opérations. 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 !

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.

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 Bezout 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.

Algorithme d'Euclide étendu

D'après l'identité de Bezout \((\ref{eq:Bezout})\) 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 Bezout \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 va pouvoir construire un couple \((u,v)\) qui satisfait \(au+bv=(a,b)\). Observons la suite des divisions euclidiennes avec leur quotients et restes, effectuées pour obtenir \((192,57)=3\) :

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

Isolons les restes dans chacune de ces identités sauf la dernière, le reste de la dernière division euc­li­dien­ne étant nul, c'est celui de l'avant dernière \((\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 Bezout 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 remplace alors \(\boxed{6\,.\,(-2)}\) dans l'égalité \((\ref{eq:box4})\) par \((15\,.\,{\color{#F62}(-1)}+3)\) et on isole \(3\) à droite pour obtenir l'identité de Bezout \((\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[1,n]}\) 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 Bezout 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 Bezout 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 Bezout 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{#FF0}n}\) suivante :

\begin{equation} \label{eq:regle} R_{\color{#FF0}n}:\qquad(u,v)\lf (v,u-q_{\color{#FF0}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[1,n]}\) 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\).

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
   b ← a MOD b
   Q ← Q + [a DIV b]
   a ← t
i ← #Q
u ← 0
v ← 1
TANT QUE (i > 0):
   t ← u
   u ← v
   v ← t - Q[i] * v
   i ← i - 1
RETOURNER (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.

Soient \(a\) et \(b\) deux entiers relatifs. On désigne par \((q_i)_{i\in[1,n]}\) 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 Bezout : \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}
Écrivez un programme Python qui demande à l'utilisateur de saisir deux nombres entiers relatifs \(a\) et \(b\) et calcule un couple \((u,v)\) solution de l'identité de Bezout pour \(d:=(a,b)\).
Calculez un couple \((u,v)\) solution de l'identité de Bezout 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\).

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. Par exemple, 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 avec un simple mètre et sans équerre. En effet l'égalité \[3^2+4^2=5^2\] 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.

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 identité de Bezout et on sait d'après le théorème de Bezout 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})\). 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 développer l'expression \((\ref{eq:allsol})\) pour s'en convaincre. 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\). Les trois propositions suivantes sont équivalentes :
  1. \(x\in (\Z/n\Z)^\times\),
  2. \(x\) n'est pas un diviseur de 0, i.e. \(\forall y\in\Z/n\Z\ \ x.y=0\Rightarrow y = 0\),
  3. \((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 Bezout, 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\).
Soient \((a,b,c)\in\Z^3\). Alors \begin{equation} \left((a\mid bc)\wedge(a,b)=1\right)\ \Rightarrow\ (a\mid c). \end{equation}
Si \((a,b)=1\), alors d'après identité de Bezout 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[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[1,p-1]\), le théorème de Gauss permet de conclure.

Soient \((a,b)\in\Z^2\) et \(p\) un nombre premier. Alors \begin{equation} p\mid ab\ \Rightarrow (p\mid a)\ \vee\ (p\mid b). \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\), il est noté \(\varphi(n)\). La fonction \(\varphi\) ainsi définie est appelée indicatrice d'Euler.*Leonhard Euler était un mathématicien Suisse du 18ème siècle. L'étude des propriétés de ce groupe multiplicatif est difficile, nous ne l'aborderons pas ici.

Soit \(n\) un entier strictement positif et \(a\) un entier premier avec \(n\), 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\) est \(a\) un entier relatif qui n'est pas mul­ti­ple de \(p\). Alors \begin{equation} a^{p-1}\equiv 1\ (\text{mod}\ 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[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[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{R}v\) si et seulement s'il existe \(s\in[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 nouveau partage donnerait \(4\) pièces au cuisinier. Mais l'affaire se gâte à nouveau car un tempête fait chavirer leur bâteau et il reste 6 pirates et leur butin ainsi que le (chanceux) cuisinier qui recevrait alors 5 pièces d'or. Quel butin pourra récupérer le cuisinier s'il empoisonne les 6 survivants ?

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 d'équations congruentielles 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'ensemble 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 morphisme d'anneaux surjectif.

Ici nous allons considérer une famille \((n_i)_{i\in[1,\,k]})\) de \(k\) entiers naturels non-nuls et premiers entre eux pour constituer la famille \((\Z/n_i\Z)_{i\in[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.

Soient \((n_i)_{i\in[1,k]})\) 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[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[1,\,k]^2\).

Soient \((n_i)_{i\in[1,k]}\) une famille de \(k\) entiers naturels non-nuls et premiers entre eux et \(n\) leur produit. Alors pour toute famille \((r_i)_{i\in[1,k])}\) d'entiers de \(\Z/n\Z\), le système d'équations \begin{equation} \label{eq:resteschinois} \forall i\in[1,k]\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. ). On calcule alors son inverse en appliquant l'algorithme d'Euclide étendu pour obtenir les deux coefficients \((u,v)\) de l'identité de Bezout :

\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}^kr_i.{\color{#88F}\mu_i}.{\color{#F44}\tilde{n_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 \(r_i.\mu_i.\tilde{n_i}\) d'indice \(i\) est non-nul puisque tous les autres termes de cette somme sont des multiples de \(n_i\). Or \(r_i.\mu_i.\tilde{n_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écapitule :

\begin{align*} n&=17.11.6=1122,\\ n_1&={\color{#FF0}17} & {\color{#F44}\tilde n_1}&=11.6={\color{#F44}66} & r_1&=3,\\ n_2&={\color{#FF0}11} & {\color{#F44}\tilde n_2}&=17.6={\color{#F44}102} & r_2&=4,\\ n_3&={\color{#FF0}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 Bezout pour les trois calculs de pgcd \(({\color{#F44}66},{\color{#FF0}17})\), \(({\color{#F44}102},{\color{#FF0}11})\) et \(({\color{#F44}187},{\color{#FF0}6})\) : \begin{align*} {\color{#F44}66}.{\color{#88F}8}+{\color{#FF0}17}.(-31)&\equiv 1\ (\text{mod}\ n) &\Rightarrow& & {\color{#88F}\mu_1}&={\color{#88F}8},\\ {\color{#F44}102}.{\color{#88F}4}+{\color{#FF0}11}.(-37)&\equiv 1\ (\text{mod}\ n) &\Rightarrow& & {\color{#88F}\mu_2}&={\color{#88F}4},\\ {\color{#F44}187}.{\color{#88F}1}+{\color{#FF0}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&:=3.{\color{#88F}8}.{\color{#F44}66} + 4.{\color{#88F}4}.{\color{#F44}102} + 5.{\color{#88F}1}.{\color{#F44}187}\\ &= 4151,\\ &\equiv \boxed{785}\ (\text{mod}\ 1122). \end{align*}

Nous admettrons le corollaire suivant :

Soient \((n_i)_{i\in[1,k]}\) 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[1,\,k]}(\Z/n_i\Z)^\times. \end{equation}
Soient \(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[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 s'appuie sur le théorème d'Euler. Il fonctionne de la manière suivante : Bob veut envoyer un message à Alice. Alice choisit deux nombres premiers \(p\) et \(q\) (avec des centaines de chiffres) et calcule leur produit \(n:=pq\). 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.

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.

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

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 \([1,\ell]\times[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{#FF0}i},1) &{\color{#FF0}\cdots} &{\color{#FF0}\cdots} & ({\color{#FF0}i},{\color{#88F}j}) & {\color{#FF0}\cdots} & ({\color{#FF0}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+0&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{#FF0}1\\ 2&\color{#FF0}3 \end{pmatrix} = \begin{pmatrix} (1,0).(-1,2) & {\color{#88F}(1,0)}.{\color{#FF0}(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{#FF0}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.