Comprendre intuitivement l'arithmétique modulaire (Le calcul de l'horloge et le règne des restes)

Il est neuf heures et un vol part dans cinq heures. Sur le cadran d'une montre à aiguilles, il n'existe pas de quatorze: l'aiguille se pose sur le deux, et vous l'avez lu sans y penser. Les heures font le tour à douze et repartent. Vous pratiquez l'arithmétique modulaire depuis que vous savez lire l'heure; vous n'aviez simplement jamais croisé la notation.

Tout le sujet est là. Choisissez un nombre où boucler, oubliez chaque tour complet, et ne gardez que l'endroit où vous arrivez. Ce qui mérite un article, c'est que cette seule habitude, ne garder que le reste, résout des problèmes qui paraissent impossibles de front: le dernier chiffre d'un nombre à soixante-dix chiffres, la divisibilité par 9 d'un nombre énorme, la validité ou non d'un numéro de carte bancaire, et la façon dont un message peut être brouillé pour que seul son destinataire le remette en clair.

Cet article donne l'image: ce qu'est vraiment un reste, pourquoi vous avez le droit de réduire avant de calculer, ce qui se passe avec les négatifs et avec les puissances, et d'où vient la seule véritable difficulté, la division.

Un reste, c'est là où vous arrivez, pas ce qui traîne

La définition standard dit que $a \bmod n$ est le reste de la division de $a$ par $n$. C'est exact, et c'est aussi pourquoi le sujet ressemble à une corvée, car le mot « reste » évoque le rebut abandonné après une division, une pensée d'après coup.

Meilleure image: une piste circulaire portant $n$ repères, numérotés de $0$ à $n-1$. Pour trouver $a \bmod n$, partez de $0$ et faites $a$ pas le long de la piste. L'endroit où vous vous arrêtez est la réponse. Faire 17 pas sur une piste à 5 repères, c'est boucler trois tours complets (15 pas) puis avancer encore de 2, vous vous arrêtez donc sur le repère 2. D'où $17 \bmod 5 = 2$. Les tours complets sont le quotient; l'endroit où vous arrivez est le reste.

Cette image fait deux choses que la définition ne fait pas. Elle impose au reste de tomber toujours entre $0$ et $n-1$, puisqu'il n'y a pas d'autres repères. Et elle explique pourquoi deux nombres peuvent être « les mêmes » modulo $n$ tout en étant follement différents: $2$, $17$, $102$ et $5{,}000{,}002$ s'arrêtent tous sur le repère 2 d'une piste à 5 repères. Ils ne diffèrent que par des tours, et la piste ne garde pas la mémoire des tours.

Les mathématiciens écrivent cette idée sous la forme d'une congruence:

$$17 \equiv 2 \pmod{5}$$

Lisez-la ainsi: « 17 arrive là où arrive 2, sur la piste à 5 repères ». La triple barre n'est pas un signe égal, car 17 et 2 ne sont pas égaux. Elle dit qu'ils sont interchangeables pour toute question qui ne s'intéresse qu'à la position sur la piste. La version précise: $a \equiv b \pmod{n}$ signifie que $n$ divise $a - b$, autrement dit que les deux nombres diffèrent d'un nombre entier de tours.

L'addition et la multiplication ne regardent que votre position

Voici le fait qui fait de l'arithmétique modulaire un outil et non une curiosité. Si vous devez additionner deux nombres puis prendre le reste, vous pouvez prendre les restes d'abord, les additionner, et réduire à nouveau. Le résultat est identique. Il en va de même pour la soustraction et la multiplication.

Sur la piste, c'est évident. Ajouter 17, c'est faire 17 pas, soit trois tours plus 2. Les trois tours vous ramènent à votre point de départ et ne changent rien, ajouter 17 a donc exactement le même effet qu'ajouter 2. Les tours cachés dans un nombre sont du poids mort, et ils restent du poids mort à travers l'addition comme à travers la multiplication, car un multiple de $n$ multiplié par n'importe quoi reste un multiple de $n$.

Écrit en toutes lettres, avec $a = qn + r$ et $b = pn + s$:

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

Tout ce qui se trouve dans la première parenthèse est constitué de tours. Seul $rs$ survit, donc $ab \bmod n$ vaut $rs \bmod n$. Les restes portent toute l'information dont la question a besoin.

C'est pourquoi le conseil donné dans le module d'arithmétique de Math Zen est de réduire pas à pas plutôt que de calculer la valeur complète. Supposons que vous vouliez $123 \times 456 \bmod 7$. Vous pourriez développer jusqu'à 56 088 puis faire une division par 7. Ou vous pouvez remarquer que $123 = 119 + 4$, donc $123 \equiv 4$, et que $456 = 455 + 1$, donc $456 \equiv 1$, et la réponse est $4 \times 1 = 4$. Deux petites réductions remplacent une multiplication à quatre chiffres. L'habitude à prendre: ne laissez jamais un nombre dépasser $n$ si seul son reste vous intéresse.

Les nombres négatifs marchent dans l'autre sens

L'image de la piste règle aussi le cas qui fait trébucher presque tout le monde. Que vaut $-3 \bmod 5$ ?

Faites 3 pas en arrière depuis 0 sur une piste à 5 repères. Vous passez par 4, puis 3, et vous arrivez sur 2. Donc $-3 \equiv 2 \pmod{5}$. Un nombre négatif n'est qu'une marche dans l'autre sens, la même idée que dans Comprendre intuitivement les nombres négatifs, et le reste est toujours l'endroit où vous arrivez, toujours entre $0$ et $n-1$.

Le raccourci: ajoutez des tours jusqu'à rendre le nombre positif. $-3 + 5 = 2$. Pour $-14 \bmod 5$, ajoutez 15 (trois tours) et vous obtenez 1. Calculatrices et langages de programmation ne s'accordent pas sur les restes négatifs, certains renvoyant $-4$ pour $-14 \bmod 5$, donc lors d'un contrôle donnez toujours la réponse sous forme du repère positif ou nul de la piste, et vérifiez la convention de votre calculatrice avant de lui faire confiance.

La soustraction raconte la même histoire. $3 - 8 \pmod{5}$ vaut $-5$, soit exactement un tour en arrière, la réponse est donc 0. Ou réduisez d'abord: $8 \equiv 3$, donc $3 - 3 = 0$.

Le dernier chiffre d'une puissance énorme

C'est le problème qui convainc les gens que le sujet vaut la peine d'être appris, et c'est une conséquence directe de la règle « réduire d'abord ».

Le dernier chiffre d'un nombre est ce nombre modulo 10, parce que les dizaines, les centaines et tout ce qui est au-dessus sont des multiples de 10 et reviennent sur 0 sur une piste à 10 repères. Donc « quel est le dernier chiffre de $7^{100}$ » est la question « que vaut $7^{100} \bmod 10$ », et vous n'avez jamais à calculer $7^{100}$.

À la place, regardez les puissances de 7 tourner sur la piste à 10 repères, en réduisant chaque fois:

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

Dès que vous touchez 1, le cycle redémarre: 7, 9, 3, 1, 7, 9, 3, 1, de période 4. Comme $100 = 4 \times 25$, la centième puissance se trouve à la fin d'un cycle complet, au même endroit que $7^4$, et son dernier chiffre est 1.

Toute base possède un cycle modulo 10, et la plupart sont courts. Les puissances de 2 parcourent 2, 4, 8, 6. Celles de 3 parcourent 3, 9, 7, 1. Celles de 5 et de 6 ne bougent jamais. La méthode est toujours la même: trouvez la longueur du cycle en réduisant au fur et à mesure, divisez l'exposant par cette longueur, et le reste de cette division vous dit où vous êtes dans le cycle. C'est l'idée des exposants, la multiplication répétée, appliquée sur une piste circulaire au lieu d'une droite.

Pourquoi le critère de la somme des chiffres pour 9 fonctionne

Tout le monde apprend qu'un nombre est divisible par 9 si la somme de ses chiffres est un multiple de 9, et presque personne n'apprend pourquoi. L'arithmétique modulaire en fait un argument d'une ligne.

Dix, c'est un tour plus un sur une piste à 9 repères: $10 \equiv 1 \pmod{9}$. Alors $100 = 10 \times 10 \equiv 1 \times 1 = 1$, et toute puissance de 10 est également congrue à 1. Donc un nombre comme $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ est congru à $4 + 5 + 2 + 7 = 18 \pmod{9}$, et 18 vaut $0$ sur la piste à 9 repères, donc 4 527 est divisible par 9. La somme des chiffres n'est pas une astuce. C'est le nombre lui-même, vu modulo 9.

Le critère pour 3 fonctionne pour la même raison, puisque $10 \equiv 1 \pmod{3}$ aussi. Celui pour 11 vient de $10 \equiv -1 \pmod{11}$, qui fait alterner les puissances de 10 entre $1$ et $-1$ et donne la somme alternée des chiffres. Toutes les règles de divisibilité qu'on vous a demandé d'apprendre par coeur sont un seul fait, « réduisez les puissances de 10 », appliqué à des pistes différentes.

Clés de contrôle: l'arithmétique modulaire dans votre portefeuille

Chaque ISBN, chaque numéro de carte bancaire et chaque code-barres se termine par un chiffre dont le seul rôle est d'être un reste.

Le dernier chiffre d'un ISBN à 13 chiffres est choisi pour qu'une somme pondérée des treize chiffres, avec des poids alternant 1 et 3, soit congrue à $0 \pmod{10}$. Tapez un seul chiffre de travers et la somme atterrit ailleurs sur la piste à 10 repères, et le lecteur refuse le code. Les cartes bancaires utilisent l'algorithme de Luhn, une pondération un peu plus fine qui attrape aussi la plupart des inversions de deux chiffres voisins, là encore en vérifiant une somme modulo 10.

Ce sont les humbles cousins d'une application bien plus vaste. Le chiffrement moderne repose sur le fait qu'élever un nombre à une puissance modulo un $n$ très grand est facile, alors que remonter l'opération sans clé secrète ne l'est pas. La recherche de cycle que vous venez de faire pour $7^{100}$ est la même opération, portée à des nombres de plusieurs centaines de chiffres, et la règle « réduire au fur et à mesure » est la seule raison pour laquelle elle est calculable.

La division, là où la piste devient cahoteuse

L'addition, la soustraction et la multiplication se comportent sur une piste exactement comme sur la droite numérique. La division, non, et c'est le seul endroit où le sujet mérite sa réputation.

Sur la droite numérique ordinaire, diviser par 4 revient à multiplier par $\tfrac{1}{4}$, le nombre qui, multiplié par 4, donne 1. Sur une piste à 12 repères, existe-t-il un repère qui, multiplié par 4, tombe sur 1 ? Essayez-les tous: $4 \times 1 = 4$, $4 \times 2 = 8$, $4 \times 3 = 12 \equiv 0$, $4 \times 4 = 16 \equiv 4$, et le motif 4, 8, 0 se répète indéfiniment. Il ne touche jamais 1. Sur la piste à 12 repères, diviser par 4 n'existe donc pas.

La raison est que 4 et 12 partagent un facteur. Partez d'un multiple de 4, ajoutez ou retirez des tours de 12, et vous avez toujours un multiple de 4, vous ne pouvez donc jamais arriver 1 au-delà d'un multiple de 12. Essayez 5 à la place: $5 \times 5 = 25 = 24 + 1 \equiv 1$, donc 5 est son propre inverse sur la piste à 12 repères et diviser par 5 ne pose aucun problème. La règle: $a$ possède un inverse modulo $n$ exactement lorsque $a$ et $n$ n'ont aucun facteur commun autre que 1.

Cette règle a une conséquence frappante. Si $n$ est premier, aucun nombre de $1$ à $n - 1$ ne partage de facteur avec lui, tout repère non nul possède donc un inverse et vous pouvez diviser librement. Les pistes premières sont celles où les quatre opérations fonctionnent, ce qui explique en grande partie pourquoi les nombres premiers, dont l'infinitude des nombres premiers garantit la réserve, siègent au centre de la théorie des nombres et de la cryptographie.

D'où viennent les erreurs

L'arithmétique modulaire compte peu de pièces mobiles, et les erreurs sont d'autant plus précises.

La première consiste à réduire l'exposant au lieu de la base. Dans $7^{100} \bmod 10$, vous pouvez réduire 7 modulo 10 (c'est déjà fait), et vous pouvez réduire l'exposant modulo la longueur du cycle une fois que vous la connaissez, mais vous ne pouvez pas réduire 100 modulo 10 pour calculer $7^0$. Les exposants vivent sur une autre piste, celle dont la taille est la longueur du cycle, et mélanger les deux pistes est de loin l'erreur la plus fréquente du sujet.

La deuxième est le reste négatif. $-14 \bmod 5$ vaut 1, pas $-4$. Même position sur la piste, mais un seul des deux porte le nom conventionnel, et les corrigés veulent celui qui est positif ou nul.

La troisième est de diviser sans vérifier l'existence d'un inverse. Simplifier un facteur commun des deux membres d'une congruence n'est légitime que si ce facteur ne partage rien avec le module. De $4 \times 2 \equiv 4 \times 5 \pmod{12}$, qui est vrai puisque les deux membres valent 8, vous ne pouvez pas barrer le 4 pour conclure que $2 \equiv 5$, ce qui est faux. Les tours que vous jetez en simplifiant doivent être des tours de la piste d'origine.

La quatrième est d'oublier de réduire à la fin. Obtenir $rs = 21$ sur une piste à 7 repères et écrire 21 n'est pas faux, à proprement parler, mais ce n'est pas une réponse non plus. La réponse est un repère de la piste, et 21 fait trois tours, le repère est donc 0.

La place de Math Zen

Le module d'arithmétique de Math Zen réserve un bloc entier à l'arithmétique modulaire, et la progression est bâtie autour de l'habitude de réduire d'abord plutôt qu'autour de la notation. Les premiers exercices demandent de simples restes et congruences avec de petits modules, jusqu'à ce que « où est-ce que j'arrive » devienne automatique. Les blocs intermédiaires mêlent négatifs et produits, où l'enjeu est de réduire chaque facteur avant de multiplier et de donner le reste positif ou nul. Les derniers blocs sont les problèmes de dernier chiffre et de longueur de cycle, ceux qui apparaissent aux concours et aux tests d'admission et qui punissent quiconque tente de calculer la puissance entière.

Parce que les séances sont courtes et que les problèmes reviennent à intervalles espacés, comme le décrit la répétition espacée pour l'entraînement en maths, la recherche de cycle devient un réflexe au lieu d'une procédure qu'on va consulter. La plupart des gens n'ont pas une lacune en arithmétique modulaire qu'un chapitre viendrait combler. Ils ont une image, la piste, que personne n'a dessinée pour eux, et une quarantaine de répétitions qui n'ont jamais été faites.

Le bilan

L'arithmétique modulaire est l'arithmétique sur une piste circulaire à $n$ repères. Un reste est l'endroit où vous arrivez après $a$ pas, les tours complets sont oubliés, et deux nombres sont congrus lorsqu'ils arrivent sur le même repère. Comme les tours n'apportent rien aux sommes ni aux produits, vous pouvez réduire chaque nombre à son reste avant d'additionner ou de multiplier, et cette seule permission transforme des calculs impossibles, comme le dernier chiffre de $7^{100}$, en cycles courts que l'on suit à la main. Les critères de divisibilité sont les puissances de 10 réduites modulo 9, 3 ou 11. Les clés de contrôle sont des restes qui attrapent les fautes de frappe. La division ne fonctionne que si le nombre ne partage aucun facteur avec la piste, et c'est pourquoi les pistes premières sont spéciales.

Quand un problème modulaire bloque, dessinez la piste. Demandez où chaque morceau arrive, réduisez au fur et à mesure, et gardez l'exposant sur sa propre piste. La réponse est un repère entre $0$ et $n - 1$, et l'image vous y mènera avant la formule.