Lorsque l'on considère la division euclidienne de a par n, on obtient un reste. Les valeurs possibles de ce reste sont limitées : il n'y en a que n. Voilà un nouveau point de vue permettant de simplifier de nombreux calculs et de considérer bien des problèmes sous un autre angle !

Un enfant un peu curieux pourrait se demander pourquoi ses parents lui font prendre un « quatre-heures » vers seize heures. Et pourquoi, lorsqu'il est dix heures, quatre heures après, il est deux heures. Voilà bien de curieuses additions… L'idée qui se cache derrière tout cela est que, lorsque midi sonne, on peut recompter les heures en partant de zéro. Ainsi, on peut assimiler « 5 heures » et « 17 heures » : la différence entre ces deux horaires est de douze heures. Dit autrement, 5 et 17 ont le même reste dans la division euclidienne par 12.

 

Pourquoi se limiter aux horloges dont le cadran est partagé en douze secteurs ? Que se passerait-il avec des cadrans de dix heures ? Et de trente-sept heures ? Le mathématicien, malicieux et imaginatif, ne peut s'empêcher de généraliser cette idée. C'est ainsi que se construisent les congruences.

 

 

 

On a besoin de deux entiers a et b et d'un entier naturel n (au moins égal à 2). On dira que a et b sont congrus modulo n s'ils ont le même reste dans la division euclidienne par n. De façon équivalente, leur différence a – b est un multiple de n. On note cela a  b (mod n). Par exemple : 9  24 (mod 5).

Tout se passe bien avec l'addition : si a  b (mod n) et a'  b' (mod n), alors a + a'  b + b'(mod n). Il en va de même pour la multiplication par un entier k : si a  b (mod n), alors ka   kb (mod n). Mais attention ! Les divisions deviennent problématiques. Ce n'est pas parce que 2x  6 (mod 10) que x  3 (mod 10). Pensez au cas où x = 8…

 

Travailler avec les congruences revient à se concentrer sur les restes dans les divisions euclidiennes. Cela peut permettre de limiter les cas à étudier. Cherchons par exemple le nombre d'entiers premiers triplets, c'est-à-dire de triplets de la forme (p, p + 2, p + 4) où p, p + 2 et p + 4 sont des nombres premiers. Pour p = 3, on trouve le triplet (3, 5, 7). Mais si p est différent de 3, alors on a p  1 (mod 3) ou p  2 (mod 3) car p est premier. Si p  1 (mod 3), alors p + 2  0 (mod 3) et n'est pas premier. Si p  2 (mod 3), alors p + 4  0 (mod 3) et n'est pas premier. Ainsi, les seuls entiers premiers triplets sont 3, 5 et 7.

Les puissances se manipulent aussi aisément dans le contexte des congruences : si a    b (mod n), alors a^k   b^k (mod n) pour tout entier naturel k. On peut ainsi facilement déterminer les deux derniers chiffres de 71 777 par exemple. En effet, un petit calcul à la main montre que 7⁴   1 (mod 100). On a donc 7^4×444   1⁴⁴⁴ (mod 100) et 7^{4×444 + 1}   1 × 7 (mod 100). Autrement dit, 7^{1 777}   7 (mod 100), donc 7^{1 777} se termine par 07.

Les congruences permettent aussi de construire de nouveaux tests de divisibilité (voir plus bas). À titre d'exemple, comme 1000 est congru à – 1 modulo 13, pour savoir si 314159265407 est un multiple de 13, il suffit d'écrire que 314 × 1 000³ + 159 × 1 000² + 256 × 1 000 + 407 est congru a – 314 + 159 – 265 + 407 modulo 13. Ce calcul donne – 13 : la réponse est oui ! 

 

 

 

En arithmétique, les nombres premiers ne sont jamais bien loin. Combinés avec les congruences, ils donnent des résultats aussi élégants que féconds. Au XVII^e siècle, le Gascon Pierre de Fermat a énoncé un « grand théorème » devenu célèbre pour avoir résisté aux mathématiciens pendant plus de trois siècles. Mais le prince des amateurs, comme il est parfois surnommé, a aussi énoncé en 1640, dans une lettre à son ami Bernard Frénicle de Bessy, un « petit théorème », démontré quelques années plus tard par Gottfried Leibniz puis Leonhard Euler. Ce théorème affirme que a^p–1   1 (mod p) pour tout nombre premier p et tout entier a qui n'est pas un multiple de p.

Par exemple, on a bien 1^5–1   1 (mod 5), 2^5–1   16   1 (mod 5), 3^5–1  81   1 (mod 5) et 4_^5–1   256   1 (mod 5).

Les retombées de ce théorème sont incommensurables ! Il est utilisé dans de nombreuses méthodes de cryptographie. Il intervient en particulier dans la méthode de chiffrement RSA, un algorithme créé par Ronald Rivest, Adi Shamir et Leonard Adleman en 1977 et aujourd'hui massivement utilisé dans les transactions financières et les échanges d'information sur Internet. La sécurité des méthodes de chiffrement repose le plus souvent sur la difficulté à décomposer un très grand nombre entier en produit de facteurs premiers. Là aussi, le petit théorème de Fermat intervient : il permet de construire des tests de primalité (ou, plus exactement, des tests prouvant qu'un nombre n'est pas premier).

Attention : ce n'est pas parce qu'un nombre p vérifie a^p–1   1 (mod p) pour tout entier a plus petit que p que p est forcément premier. Dans les années 1910, le mathématicien américain Robert Carmichael donne les premiers exemples de nombres qui ne sont pas premiers et qui vérifient pourtant la conclusion du petit théorème de Fermat. C'est le cas de 561 et de 1 105. Les nombres de Carmichael, c'est ainsi qu'on les nomme maintenant, sont encore aujourd'hui à l'origine de recherches fructueuses.

En 1994, William Robert Alford, Andrew Granville et Carl Pomerance ont démontré qu'il en existait une infinité. En 2012, Thomas Wright est allé encore plus loin en démontrant qu'il existe une infinité de nombres de Carmichael congrus à a modulo M pour tout couple d'entiers a et M premiers entre eux. Dit autrement, toute progression arithmétique de la forme (a + kM)_k≥1 avec a et M des entiers premiers entre eux contient une infinité de nombres de Carmichael.

 

Le petit théorème de Fermat a aussi permis à Leonhard Euler de mettre en défaut une conjecture de… Pierre de Fermat lui-même ! Ce dernier pensait que tous les nombres de la forme  étaient premiers. C'est vrai pour n ≤ 4, mais pour n = 5 tout s'écroule ! Euler a trouvé à la main que  (soit 4294967297) est divisible par 641. Il a pu économiser ses calculs en utilisant astucieusement le petit théorème de Fermat et établir ce résultat en n'effectuant que quatre divisions !

Le génie suisse ne s'est pas arrêté là et a aussi généralisé le résultat de Fermat : pour tout entier naturel n, et pour tout entier a premier avec n, on a   1 où  est l'indicatrice d'Euler, c'est-à dire le nombre d'entiers compris entre 1 et n et premiers avec n.

Tout ceci n'est qu'un petit aperçu de ce qu'offrent les congruences. On pourra retenir que la portion congrue des divisions euclidiennes a… de beaux restes !