Calculatrice de modulo

-47 ÷ 5 = -9 reste -2 (tronqué) ; -2 + 5 = 3, donc -47 mod 5 = 3 et -47 ≡ 3 (mod 5)

a

Le dividende, le nombre que l’on réduit. Il peut être négatif, et c’est le cas qui vaut la peine d’être testé : a mod n doit ressortir non négatif même quand a ne l’est pas, donc -47 doit atterrir sur 3 plutôt que sur -2. Les entiers de -1 000 000 000 à 1 000 000 000 sont acceptés, et 0 est un dividende parfaitement valable dont le résidu vaut toujours 0

n

Le module, le nombre par lequel on divise. Il peut être négatif lui aussi, et le résidu ne change pas pour autant : 47 mod -5 et 47 mod 5 valent tous les deux 2, parce que l’affirmation « n divise a - r » et l’affirmation « -n divise a - r » disent exactement la même chose. Zéro est la seule valeur refusée, et la page imprime n tel qu’il a été saisi plutôt qu’en le remplaçant par sa valeur absolue

r

Le résidu, qui est la réponse. C’est le plus petit nombre non négatif qu’on puisse retirer à a en laissant un multiple de n. Deux conditions le déterminent complètement : r est au moins égal à 0, et r est strictement inférieur à la taille de n. -47 mod 5 donne 3 parce que 3 est la plus petite valeur non négative pour laquelle -47 - 3 = -50 est un multiple de 5

((a mod n) + |n|) mod |n|

La recette en deux temps que suit la page, et la raison d’être du second temps. Le premier temps est ce que calculent la plupart des langages et il peut rendre une réponse négative ; le second ajoute la taille du module et réduit de nouveau, ce qui pousse le résultat dans l’intervalle non négatif sans changer le multiple de n à partir duquel il est mesuré. Utiliser la taille de n plutôt que n lui-même est ce qui permet à un module négatif de passer sans être modifié

a ≡ r (mod n)

La congruence, qui est la première ligne du panneau de résultat. Elle dit que n divise exactement a - r, et c’est la même affirmation que le résidu écrit seul, avec le module et le dividende nommés à côté. Le symbole à trois barres et le mot-clé mod sont de la notation et non des mots, ils s’impriment donc à l’identique dans toutes les langues du site, et aucun séparateur de milliers n’est inséré dans les nombres

-47 ≡ 3 (mod 5)

La saisie par défaut écrite en toutes lettres. C’est le cas qui sépare cette page d’une calculatrice de reste : les deux mêmes nombres donnent -9 avec un reste de -2 sous la convention tronquée qu’utilise une calculatrice de collège, et -47 ≡ 3 (mod 5) ici. Saisir 47 au lieu de -47 donne 2 plutôt que 3, donc un seul signe moins déplace la réponse d’un pas entier autour du cycle

Passez par cette page chaque fois que la réponse doit boucler plutôt que s’arrêter. L’arithmétique de l’horloge est l’exemple le plus ancien : 10 heures plus 5 heures font 3 heures, ce qui est 15 mod 12, et c’est précisément parce que le résidu n’est jamais négatif qu’un cadran reste lisible. Le travail sur les calendriers a la même forme — le centième jour d’une année, ou le jour de la semaine d’une date donnée, est un résidu modulo 7. En programmation, un modulo sert à tester si un nombre en divise un autre (a mod n vaut 0 quand n y entre exactement), à ramener un indice dans les bornes d’un tampon circulaire ou d’une table de hachage, à maintenir un compteur qui boucle entre des bornes fixes, et à prendre les éléments d’une liste chacun à son tour. La cryptographie est bâtie dessus : RSA et Diffie-Hellman sont de l’arithmétique modulaire sur de très grands nombres, et toute la raison pour laquelle le résidu est défini comme non négatif est qu’une réponse signée serait une arithmétique ambiguë sur laquelle bâtir. Les clés de contrôle, des numéros de compte bancaire aux ISBN, sont des résidus modulo 9, 10 ou 11. Quand la question est plutôt « combien de fois cela tient-il, et que reste-t-il, sous la convention qu’utilise ma calculatrice », la calculatrice de reste est la meilleure page parce qu’elle expose les deux conventions côte à côte ; quand la question est ce que les deux nombres ont en commun, la page du PGCD y répond directement.

1. Le piège du signe : -47 mod 5

   1. On divise comme d’habitude en jetant la partie fractionnaire : -47 ÷ 5 = -9,4, donc le quotient tronqué vaut -9
   2. -9 × 5 = -45, et -47 - (-45) = -2, donc le reste tronqué vaut -2
   3. Le résidu doit être au moins égal à 0, on ajoute donc la taille du module : -2 + 5 = 3
   4. On vérifie que le résultat est dans l’intervalle : 0 ≤ 3 < 5, donc aucun ajustement supplémentaire n’est nécessaire
   5. On lit la congruence : -47 ≡ 3 (mod 5), ce qui veut dire que 5 divise exactement -47 - 3 = -50

   La saisie par défaut, et celle qui explique pourquoi cette page existe. Une calculatrice de collège, comme la plupart des langages de programmation, annoncera -9 avec un reste de -2 pour cette division ; cette réponse n’est pas fausse, elle répond à une question formulée autrement. Le résidu vaut ici 3 parce que 3 est la plus petite valeur non négative qui laisse un multiple de 5. Remarquez que 47 mod 5 vaut 2, et non -3 ni 3 — déplacer le dividende d’un pas entier autour du cycle déplace le résidu d’un cran, et les deux résidus diffèrent exactement de 1 et non de 5.

2. Un module négatif : 47 mod -5

   1. 47 ÷ 5 = 9,4, donc 5 y entre neuf fois et 9 × 5 = 45
   2. 47 - 45 = 2, qui est déjà dans l’intervalle 0 ≤ 2 < 5
   3. Le module est négatif, mais la divisibilité ne se soucie pas du signe : -5 divise 45 exactement, donc il divise aussi 47 - 2 exactement
   4. La congruence s’écrit avec le module tel qu’il a été saisi : 47 ≡ 2 (mod -5)

   Le cas qui montre que le résidu est insensible au signe du module. Remplacer -5 par 5 ne change rien à la réponse, parce que -5 divise un nombre exactement quand 5 le divise. La page conserve le signe moins dans la congruence imprimée plutôt que de l’effacer discrètement ; réécrire -5 en 5 donnerait l’impression que la saisie a été jetée. Comparez les deux lignes de la table de référence qui partagent le diviseur -5 avec celles qui partagent 5 : c’est seulement le signe du dividende qui déplace le résidu.

3. Le cas ordinaire : 1 234 mod 12

   1. 12 × 100 = 1 200, et 1 234 - 1 200 = 34, on continue donc : 12 × 2 = 24 laisse 34 - 24 = 10
   2. 12 × 3 = 36 dépasserait 34, donc le quotient vaut 102 et ce qui reste vaut 10
   3. 10 est au moins égal à 0 et inférieur à 12, c’est donc déjà le résidu
   4. On le lit comme une congruence : 1 234 ≡ 10 (mod 12)

   Le cas simple avec deux nombres positifs, où le résidu et un reste ordinaire coïncident — et c’est justement l’intérêt de l’inclure. Quand les deux nombres sont positifs, il n’y a rien à réconcilier, et la page fait le même travail que n’importe quel outil de reste. Les lignes intéressantes sont celles qui contiennent un signe moins. Cette paire-là a une seconde lecture qui vaut la peine d’être remarquée : 1 234 mod 12 est la façon de demander sur quelle heure retombe une durée quand le cadran compte douze heures, et 10 est une heure parfaitement sensée alors que -2 ne l’aurait pas été.

Le module ne peut pas être nul. Diviser par zéro n’a pas de réponse, il n’y a donc aucun reste à rapporter ni de plus petit reste non négatif ; la page refuse la saisie plutôt que de renvoyer une valeur de remplacement qui ressemble à un résultat. Les deux nombres doivent être entiers. Un module fractionnaire a sa propre définition dans certaines branches des mathématiques, mais ce n’est pas celle que cette page implémente, donc 47,5 est refusé plutôt qu’arrondi discrètement à 48 et traité comme si c’était ce que vous aviez demandé. La valeur absolue de chaque nombre est plafonnée à un milliard, ce qui garde chaque étape intermédiaire dans la plage où un nombre à double précision représente encore les entiers exactement ; au-delà, l’arithmétique commencerait à arrondir et la réponse aurait l’air parfaitement ordinaire tout en étant fausse. La page rapporte un résidu et une congruence, rien d’autre : elle ne donne pas le quotient, ne liste pas les autres nombres congrus à votre dividende, et ne fait pas d’arithmétique modulaire sur plus d’une paire à la fois. Un module négatif est accepté et imprimé tel qu’il a été saisi, ce qui veut dire que deux congruences qui disent la même chose peuvent avoir l’air différentes à l’écran — 47 ≡ 2 (mod -5) et 47 ≡ 2 (mod 5) sont la même affirmation. Enfin, la table de référence plus bas montre quatre paires figées plutôt que de suivre vos saisies ; c’est le panneau de résultat qui répond à ce que vous avez tapé.

Pourquoi -47 mod 5 vaut-il 3 et non -2 ?

Parce que le résidu est défini comme le plus petit nombre non négatif qu’on puisse retirer au dividende en laissant un multiple du module. -2 comme 3 remplissent la condition au sens où -47 - (-2) = -45 et -47 - 3 = -50 sont des multiples de 5, donc l’arithmétique seule ne choisit pas entre eux. C’est la définition qui tranche : le résidu vit dans l’intervalle allant de 0 au module exclu, et -2 est en dehors. Tout le reste en découle. Ce que vous obtenez d’un langage de programmation dépend de la convention qu’il a choisie, et JavaScript, C, Java et Go ont choisi l’autre — ils laissent le signe suivre le dividende. Python a choisi celle-ci. Aucun langage n’est cassé : ils répondent à des questions formulées différemment.

Le module peut-il être négatif ?

Oui, et le résidu n’est pas affecté par son signe. Un module négatif fonctionne parce que la divisibilité ignore les signes : -5 divise un nombre exactement quand 5 le divise, donc l’ensemble des multiples de -5 est le même que celui des multiples de 5, et le plus petit nombre non négatif de cet ensemble est le même dans les deux cas. La page imprime le module exactement tel qu’il a été saisi plutôt que de remplacer -5 par 5, parce que réécrire votre entrée donnerait l’impression que le signe a été perdu. Ainsi 47 mod -5 vaut 2 et 47 mod 5 vaut 2 aussi, et les deux congruences imprimées ne diffèrent que par un signe moins.

Que se passe-t-il si je saisis 0 comme module ?

La page le refuse. Mod 0 n’a aucune valeur à rapporter : zéro ne divise que zéro, il n’y a donc aucun multiple entier de 0 auquel mesurer le dividende et aucun reste à prendre. Renvoyer 0, ou le dividende lui-même, aurait l’air d’une réponse et serait faux pour toute entrée. Refuser la saisie est l’issue honnête. La division par zéro est indéfinie partout ailleurs en arithmétique, pour la même raison.

Est-ce la même chose que la calculatrice de reste de ce site ?

Non, et les deux donnent des réponses différentes au même calcul, ce qui est la façon la plus claire de voir la différence. La page du reste expose deux conventions côte à côte et vous laisse choisir, parce que la division euclidienne en a réellement deux en circulation et qu’une classe peut enseigner l’une ou l’autre. Cette page-ci ne propose pas de choix, parce que le modulo n’a qu’une seule lecture : la réponse n’est jamais négative. Pour -47 divisé par 5, la page du reste affichera -9 avec un reste de -2 sous sa convention par défaut, tandis que celle-ci affiche la congruence -47 ≡ 3 (mod 5). Utilisez l’autre page pour voir comment les deux conventions diffèrent sur une paire précise de nombres ; utilisez celle-ci quand ce que vous voulez est le résidu lui-même.

Où utilise-t-on réellement un résidu ?

Partout où un comptage doit boucler au lieu de croître sans fin. Le cadran d’une horloge est le cas quotidien : douze heures sur le cadran veulent dire que l’heure après 10 heures plus 5 heures est 15 mod 12, soit 3. Les jours de la semaine fonctionnent de la même façon modulo 7. En programmation, un modulo teste la divisibilité, puisque a mod n vaut 0 exactement quand n divise a sans reste ; il ramène un indice dans les bornes d’un tampon circulaire ou d’une table de hachage, où un indice sorti par le bout doit revenir au début ; et il maintient un compteur qui boucle entre des bornes fixes. La cryptographie à clé publique est de l’arithmétique modulaire sur de très grands nombres, et c’est pourquoi la convention non négative compte — une arithmétique qui produirait des résultats signés serait ambiguë pour bâtir dessus.

Pourquoi n’afficher que la congruence et pas le quotient ?

Parce que le quotient ne fait pas partie de ce que dit un résidu. Une congruence nomme le dividende, le résidu et le module, et l’affirmation qu’elle porte est que le module divise la différence des deux premiers. Cette affirmation est complète sans quotient, puisque le quotient est le nombre qu’on obtient en demandant combien de fois entières le module y tient, et que cette question relève de la division posée. Si vous voulez le quotient en même temps, la calculatrice de reste et la calculatrice de division posée le rapportent toutes les deux. Le résidu seul est également imprimé, sur la deuxième ligne du panneau de résultat, pour qu’un lecteur qui ne veut que le nombre n’ait pas à l’extraire de la phrase.

• Modular Arithmetic — the arithmetic of remainders, including the convention that the residue is taken in the interval from 0 up to the modulus — Wolfram MathWorld (United States)
• Congruence — the notation a ≡ r (mod n) and what it means for one number to divide the difference of two others exactly — Wolfram MathWorld (United States)
• Remainder (%) — the JavaScript operator whose sign follows the dividend, the behaviour that makes -47 % 5 return -2 and the reason a second step is needed here — MDN Web Docs (Mozilla)
• Arithmétique modulaire — le résidu pris dans l’intervalle allant de 0 au module, la notation a ≡ r (mod n), et le désaccord entre langages sur le signe du reste — Wikipédia en français