Le petit théorème de Fermat affirme que si p est un nombre premier (comme 2, 3, 5, 7, 11 ou 5 273) et si a est un entier non divisible par p alors a ^p–1 – 1 est divisible par p. Pour des petites valeurs de a et de p, le résultat n'est peut-être pas spectaculaire et le théorème ne semble pas si utile. Mais pour des valeurs assez grandes, les calculs deviennent vite inaccessibles et le théorème peut nous sauver la mise.

Les démonstrations de ce théorème sont nombreuses et parfois très originales. Une des plus classiques consiste à considérer la liste des multiples de a suivante : a, 2a, 3a, 4a… (p – 1) a. Notons r₁, r₂… r_p–1 les restes respectifs dans la division euclidienne de ces nombres par p. Aucun de ces restes n'est égal à 0 car aucun des multiples de a de notre liste n'est divisible par p (voir l'encadré sur le théorème de Gauss). En outre, ces restes sont tous différents. En effet, supposons que rk et rk' sont égaux, avec k ≤ k'. On peut alors écrire que k'a – ka, soit (k' – k) a, est un multiple de p. Le même argument que précédemment impose que p divise k' – k, et comme k' – k est un entier naturel strictement inférieur à p, la seule valeur possible pour cette différence est 0. Autrement dit, k = k'.

Les valeurs prises par ces restes sont donc 1, 2, 3… et p – 1, mais pas forcément dans cet ordre. Il suffit donc maintenant de constater que le produit a × 2a × 3a × … × (p – 1) a est congru à 1 × 2 × 3 × … × (p – 1) modulo p. Il s'en suit que a ^p–1 (p – 1)! est congru à (p – 1)! modulo p. Dit autrement, p divise a ^p–1(p – 1)! – (p – 1)! mais pas (p – 1)!. D'après le théorème de Gauss, p divise bien a ^p–1 – 1

Euler entre en scène

Le mathématicien suisse Leonhard Euler, scientifique au génie incommensurable, s'est toujours passionné pour la théorie des nombres et l'œuvre de Pierre de Fermat en particulier, proposant une démonstration de son « petit théorème » en 1736. Il s'est aussi intéressé au « grand théorème » de Fermat, qui affirme que l'équation xⁿ + yⁿ = zⁿ (où x, y et z sont des entiers non nuls) n'admet aucune solution pour tout entier n strictement supérieur à 2. Il démontre ainsi le cas n = 3 et conjecture que tout puissance n-ième est la somme d'au moins n puissance n-ième. Cette conjecture tiendra jusqu'en 1966, quand Leon Lander et Thomas Parkin proposeront le contre-exemple suivant : 27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵.

Le premier exploit d'Euler à propos des travaux de Fermat concerne les nombres de Fermat. Ces entiers, notés F_n, sont égaux à 2²ⁿ + 1. Les premiers nombres de Fermat sont 3, 5, 17, 257 et 65 537. Ces cinq nombres étant premiers, Pierre de Fermat pensait qu'il en était de même pour les autres. Hélas, les nombres de Fermat devenant vite très grands, il est bien difficile de tenter de le vérifier à la main ! C'est là que Leonhard Euler fait preuve de plus d'une astuce et ce, grâce au petit théorème de Fermat…

Notons p un diviseur premier de  On a alors  et donc  On peut établir que 2⁶ = 64 est en fait le plus petit exposant strictement positif k tel que 2^k / 1 (mod p). Par ailleurs, le petit théorème de Fermat nous indique que 2 ^p–1 aussi est congru à 1 modulo p.

Effectuons la division euclidienne de p – 1 par 64. On obtient p – 1 = 64q + r, avec 0 ≤ r < 64.

Comme 2⁶⁴ / 1 (mod p), on a : 2^64q+r = (2⁶⁴)^q × 2^r / 2^r (mod p). 

On en déduit donc que 2^r / 1 (mod p) et, comme 0 ≤ r < 64, la seule possibilité est r = 0. On établit ainsi que p est de la forme 64k + 1.

Dans ces conditions, Euler n'avait plus qu'à tester différentes valeurs de k. Pour k = 1, 2, 5, 6 ou 8, le nombre 64k + 1 n'est pas premier. Pour k = 3, on trouve le nombre premier 193, mais la division par 193 de F₅ donne un reste de 109. De même, pour k = 4, 7 et 9, on trouve les nombres premiers 257, 449 et 577, mais les divisions de F₅ par ces nombres donnent comme restes respectifs 2, 325 et 288. Heureusement, pour k = 10, on trouve finalement que F₅ = 641 × 6 700 417. En suivant ce chemin, il n'y a aucun calcul insurmontable à la main !

La conjecture de Fermat tombe ainsi à l'eau et à l'heure actuelle, aucun autre nombre de Fermat premier n'a été découvert. On ignore même s'il en existe ! On sait qu'ils sont tous composés de F₅ à F₃₂, mais après, les informations sont très lacunaires…

Et si p n'est pas premier ?

 Leonhard Euler ne s'est cependant pas arrêté à ce petit numéro virtuose sur la décomposition de F₅. Vingt-huit ans plus tard, il généralise le petit théorème de Fermat pour des nombres entiers quelconques, qui ne sont pas forcément premiers. Il affirme, dans un théorème qui porte maintenant son nom, que si a est un nombre premier avec n alors n divise a^φ(n) – 1. Quel est donc cet exposant φ (n) ? Il est tout simplement égal au nombre d'entiers compris entre 1 et n qui sont premiers avec n. Par exemple, φ(12) est égal à 4 car les seuls entiers inférieurs à 12 et premiers avec 12 sont 1, 5, 7 et 11. Ainsi, pour tout entier a qui n'est pas premier avec 12, le théorème d'Euler permet d'établir que a⁴ – 1 est divisible par 12. L'application φ est appelée indicatrice d'Euler (bien sûr !).

Si p est un nombre premier, il est premier avec tous les entiers de 1 jusqu'à p – 1 et on a donc φ(p) = p – 1 On retrouve alors le petit théorème de Fermat.

La fonction indicatrice d'Euler est d'une importance capitale en arithmétique ; elle a des applications très concrètes dans le domaine de la cryptographie. On la retrouve d'ailleurs dans le système de codage RSA : si p et q sont deux nombres premiers, φ(pq) = (p – 1)(q – 1)

Étant donné l'utilité de l'indicatrice d'Euler, plusieurs propriétés permettent de calculer ses valeurs, et en particulier, si p₁, p₂… p_n sont les nombres premiers intervenant dans la décomposition d'un entier n en produit de facteurs premiers, alors φ(n) est égal au produit de n par :

\( \left(1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) ... \left( 1 - \frac{1}{p_n} \right)\)
  

La réciproque du petit théorème de Fermat est-elle vraie ? Autrement dit, si l'on trouve un nombre n tel que, pour tout entier a premier avec n, on a a^n–1 / 1 (mod n), alors n est-il forcément premier ? La réponse est non ! De tels nombres sont appelés nombres de Carmichael. Le plus petit nombre de Carmichael est 561, qui est égal à 3 × 11 × 17. Quelques années avant l'étude menée par Robert Carmichael au début du XX^e siècle, le mathématicien allemand Alwin Reinhold Korselt (1864-1947) avait déjà trouvé une caractérisation de ces nombres. Son critère établit qu'un nombre composé n est un nombre de Carmichael si, et seulement si, pour tout nombre premier p divisant n, p² ne divise pas n et p – 1 divise n – 1. Avec ce critère, il devient très aisé de vérifier que 561 est bien un nombre de Carmichael.

Robert Daniel Carmichael (1879–1967)

On dispose même de formules explicites pour en produire d'autres. Par exemple, tout nombre de la forme (6k + 1)(12k + 1)(18k + 1) est un nombre de Carmichael, à condition que ces trois facteurs soient premiers. Cette formule ne donne hélas pas tous les nombres de Carmichael : pour k = 1, on trouve 7 × 13 × 19 = 1 729.

William Alford, Andrew Granville et Carl Pomerance ont démontré en 1994 qu'il existait une infinité de nombres de Carmichael. Heureusement, ils sont « assez rares » ! Cela permet donc de créer un test de primalité probabiliste. Si un nombre entier n vérifie a ⁿ  \( \equiv\) a (mod n) pour tout nombre a, il est « très vraisemblablement premier ». On peut limiter les tests : par exemple, si 2 ^n–1 \( \equiv\) 1 (mod n), alors n est probablement premier ; s'il ne l'est pas, on dit qu'il est pseudo-premier de base 2. Il n'y a que deux cent quarante-cinq nombres pseudo-premiers de base 2 inférieurs à 1 000 000. En testant aussi si le nombre est pseudo-premier de base 3, 5 ou 7, on diminue encore la probabilité de faire une erreur !

Polygones constructibles et nombres de Fermat

 Revenons aux nombres de Fermat : ils ont aussi des applications en géométrie ! Les savants grecs se posaient de nombreuses questions sur les constructions à la règle et au compas. Rien de plus simple que de construire un triangle équilatéral. La réalisation d'un carré n'est pas très compliquée non plus. L'hexagone régulier s'obtient assez facilement, comme le savent les écoliers férus de rosaces à colorier. Dessiner un pentagone régulier demande déjà plus d'astuce. Que dire des polygones réguliers à n côtés ?

Alors qu'il n'a que 19 ans, Carl Friedrich Gauss découvre une méthode pour construire à la règle et au compas un polygone régulier à dix-sept côtés (heptadécagone). Il va encore plus loin et établit un joli théorème permettant de caractériser les polygones réguliers constructibles avec ces deux outils de base : il faut et il suffit que le nombre n de côtés soit un produit de nombres de Fermat premiers et d'une puissance de 2. Comme il n'y a que cinq nombres de Fermat premiers connus actuellement, cela limite assez fortement le nombre de polygones réguliers constructibles à la règle et au compas en se ramenant à trente-deux cas de base. Aussi, affiner notre connaissance des nombres de Fermat permettrait très concrètement de mieux cerner les polygones réguliers constructibles à la règle et au compas !

On le voit, le petit théorème Fermat et ses avatars n'ont pas fini d'alimenter les travaux les plus pointus et d'être la source d'applications des plus novatrices.