Fermat, magistrat de son état, était passionné de mathématiques, d'arithmétique surtout, et il a toujours eu beaucoup d'amis fanatiques eux aussi de mathématiques. C'est dans une lettre à l'un d'eux, Bernard Frenicle de Bessy, mathématicien, astronome, mécanicien, mais aussi spécialiste de théorie des nombres et de combinatoire, qu'il dévoila pour la première fois, le 18 octobre 1640, l'énoncé à qui on donnera par la suite le nom de petit théorème de Fermat. Le résultat a depuis fait son chemin et trouvé des applications jusqu'à aujourd'hui.
D'abondantes explications
« Tout nombre premier mesure infailliblement une des puissances – 1 de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre donné – 1 ; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont à la question. » Tel est l'énoncé écrit de la main de Fermat à son ami (voir en encadré)…
L'exégèse du texte de Fermat.
Dans le souci d'éclairer ses affirmations, Fermat donne aussitôt quelques exemples. Il choisit comme « progression » celle des puissances de 3, dont il donne la liste : 3, 9, 27, 81, 243, 729… Considérant ensuite le nombre premier p = 13, il explique fort doctement que 13 divise 33 – 1 (soit 26), où l'exposant 3 est sous-multiple de 12 (12 = 13 – 1), puis que 729 (égal à 36) est tel que 13 divise aussi 729 – 1, parce que l'exposant 6 de 3 est multiple du premier exposant, 3. Il conclut enfin, fidèle à lui-même : « Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers ; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long. » Des explications, donc, mais de démonstration, point… Il est vrai qu'il n'était pas d'usage à l'époque de publier les preuves des résultats que l'on avançait ! Et pourtant, le théorème était né, sans nom d'ailleurs, puisqu'il faut attendre Gauss en 1801 pour en parler comme d'un « théorème remarquable, tant par son élégance que par sa grande utilité » et préciser qu'il s'appelle « ordinairement Théorème de Fermat, du nom de l'inventeur ». La dénomination « petit théorème de Fermat » (kleine Fermatsche Satz) viendra, elle, en 1913 seulement, de la part du mathématicien allemand Kurt Hensel.
Nous avons aujourd'hui une préférence pour l'énoncer ainsi : si p est un entier naturel premier et a un autre entier naturel premier avec p, alors a p–1 – 1 est divisible par p. Soit, pour continuer la liste prévue par Fermat : 37–1 – 1 est divisible par 7, 311–1 – 1 l'est par 11 et 313–1 – 1 par 13. Il se formule de manière encore plus concise dans le langage des congruences, introduit par Gauss un siècle plus tard : si p est un entier naturel premier et si a est premier avec p, alors a p–1 – 1 / 0 modulo p.
Cette assertion est équivalente à : si p est un entier naturel premier et si a est premier avec p, alors a p / a modulo p. En effet, le premier énoncé implique le second puisque si a p–1 / 1 modulo p alors a p / a modulo p. Réciproquement, le second implique le premier, car dire que a p / a modulo p c'est dire que p divise a p – a, qui est égal à a (a p–1 – 1). Or p ne divise pas a, donc – et c'est Gauss qui, par son lemme, nous permet de conclure – p divise a p–1 – 1.
Plus tard, les démonstrations
Nous avons là un théorème bien énoncé, assorti de multiples exemples, mais toujours pas démontré ! Il faut attendre 1736 pour voir Euler, dans les Mémoires de Saint-Pétersbourg, en donner une première démonstration, qui sera reprise par le mathématicien français Adrien-Marie Legendre dans sa Théorie des nombres (1798). Elle repose, comme celle d'Euler, sur le développement du binôme (1 + x)c, où le nombre premier c divise tous les coefficients du développement sauf le premier et le dernier. Legendre conclut, en mettant en œuvre – sorte de récurrence à l'envers – une « descente finie » qui, partant de N = 1 + x, mène à N – 1… puis à 0, écrivant que, si Nc – 1 = (N – 1)c, en « omettant » les multiples de c, comme s'il faisait déjà appel aux congruences, alors
Nc – N = (N – 1)c – (N – 1) = (N – 2)c – (N – 2) = … = (N – N)c – (N – N),
qui est évidemment égal à 0.
Leonhard Euler avait, entre-temps, donné du théorème de Fermat une autre démonstration, intéressante à double titre : tout d'abord, avec comme libellé « Si le nombre a est premier avec p et que l'on forme la progression géométrique 1, a, a2, a3, a4, a5, a6, a7 etc. il y a de nombreux termes, qui divisés par p, laissent pour reste 1 et les exposants de ces termes forment une progression arithmétique. », elle reprend exactement la démarche de Fermat, et ensuite, elle utilise le principe des tiroirs, cher à tous les amateurs de jeux mathématiques.
Le nombre de termes de la progression en question est infini, certes, nous dit cette démonstration, mais il ne peut y avoir au plus que p – 1 restes dans la division par p. C'est donc, principe des tiroirs oblige, que deux nombres de la progression, par exemple a m et a n, ont même reste r. Dans ce cas, a m – a n est divisible par p. Or, vu la configuration des termes de la progression, a m – a n = a n (a m-n – 1), ceci étant divisible par p. Comme p est premier avec a, il l'est avec tous les termes de la progression, donc avec a n et c'est alors l'autre facteur, a m-n – 1, qui est divisible par p. C'est dire que si q = m – n, alors a q – 1 est divisible par p, ainsi que toutes les puissances a2q, a3q, a4q… diminuées de 1, avec des exposants en progression arithmétique.
D'innombrables démonstrations de ce théorème maintenant célèbre ont vu le jour au cours de l'histoire, leur niveau de difficulté allant de l'arithmétique élémentaire à la théorie des groupes. Leibniz en a donné une semblable à celle de Euler, Gauss en donne plusieurs dans ses Disquisitiones arithmeticae.
Arrêtons-nous sur l'une d'elles, originale, qui fait appel à un autre principe, cher au créateur américain de jeux mathématiques Martin Gardner, le principe du double dénombrement (double counting). Il s'agit d'utiliser ici le dénombrement, de deux façons différentes, des n mots de longueur p écrits avec un alphabet de a lettres, où il existe au moins deux symboles différents, p étant un nombre premier.
Premier décompte : il y a au total a p mots de longueur p écrits avec cet alphabet, desquels il faut retirer les a mots constitués d'une seule et même lettre. Nous en sommes donc à n = a p – a mots.
Deuxième décompte : on groupe ces mots par ensembles pouvant être déduits l'un de l'autre par permutation circulaire, un peu comme un collier qui, une fois refermé, ne permet plus de distinguer par quelle perle on l'a commencé. Il existe p façons différentes de couper le collier entre les perles et si p est premier, on peut former p mots de p symboles une fois le collier ouvert car chaque permutation donne un mot différent. Par contre, si p n'est pas premier, plusieurs permutations peuvent donner le même mot. Ainsi, si p est premier, n = p × (nombre de colliers) et on vient de démontrer que le nombre de mots est multiple de p, ou encore que a p – a était, si p est premier, multiple de p. Voilà le petit théorème de Fermat démontré de manière plutôt ludique… non ?
La maison natale de Fermat à Beaumont-de-Lomagne
(Tarn-et-Garonne).
D'intéressantes applications
Le petit théorème de Fermat, s'il a donné lieu à des démonstrations originales et dignes d'intérêt, utilisant des méthodes variées, a permis aussi de fructueuses applications. L'une d'elles peut être une façon de repérer si un nombre est premier. Pauvre Fermat, qui n'avait, pour pouvoir répondre à l'interrogation de Mersenne de savoir si le nombre 100 895 598 169 est premier, que des méthodes arithmétiques très élémentaires comme celle de le décomposer en différence de deux carrés ! Après des milliers d'itérations, il aurait pu éventuellement trouver que ce nombre infernal était égal à 505 3632 – 393 0602, mais il avait sans doute sa méthode à lui pour « trouver en l'espace d'un jour s'il est premier ou non ». Son théorème va permettre une avancée sur ce point : à défaut de savoir si un nombre est premier, il nous fera savoir s'il… ne l'est pas. En effet, pour tester si un nombre p est premier, on peut choisir a < p, calculer a p–1 modulo p : si le résultat est différent de 1, alors p est à coup sûr composé. Par contre, on ne peut rien conclure si le résultat est égal à 1, car la réciproque du théorème de Fermat est fausse : a p–1 peut très bien être congru à 1 modulo p sans que p soit premier. Les nombres de Carmichael, par exemple, sont parmi ces faux-amis : 561 est égal à 3 × 11 × 17… et pourtant 5560 est congru à 1 modulo 561.
Une application beaucoup plus fructueuse du petit théorème de Fermat est l'invention du codage RSA. Ce dernier (voir Cryptographie et Codes secrets, Bibliothèque Tangente 26, 2013) repose en effet sur le fait que, p et q étant deux nombres premiers et k un entier tel que k – 1 soit divisible par (p – 1)(q – 1), alors, pour tout entier x, x k – x est divisible par pq. Cette propriété est une conséquence directe du petit théorème de Fermat :
Comme k est divisible par p – 1, il existe K entier tel que k – 1 = K (p – 1), ou k = 1 + K (p – 1).
D'où x k – x = x (x k–1 – 1) = x [(x K) p–1 – 1] est divisible par p d'après notre fameux théorème.
On peut ensuite démontrer que, si k – 1 est divisible par (p – 1)(q – 1), alors, pour tout x, xk – x est divisible par le produit pq.
Ainsi, Ron Rivest, Adi Shamir et Leonard Adleman, les inventeurs en 1977 de ce système de cryptographie, se sont appuyés sur un théorème énoncé par Fermat en 1640… Même s'il n'en avait pas donné la démonstration, le magistrat-mathématicien a tout de même laissé là un bel héritage mathématique !
Lire la suite