Exercices corrigés : l'arithmétique modulaire (201-N11)

a) Pour tout entier $a$ et tout entier $n>0$, il existe un UNIQUE couple d'entiers $(q,r)$ tel que $a=nq+r$ avec $0\leq r<n$. Deux choses comptent dans cet énoncé : l'existence et l'unicité d'une part, et surtout l'ENCADREMENT du reste entre 0 inclus et $n$ exclu. C'est cet encadrement qui interdit un reste négatif, et c'est lui qu'on oublie quand $a<0$.

b) $2026=12\times 168+10$, donc $q=168$ et $r=10$ : c'est ce que montre l'horloge de la figure, où l'on tourne 168 fois avant de s'arrêter sur 10. Pour 7 : $2026=7\times 289+3$, donc $q=289$ et $r=3$. On vérifie toujours en recalculant $nq+r$, ce qui coûte une seconde et attrape toutes les erreurs de table.

c) Pour $-17$ par 5 : le quotient doit être choisi de sorte que le reste tombe dans $[0;5[$. Avec $q=-4$ : $-17=5\times(-4)+3$, donc $r=3$. Le réflexe $-17=5\times(-3)-2$ donnerait $r=-2$, qui n'est pas un reste valide. Pour $-1$ par 12 : $-1=12\times(-1)+11$, donc $r=11$ : c'est le dernier cran de l'horloge avant de repasser par zéro, ce qui est exactement l'image à retenir.

d) En PYTHON, $-17\ \%\ 5$ vaut 3, la convention mathématique, puisque le diviseur 5 est positif. En C et en JAVA, l'opérateur renvoie $-2$, du signe du dividende. Les deux langages calculent correctement, ils ne répondent simplement pas à la même question. Conséquence pratique pour un programmeur : un code d'indexation circulaire écrit en C doit corriger le cas négatif, par exemple avec $((a\ \%\ n)+n)\ \%\ n$, alors que le même code en Python fonctionne tel quel.

e) Les jours de la semaine se comptent modulo 7. $100=7\times 14+2$, donc dans 100 jours on avance de 2 crans : mardi plus 2 donne JEUDI. Il y a 100 jours, on recule de 2 crans : mardi moins 2 donne DIMANCHE. On peut aussi écrire $-100\bmod 7=5$ et avancer de 5, ce qui donne également dimanche, puisque avancer de 5 ou reculer de 2 revient au même sur un cycle de 7.

a) DIVISIBILITÉ : $a\equiv b\pmod n$ signifie que $n$ divise $a-b$. RESTES : cela signifie que $a$ et $b$ ont le MÊME reste dans la division par $n$. Les deux formulations sont équivalentes, et il faut savoir passer de l'une à l'autre : la première sert dans les démonstrations, la seconde dans les calculs.

b) RÉFLEXIVE : $n$ divise $a-a=0$, donc $a\equiv a$. SYMÉTRIQUE : si $n$ divise $a-b$, il divise aussi $b-a=-(a-b)$, donc $b\equiv a$. TRANSITIVE : si $n$ divise $a-b$ et $b-c$, il divise leur somme $(a-b)+(b-c)=a-c$, donc $a\equiv c$. Les trois propriétés font de la congruence une relation d'équivalence, dont les classes sont exactement les $n$ ensembles de nombres ayant le même reste.

c) Par hypothèse $a-b=kn$ et $c-d=\ell n$ pour deux entiers $k$ et $\ell$. SOMME : $(a+c)-(b+d)=(a-b)+(c-d)=(k+\ell)n$, multiple de $n$ ✓. PRODUIT : $ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)=(ck+b\ell)n$, multiple de $n$ ✓. L'astuce du produit consiste à ajouter et retrancher $bc$, ce qui fait apparaître les deux hypothèses ; elle vaut la peine d'être retenue, elle resservira ailleurs.

d) $17\equiv 2\pmod 5$, car $17=5\times 3+2$. La compatibilité avec le produit permet d'élever les deux membres à la puissance 4 : $17^{4}\equiv 2^{4}=16\equiv 1\pmod 5$. Le reste vaut donc 1, alors que $17^{4}=83\,521$, un nombre qu'on n'a jamais eu à écrire. C'est tout l'intérêt du calcul modulaire : on réduit AVANT de multiplier, jamais après.

e) NON, la division n'est pas compatible en général. On a bien $6\equiv 12\pmod 6$, puisque $12-6=6$. En divisant les deux membres par 2 : $3\equiv 6\pmod 6$ serait faux, car $6-3=3$ n'est pas un multiple de 6. La règle correcte est qu'on peut simplifier par $k$ à condition de diviser AUSSI le modulo par $\mathrm{pgcd}(k,n)$, ou bien si $k$ est premier avec $n$. C'est cette restriction qui rend l'exercice 5 sur les inverses nécessaire.

a) La table d'addition modulo 5 s'obtient en additionnant puis en prenant le reste. Sa première ligne, celle de 0, est $0,1,2,3,4$ ; celle de 1 est $1,2,3,4,0$ ; celle de 2 est $2,3,4,0,1$, et ainsi de suite. OUI, chaque ligne contient chaque élément exactement une fois : ajouter un nombre fixé est une permutation, car on peut toujours revenir en arrière en ajoutant l'opposé. C'est vrai pour tout $n$, premier ou non.

b) Vérifications : $3\times 5=15=14+1\equiv 1$ ; $4\times 6=24=21+3\equiv 3$ ; $2\times 4=8\equiv 1$. On observe que CHAQUE LIGNE contient chaque élément non nul exactement une fois, et en particulier qu'elle contient 1. Autrement dit, tout élément non nul possède un INVERSE modulo 7, ce qui n'a rien d'évident et sera le sujet de l'exercice 5.

c) Modulo 6, la ligne de 2 donne $2,4,0,2,4$ pour les multiplicateurs $1,2,3,4,5$ : elle contient un ZÉRO alors qu'aucun des deux facteurs n'est nul, et elle ne contient PAS 1. La ligne de 3 donne $3,0,3,0,3$, encore pire. Seules les lignes de 1 et de 5 contiennent 1. La table est donc très différente de celle modulo 7.

d) $2\times 3=6\equiv 0\pmod 6$, avec $2\neq 0$ et $3\neq 0$. On appelle de tels éléments des DIVISEURS DE ZÉRO. Ils apparaissent parce que 6 se factorise en $2\times 3$ : le produit récupère tous les facteurs de 6 et devient un multiple de 6. Modulo 7 c'est impossible, car 7 est PREMIER : si 7 divise un produit $ab$, il divise $a$ ou $b$, propriété qui définit précisément les nombres premiers.

e) Un élément $a$ est inversible modulo $n$ si et seulement si $\mathrm{pgcd}(a,n)=1$. Par conséquent, TOUS les éléments non nuls sont inversibles si et seulement si $n$ est PREMIER, auquel cas les entiers modulo $n$ forment un corps. Si $n$ est composé, les éléments qui partagent un facteur avec $n$ ne sont pas inversibles et sont des diviseurs de zéro. Cette distinction est ce qui rend les modules premiers si précieux en cryptographie et en codes correcteurs.

a) Posons $r=a\bmod n$, donc $a=nq+r$. Si $d$ divise $a$ et $n$, alors il divise $a-nq=r$, donc il divise $n$ et $r$. Réciproquement, si $d$ divise $n$ et $r$, il divise $nq+r=a$, donc il divise $a$ et $n$. Les deux couples ont donc EXACTEMENT les mêmes diviseurs communs, et en particulier le même plus grand. L'algorithme consiste alors à remplacer le couple par un couple plus petit jusqu'à ce que le reste s'annule.

b) $1071=2\times 462+147$ ; $462=3\times 147+21$ ; $147=7\times 21+0$. Le dernier reste non nul est 21, donc $\mathrm{pgcd}(1071,462)=21$. La figure donne la lecture géométrique : on pave le rectangle par des carrés de plus en plus petits, et le côté du dernier carré est le PGCD. Trois divisions ont suffi là où la recherche des diviseurs de 1071 en aurait demandé beaucoup plus.

c) $240=5\times 46+10$ ; $46=4\times 10+6$ ; $10=1\times 6+4$ ; $6=1\times 4+2$ ; $4=2\times 2+0$. Le PGCD vaut 2. Notez que ces deux nombres, plus petits que ceux de la question b, ont demandé PLUS d'étapes : le nombre d'étapes ne dépend pas de la taille des nombres mais de la suite des quotients, tous égaux à 1 dans le pire cas.

d) Les deux versions tiennent en quatre lignes et se lisent directement sur la question a. La version ITÉRATIVE remplace le couple $(a,n)$ par $(n,a\bmod n)$ à chaque tour et s'arrête quand le second terme s'annule ; c'est alors le premier qui porte le PGCD. La version RÉCURSIVE traduit la même égalité mot pour mot, avec le cas de base $n=0$ qui renvoie $a$. La récursive est plus lisible et son nombre d'appels est le nombre de divisions, donc elle ne risque aucun débordement de pile pour des entiers de taille raisonnable ; l'itérative évite malgré tout ce risque et reste la forme employée dans les bibliothèques.

e) Le théorème de Lamé affirme que le nombre d'étapes est au plus environ $5$ fois le nombre de CHIFFRES du plus petit des deux nombres, ce qui est remarquablement peu : moins de 50 étapes pour des nombres de dix chiffres. Le PIRE CAS est celui de deux nombres de FIBONACCI consécutifs, comme 89 et 55, pour lesquels tous les quotients valent 1 et où l'algorithme ne peut donc rien accélérer. C'est un exemple rare où le pire cas d'un algorithme est connu explicitement.

a) L'inverse de $a$ modulo $n$ existe si et seulement si $\mathrm{pgcd}(a,n)=1$, c'est-à-dire si $a$ et $n$ sont PREMIERS ENTRE EUX. Pour 3 modulo 7 : $\mathrm{pgcd}(3,7)=1$, l'inverse existe. On essaie : $3\times 1=3$, $3\times 2=6$, $3\times 3=9\equiv 2$, $3\times 4=12\equiv 5$, $3\times 5=15\equiv 1$ ✓. L'inverse de 3 modulo 7 est donc 5.

b) $\mathrm{pgcd}(4,9)=1$, l'inverse existe : $4\times 7=28=27+1\equiv 1\pmod 9$, donc l'inverse est 7. Modulo 8, en revanche, $\mathrm{pgcd}(4,8)=4\neq 1$ : il n'y a pas d'inverse. On le vérifie sur la table, les multiples de 4 modulo 8 ne prennent que les valeurs 0 et 4, jamais 1. Le même nombre 4 est donc inversible ou non selon le module, ce qui montre bien que l'inversibilité est une propriété du COUPLE et non du nombre.

c) On multiplie les deux membres par l'inverse de 3, c'est-à-dire par 5 : $5\times 3x\equiv 5\times 2$, soit $15x\equiv 10$, soit $x\equiv 3\pmod 7$ puisque $15\equiv 1$ et $10\equiv 3$. Vérification : $3\times 3=9\equiv 2\pmod 7$ ✓. Il y a donc exactement UNE solution modulo 7, comme toujours lorsque le coefficient est inversible.

d) $\mathrm{pgcd}(4,10)=2$, qui ne vaut pas 1 : on ne peut pas inverser. Mais 2 DIVISE le second membre 6, donc l'équation a des solutions. On divise tout par 2, MODULE COMPRIS : $2x\equiv 3\pmod 5$. Cette fois $\mathrm{pgcd}(2,5)=1$ et l'inverse de 2 modulo 5 est 3, d'où $x\equiv 3\times 3=9\equiv 4\pmod 5$. Modulo 10, cela donne DEUX solutions, $x=4$ et $x=9$. Vérification : $4\times 4=16\equiv 6$ ✓ et $4\times 9=36\equiv 6$ ✓. Le nombre de solutions est égal au PGCD, ici 2.

e) $\mathrm{pgcd}(6,9)=3$, et 3 NE DIVISE PAS 4. L'équation n'a donc AUCUNE solution. On le voit directement : $6x$ est toujours un multiple de 3, donc son reste modulo 9 appartient à $\{0,3,6\}$, et 4 n'y figure pas. Règle générale : $ax\equiv b\pmod n$ a des solutions si et seulement si $\mathrm{pgcd}(a,n)$ divise $b$, et il y en a alors exactement $\mathrm{pgcd}(a,n)$ modulo $n$.

a) Pour tous entiers $a$ et $b$ non tous nuls, il existe des entiers $u$ et $v$ tels que $au+bv=\mathrm{pgcd}(a,b)$. Lorsque $a$ et $b$ sont PREMIERS ENTRE EUX, cela devient $au+bv=1$, et réciproquement : une telle écriture prouve que le PGCD vaut 1, puisque tout diviseur commun divise le membre de gauche donc divise 1. C'est le critère le plus commode pour démontrer que deux nombres sont premiers entre eux.

b) On remonte les divisions. De $462=3\times 147+21$ on tire $21=462-3\times 147$. De $1071=2\times 462+147$ on tire $147=1071-2\times 462$. En substituant : $21=462-3\left(1071-2\times 462\right)=462-3\times 1071+6\times 462=7\times 462-3\times 1071$. Donc $u=-3$ et $v=7$. Vérification : $-3\times 1071+7\times 462=-3213+3234=21$ ✓. La discipline est de substituer UNE division à la fois, de bas en haut, sans jamais développer les produits avant la fin.

c) Euclide d'abord : $43=2\times 17+9$ ; $17=1\times 9+8$ ; $9=1\times 8+1$ ; $8=8\times 1+0$. Le PGCD vaut 1, l'inverse existe. Remontée : $1=9-8$ ; puis $8=17-9$ donne $1=9-(17-9)=2\times 9-17$ ; puis $9=43-2\times 17$ donne $1=2\left(43-2\times 17\right)-17=2\times 43-5\times 17$. Donc $-5\times 17\equiv 1\pmod{43}$, et l'inverse de 17 est $-5$, c'est-à-dire $38$ modulo 43. Vérification : $17\times 38=646=43\times 15+1$ ✓.

d) La recherche exhaustive teste les valeurs $1,2,\dots,n-1$ jusqu'à tomber sur 1 : son coût est de l'ordre de $n$ multiplications, donc EXPONENTIEL en le nombre de chiffres de $n$. L'algorithme d'Euclide étendu, lui, effectue au plus environ $5$ fois le nombre de chiffres de divisions, donc un coût LINÉAIRE en ce nombre. Sur un module de 600 chiffres comme ceux du chiffrement RSA, la première méthode est impossible dans l'âge de l'Univers et la seconde prend une fraction de milliseconde. C'est cet écart qui rend la cryptographie moderne praticable.

e) Le code ci-dessous renvoie le triplet formé du PGCD et des deux coefficients de Bézout, en propageant les coefficients à chaque tour de boucle.

a) Si $p$ est PREMIER et si $p$ ne divise pas $a$, alors $a^{p-1}\equiv 1\pmod p$. Vérification avec $a=3$ et $p=7$ : $3^{1}=3$, $3^{2}=9\equiv 2$, $3^{3}\equiv 6$, $3^{4}\equiv 18\equiv 4$, $3^{5}\equiv 12\equiv 5$, $3^{6}\equiv 15\equiv 1$ ✓. La figure montre ce cycle de longueur 6 : les six valeurs non nulles apparaissent toutes, exactement une fois, avant que le cycle ne se referme sur 1.

b) Le théorème permet de réduire l'EXPOSANT modulo $p-1=6$. Comme $100=6\times 16+4$, on a $3^{100}=\left(3^{6}\right)^{16}\times 3^{4}\equiv 1^{16}\times 3^{4}=81\equiv 4\pmod 7$. Le reste vaut 4. Retenez la règle et sa limite : on réduit la BASE modulo $p$, et l'EXPOSANT modulo $p-1$, jamais l'inverse.

c) $p=11$ est premier et ne divise pas 2, donc $2^{10}\equiv 1\pmod{11}$. Comme $1000=10\times 100$, on a $2^{1000}=\left(2^{10}\right)^{100}\equiv 1^{100}=1\pmod{11}$. Le reste vaut 1. Un nombre de plus de trois cents chiffres a été réduit en une ligne.

d) $11$ s'écrit $1011$ en binaire, donc $7^{11}=7^{8}\times 7^{2}\times 7^{1}$. On calcule les carrés successifs modulo 13 : $7^{1}\equiv 7$ ; $7^{2}=49\equiv 10$ ; $7^{4}\equiv 10^{2}=100\equiv 9$ ; $7^{8}\equiv 9^{2}=81\equiv 3$. Produit : $3\times 10\times 7=210\equiv 210-208=2\pmod{13}$. VÉRIFICATION par Fermat : $7^{12}\equiv 1$, donc $7^{11}\equiv 7^{-1}$, l'inverse de 7 modulo 13. Or $7\times 2=14\equiv 1$, donc cet inverse vaut 2 ✓. Deux chemins indépendants, même réponse.

e) La méthode naïve demande $N-1$ multiplications pour $a^{N}$, soit environ $10^{600}$ opérations pour un exposant de 600 chiffres : c'est inconcevable, l'Univers n'a connu qu'environ $10^{17}$ secondes. L'exponentiation rapide en demande au plus $2\log_{2}N$, soit environ $2\times 600\times 3{,}32\approx 3986$ multiplications, l'affaire de quelques millisecondes. C'est cette différence, et elle seule, qui permet à un navigateur d'ouvrir une connexion chiffrée en un clin d'œil.

1) FAUX. L'égalité écrite est correcte, mais $-2$ n'est PAS un reste valide : la division euclidienne impose $0\leq r<n$, donc ici $0\leq r<5$. Il faut choisir $q=-4$ : $-17=5\times(-4)+3$, donc $-17\bmod 5=3$. C'est aussi ce que renvoie Python. La confusion vient des langages comme C ou Java, dont l'opérateur suit une autre convention et renvoie effectivement $-2$ : le langage n'a pas tort, il ne calcule simplement pas le reste euclidien.

2) FAUX. On ne peut simplifier par $c$ que si $c$ est INVERSIBLE modulo $n$, c'est-à-dire premier avec $n$. Contre-exemple : $2\times 3\equiv 4\times 3\pmod 6$, car $6\equiv 12\equiv 0$, et pourtant $2\not\equiv 4\pmod 6$. La règle correcte est que $ac\equiv bc\pmod n$ entraîne $a\equiv b\pmod{\frac{n}{\mathrm{pgcd}(c,n)}}$, ce qui ne redonne le module de départ que si le PGCD vaut 1.

3) FAUX. L'inverse de $a$ modulo $n$ existe si et seulement si $\mathrm{pgcd}(a,n)=1$. Modulo 6, les éléments 2, 3 et 4 n'ont pas d'inverse, puisqu'ils partagent un facteur avec 6 ; seuls 1 et 5 en ont. L'affirmation n'est vraie que lorsque $n$ est PREMIER, cas où tous les éléments non nuls sont premiers avec $n$ par définition.

4) FAUX, et l'erreur est d'un seul cran mais elle change tout. Le petit théorème de Fermat donne $3^{6}\equiv 1\pmod 7$, donc c'est modulo $p-1=6$ que l'on réduit l'exposant, et non modulo 7. On a $100\equiv 4\pmod 6$, donc $3^{100}\equiv 3^{4}=81\equiv 4$. Réduire modulo 7 donnerait $100\equiv 2$, donc $3^{2}=9\equiv 2$, résultat faux. Règle : la base se réduit modulo $n$, l'exposant modulo $p-1$.

5) FAUX, c'est exactement le contraire. Le théorème de Lamé garantit que le nombre de divisions est au plus environ 5 fois le nombre de CHIFFRES du plus petit nombre : pour deux nombres de 600 chiffres, cela fait moins de 3000 divisions, soit une fraction de milliseconde. C'est cette efficacité qui permet de calculer l'exposant de déchiffrement d'une clé RSA, et l'algorithme d'Euclide étendu est donc au contraire un pilier de la cryptographie moderne.

a) Dans la convention ISBN-13, la clé est le treizième chiffre et elle porte le poids 1, puisque les poids alternent en commençant par 1. Il faut donc que $97+c$ soit un multiple de 10, avec $0\leq c\leq 9$. Le multiple de 10 immédiatement supérieur à 97 est 100, donc $c=3$. Formule générale : $c=\left(10-\left(S\bmod 10\right)\right)\bmod 10$, et le dernier modulo sert au seul cas où $S$ est déjà multiple de 10, où la clé vaut 0 et non 10.

b) Somme totale : $97+3=100$, qui est bien un multiple de 10 puisque $100\equiv 0\pmod{10}$ ✓. Le code complet est donc valide, et c'est cette vérification, et non le calcul de la clé, que la caisse d'une librairie effectue à chaque scan.

c) Supposons qu'un chiffre de poids $w$ passe de $d$ à $d'$. La somme change de $w\left(d'-d\right)$, avec $w$ valant 1 ou 3 et $d'-d$ compris entre $-9$ et 9, non nul. Pour que l'erreur passe inaperçue, il faudrait que $w\left(d'-d\right)\equiv 0\pmod{10}$. Avec $w=1$ : il faudrait $10$ divise $d'-d$, impossible pour un écart non nul de moins de 10. Avec $w=3$ : comme $\mathrm{pgcd}(3,10)=1$, on peut simplifier par 3 et l'on retombe sur la même impossibilité. Toute erreur d'UN chiffre est donc détectée, et c'est précisément parce que 3 est premier avec 10.

d) Interverting deux chiffres voisins $a$ et $b$ portant les poids 1 et 3, la somme passe de $a+3b$ à $b+3a$, soit une variation de $2\left(a-b\right)$. L'erreur échappe au contrôle si $2\left(a-b\right)\equiv 0\pmod{10}$, c'est-à-dire si $a-b\equiv 0\pmod 5$, donc si $\left|a-b\right|=5$. EXEMPLE : le code $9782723456807$ est valide, de somme 103 plus une clé 7, soit 110. En intervertissant le 2 et le 7 des positions 4 et 5, on obtient $9782\!\to\!9787\dots$, dont la somme pondérée devient 113 plus 7, soit 120, encore multiple de 10 : la faute de frappe n'est PAS détectée. C'est la faiblesse connue de l'ISBN-13, et c'est un défaut sérieux puisque l'interversion de deux chiffres voisins est l'erreur de saisie la plus courante.