L’arithmétique modulaire et les nombres premiers

Il existe un outil remarquable qui simplifie les raisonnements arithmétiques et facilite la compréhension de bien des propriétés des nombres entiers. Cet outil a été inventé en 1801 par le grand mathématicienmathématicien allemand Carl Friedrich Gauss, alors âgé de 24 ans. Il s'agit de l'arithmétique modulaire. En voici une présentation rapide.

L’arithmétique modulaire et les nombres premiers. © Thor Deichmann, Pixabay, DP

Lorsqu'on lit l'heure, on considère qu'après 23 heures, on passe à 0 heure. De même, il est possible, un entier n supérieur à 1 étant fixé, de calculer modulo n, c'est-à-dire en revenant à zéro dès qu'on atteint n. Si, par exemple, on calcule modulo 24, on aura 23 + 1 = 0 (comme pour l'heure), et aussi 23 + 5 = 4 (5 heures après 23 heures, il est 4 heures) ou 23 + 23 = 22 (23 heures après 23 heures, il est 22 heures), ce qu'on écrira : 23 + 1 = 0 (modmod 24) ; 23 + 5 = 4 (mod 24) ; 23 + 23 = 22 (mod 24) (signalons qu'on utilise parfois le signe ≡ à la place de =).

On peut bien sûr faire des soustractions en arithmétique modulaire : 2 - 5 = 21 (mod 24) (5 heures avant 2 heures, il était 21 heures). On peut aussi faire des multiplications : 2 x 23 = 23 + 23 = 22 (mod 24), ou convertir des nombres négatifs en nombres positifs : -3 = 21 (mod 24) ; 23 = -1 (mod 24) ; 12 = -12 (mod 24).

Un cadran d'horloge fonctionne module 12 plutôt que modulo 24 : c'est la présence ou l'absence du soleil qui nous indique dans quel cycle de 12 heures nous sommes. Sur le cadran ci-dessus on vérifie que six heures après huit heures, il est deux heures, ce qu'on écrit 8 + 6 = 2 (mod 12). © Belin

Principe de l'arithmétique modulaire

Le principe général est simple : quand on calcule modulo n, chaque fois qu'on obtient un résultat qui n'est pas compris entre 0 et n - 1, on ajoute ou l'on soustrait n autant de fois qu'il faut pour revenir dans l'intervalle des nombres de 0 à n - 1. Si a est un nombre entier, calculer a (mod n) revient à déterminer le reste de la division euclidienne de a par n : par exemple, 2.434 = 10 (mod 24), car 2.434 = 24 x 101 + 10. On vérifie que toutes les propriétés suivantes sont satisfaites :

• a + b = b + a (mod n) ; (a + b) + c = a + (b + c) (mod n) ; a + 0 = a (mod n) ;
• pour tout entier a, il existe un entier b tel que a + b = 0 (mod n) ;
• a.b = b.a (mod n) ; (a.b).c = a.(b.c) (mod n) ;
• a.1 = 1.a = a (mod n) ; 0.a = a.0 = 0 (mod n) ;
• a.(b + c) = a.b + a.c (mod n) ; (a + b).c = a.c + b.c (mod n).

L'usage de la notation a = b (mod n) présente diverses variantes. Précisons donc notre point de vue : l'expression a = b = ... = c (mod n) signifie pour nous qu'en ramenant les différents entiers a, b, ..., c, par additions ou soustractions répétées de n, dans un intervalle entre 0 et n - 1, on trouvera le même nombre.

Ce point de vue évite d'avoir à parler de classes d'équivalence, de représentant canonique, etc., et nous permet à chaque instant de ne manipuler que des nombres entiers.

Les langages informatiques offrent une fonction appelée mod, qui correspond à ce calcul modulaire : a et b étant donnés, « a mod (b) » ou « a mod b » ou « mod (a, b) » désignent le reste de la division de a par b.

En pratique, les propriétés précédentes signifient qu'on peut travailler avec le calcul modulo sans craindre d'erreur : lorsqu'on effectue des additions, des soustractions ou des multiplications (mais non des divisions, voir plus loin), on peut se ramener à l'intervalle des nombres de 0 à n - 1 à la fin du calcul, ou bien au stade du calcul qu'on trouve le plus commode, pour à nouveau calculer, etc. Par exemple, pour calculer le reste de la division de 10⁵⁰ par 99, c'est-à-dire 10⁵⁰ (mod 99), on écrit : 10² = 100 = 1 (mod 99), donc 10⁵⁰ = (10²)²⁵ = 1²⁵ = 1 (mod 99). Sans avoir fait de longues divisions, on sait que le reste de la division de 10⁵⁰ par 99 est 1.

Un nombre possède un inverse modulo n s’il est premier avec n

Lorsque deux entiers a et n sont premiers entre eux, on sait qu'il existe deux nombres u et v tels que au + nv = 1. Modulo n, cette égalité devient au = 1 (mod n). Le nombre u est tel que son produit modulo n avec a donne 1. Autrement dit, si a et n sont premiers entre eux, alors a possède un « inverse » modulo n. En utilisant cet inverse, on peut simplifier une équation. Par exemple, si a et n sont premiers entre eux et si l'on a l'égalité 2a = ca (mod n), alors, en multipliant de chaque côté de l'égalité par l'inverse de a modulo n, on trouve : 2 = c (mod n). Cette remarque concernant les inverses est très importante et nous servira fréquemment. En particulier, si p est un nombre premier, alors p est premier avec tous les nombres 1, 2, 3, ..., p - 1, d'où l'on déduit que chacun des nombres 1, 2, 3, ..., p - 1 possède un inverse modulo p.

Comme pour l’addition et la multiplication entre entiers, on dessine les tables « modulo k » ici pour k = 5 et k = 6. © Belin

Afin d'illustrer cette notion d'inverse modulo n, il est intéressant d'écrire les tables d'addition et de multiplication modulo n. À titre d'exemple, les tables modulo 5 et 6 sont représentées ci-contre. Comme 5 est premier, on s'attend à trouver un inverse pour tous les nombres inférieurs à 5 : on vérifie dans la table de multiplication modulo 5 que chaque nombre non nul possède bien un inverse. Ces couples sont repérés par leur produit, égal à 1 et indiqué en rouge :

• l'inverse de 1 est 1, car 1 x 1 = 1 (mod 5) ;
• l'inverse de 2 est 3, car 2 x 3 = 1 (mod 5) ;
• l'inverse de 3 est 2, car 2 x 3 = 1 (mod 5) ;
• l'inverse de 4 est 4, car 4 x 4 = 1 (mod 5).

Et dans la table de multiplication modulo 6 ? On remarque à présent que certains nombres n'ont pas d'inverse. C'est le cas de 2, par exemple : il n'existe aucun nombre a tel que 2a = 1 (mod 6). La raison en est que 2 n'est pas premier avec 6. Conformément à la règle générale énoncée précédemment, les nombres a qui possèdent des inverses sont les nombres premiers avec 6. Ici, seuls 1 et 5 ont un inverse modulo 6.

À titre d'exercice, je vous propose d'établir la table de multiplication modulo 13 et de vérifier que tout nombre non nul possède un inverse. Pour la table de multiplication modulo 14, vous constaterez que seuls 3, 5, 9, 11, et 13, qui sont premiers avec 14, possèdent des inverses.

La table de multiplication modulo 6 indique aussi que 2 x 3 = 0 (mod 6) : le produit modulo 6 de deux nombres non nuls peut être nul. Si l'on calcule modulo un nombre p premier, cela n'est plus le cas : en effet, a.b = 0 (mod p) signifie que p divise a.b, et, comme p est premier, qu'il divise a ou b (puisque p, s'il divise leur produit, est nécessairement un facteur premier de a, de b ou des deux) ; on a donc a = 0 (mod p) ou b = 0 (mod p). Modulo un nombre premier, un produit nul implique donc que l'un des deux facteurs au moins est nul, et le produit de deux facteurs non nuls n'est jamais nul. En résumé, si p est premier :

a.b = 0 (mod p) ⇔ a = 0 (mod p) ou b = 0 (mod p)

En termes savants, on dit que l'ensemble des nombres entre 0 et n - 1, noté Ζ/nZ, constitue un « anneau commutatif » quand on considère les opérations d'addition et de multiplication modulo n. Quand n est premier (tout nombre non nul possède alors un inverse), cet anneau est appelé un « corps ». On a donc une propriété caractéristique des nombres premiers :

l'anneau Z/nZ est un corps ⇔ n est un nombre premier.