Aller au contenu

Comment fonctionne le modulo, même avec des nombres négatifs ?

Les restes selon chaque convention de signe, puissances et inverses modulaires, sur un cadran d’horloge interactif.

Opération

−31 mod 12

5

−31 = −3 × 12 + 5 : le reste est ce qui subsiste quand on retire des multiples entiers de 12.

Valeurs clés sous forme de tableau
Règle de signeqr
Jamais négatif (maths)−35
Signe de n (Python, Excel)−35
Signe de a (JavaScript, C, Java)−2−7
Quotient q
−3
Congruence
−31 ≡ 5 (mod 12)
Jamais négatif (maths)
5
Signe de n (Python, Excel)
5
Signe de a (JavaScript, C, Java)
−7

Les restes selon chaque convention de signe, puissances et inverses modulaires, sur un cadran d’horloge interactif.

Mode d’emploi

  1. Choisissez a mod n, une puissance modulaire aᵇ mod n ou un inverse modulaire a⁻¹ mod n.
  2. Saisissez les nombres entiers, ou faites glisser le point sur le cadran pour changer a.
  3. Pour un nombre négatif, choisissez la règle de signe voulue ; les résultats des maths, de Python et de JavaScript sont listés côte à côte.

Comment ça marche

a mod n est le reste r après avoir retiré des multiples entiers de n : a = q × n + r. Imaginez une horloge à n nombres, 0 en haut : partez de 0 et faites a pas (en arrière si a est négatif) ; r est l’endroit où vous arrivez. 31 heures avant minuit, une horloge de 12 heures indique 5, car −31 = −3 × 12 + 5.

Pour les nombres négatifs, les règles diffèrent par le nom qu’elles donnent à cette position. Les maths utilisent le reste euclidien, jamais négatif (0 ≤ r < |n|). Python et Excel arrondissent q vers le bas, donc r prend le signe de n. Le % de JavaScript, C et Java arrondissent q vers 0, donc r prend le signe de a : −31 % 12 y vaut −7. Les résultats diffèrent de n et sont congrus : −7 ≡ 5 (mod 12).

Les puissances modulaires se calculent par élévations au carré successives : 4¹³ mod 497 = 445, sans jamais écrire 4¹³ en entier. L’inverse de a est le x tel que a × x ≡ 1 (mod n), trouvé par l’algorithme d’Euclide étendu : 3 × 4 = 12 ≡ 1 (mod 11), donc 3⁻¹ mod 11 = 4. Il n’existe que si a et n n’ont aucun facteur commun. Sources : Khan Academy, arithmétique modulaire ; OpenStax, Contemporary Mathematics, section 3.7.

Exemple de calcul

Combien font −31 modulo 12 ?

  1. Écrivez −31 = q × 12 + r. En mathématiques, q = −3, donc r = −31 − (−3 × 12) = 5.
  2. JavaScript et C arrondissent plutôt le quotient vers 0 : q = −2, donc le reste est −7.

5 en mathématiques et en Python, −7 en JavaScript ; les deux diffèrent de 12.

Questions fréquentes

Pourquoi −7 % 3 donne-t-il −1 en JavaScript mais 2 en Python ?

JavaScript arrondit le quotient vers 0 (−2), donc le reste est −7 − (−6) = −1. Python arrondit vers le bas (−3), donc il vaut −7 − (−9) = 2. Les deux ont raison selon leur propre règle.

Comment obtenir toujours un reste positif ou nul en code ?

Utilisez ((a % n) + n) % n pour un n positif. Cela transforme le reste tronqué de JavaScript ou de C en reste euclidien.

Où utilise-t-on l’arithmétique modulaire ?

Dans les horloges et les calendriers, les clés de contrôle comme l’IBAN et l’ISBN, les tables de hachage et la cryptographie à clé publique comme RSA, qui repose sur les puissances et les inverses modulaires.

Pourquoi 4 n’a-t-il pas d’inverse modulo 6 ?

4 et 6 ont le facteur 2 en commun : tout multiple de 4 est donc pair modulo 6 et ne peut jamais valoir 1.

Quelle est la différence entre modulo et reste ?

Pour des nombres positifs, il n’y en a pas. Pour des nombres négatifs, le « modulo » donne en général un résultat entre 0 et n − 1 (ou du signe de n), alors qu’un « reste » comme le % de JavaScript prend le signe de a.

Autres outils de la catégorie Maths et nombres

Les 63 outils de la catégorie Maths et nombres

Envoyer un avis