Le cadeau de Noël de Fermat

Le 25 Décembre 1640, Fermat fit un très joli cadeau, non seulement à son correspondant de l’époque, à savoir Mersenne, mais surtout aux mathématiques. Dans une lettre écrite le jour de Noël 1640, Fermat énonça un très joli théorème d’arithmétique: le théorème des deux carrés.

Malheureusement, et comme souvent, ce théorème fut donné sans vraie démonstration et il fallut attendre Euler (dans une lettre à Goldbach datée du 12 Avril 1749) pour avoir une première preuve de ce théorème.

Le théorème des deux carrés

Voici un extrait de cette fameuse lettre de Fermat (les œuvres complètes se trouvant ici ; vous pourrez trouver la lettre complète à la fin de cet article):Extrait_letrre_du_25_decembre_1640En termes plus modernes, voici donc ce qu’affirme le théorème des deux carrés:

Soit p un nombre premier. Alors p s’écrit comme la somme de deux carrés si, et seulement si, p=2 ou p \equiv 1 \mod[4]

(En outre, Fermat affirme que cette décomposition est unique. Et il affirme aussi que p^2 s’écrit aussi comme une somme de deux carrés de façon unique. Mais nous ne nous occuperons pas de cela dans cet article…)

Par exemple, si on prend p=13, alors il est clair que le reste dans la division euclidienne de 13 par 4 est bien 1 (13 = 4 \times 3 + 1) et on voit facilement que 13 peut effectivement s’écrire comme une somme de deux carrés: 13 = 3^2 + 2^2.

A contrario, le nombre 11 n’est pas de la forme 4k+1 (car 11 = 4 \times 2 + 3) et donc il ne peut pas s’écrire comme la somme de deux carrés.

Mais, étant donné un nombre premier p congru à 1 modulo 4 (c’est-à-dire de la forme 4k+1), comment détermine-t-on en pratique deux entiers x et y tels que p = x^2 + y^2 ? Parce que c’est bien beau de prendre l’exemple tout gentil de p=13, mais si on prend p = 1 238 761 ? (qui est bien premier et qui est bien de la forme 4k+1, je vous rassure).

Dans la suite, nous allons présenter une méthode due à Euler (merci Papa Euler !) qui permet d’obtenir une telle décomposition en somme de deux carrés. Nous allons tout d’abord la présenter sur un exemple, puis nous la présenterons dans le cas général (car elle aura le bon goût de se généraliser), ce qui nous permettra de démontrer proprement le théorème des deux carrés de Fermat !

Un exemple

Nous allons décomposer 509 en une somme de deux carrés. Le nombre 509 est bien premier et il est bien congru à 1 modulo 4 (509= 4 \times 127 + 1).

1ère étape – On commence par décomposer un multiple de 509 en une somme de deux carrés:

Plus précisément, on commence par chercher un entier u tel que u^2 + 1^2 = m \times 509 (m \in \mathbb{N}). L’existence d’un tel entier u vient d’une propriété dont nous reparlerons plus tard et qui est liée au fait que 509 \equiv 1 \mod[4]. Nous verrons même plusieurs façons de trouver un tel u en pratique. Mais pour l’instant, je vous le donne: u=208. Ainsi,

208^2 + 1^2 = 85 \times 509

Retenez bien cette valeur de 85, elle nous sera utile dans la suite.

2ème étape – A partir d’une décomposition en somme de deux carrés d’un multiple de 509, on détermine une décomposition en somme de deux carrés d’un multiple de 509 plus petit:

Pour cela, on commence par choisir des entiers r  et s tels que - \frac{85}{2}< r \leq \frac{85}{2} et - \frac{85}{2} < s \leq \frac{85}{2} et tels que:

\begin{cases} r \equiv 208 \mod[85] \\ s \equiv 1 \mod[85] \end{cases}

Il est clair que la valeur s=1 convient, et pour r, on prend la valeur r=38. Mais cela reste assez mystérieux pour le moment… Pourquoi avoir pris r et s ainsi ? Voici l’explication: tout d’abord, r^2 + s^2 est un multiple de 85:

38^2 + 1^2 = 17 \times 85

D’autre part, quand on calcule (r^2 + s^2)(u^2 + 1^2) , on obtient évidemment un multiple de 509:

(r^2 + s^2)(u^2 + 1^2) = (38^2 + 1^2)(208^2 + 1^2) = (17\times 85) \times (85\times 509)

C’est à ce moment-là qu’on utilise une très belle et astucieuse égalité due au mathématicien Brahmagupta qui nous dit que:

(38^2 + 1^2)(208^2 + 1^2) = (38 \times 208 + 1 \times 1)^2 + (38 \times 1 - 1 \times 208)^2 = 7905^2 + 170^2

On en déduit donc que:

7905^2 + 170^2 = (17 \times 85)\times (85 \times 509)

Et là, la magie de Noël opère car cette égalité est simplifiable ! On peut tout diviser par 85^2 car 7905 et 170 sont des multiples de 85 (comme par hasard !).

Comme 7905 = 85 \times 93 et 170 = 85 \times 2, on en déduit que:

93^2 + 2^2 = 17 \times 509

Nous avons bien obtenu une décomposition en somme de deux carrés d’un multiple de 509 plus petit que celui que nous avions au départ !

3ème étape – A partir de la décomposition précédente, on recommence la 2ème étape jusqu’à trouver une décomposition en somme de deux carrés de 509 lui-même:

C’est le principe de la descente de Fermat en action ! Comme précédemment, on choisit r et s tels que - \frac{17}{2}< r \leq \frac{17}{2} et - \frac{17}{2} < s \leq \frac{17}{2} et tels que:

\begin{cases} r \equiv 93 \mod[17] \\ s \equiv 2 \mod[17] \end{cases}

On trouve r = 8 et s=2. On remarque tout d’abord que

r^2 + s^2 = 8^2 + 2^2 = 68 = 4 \times 17

Le produit (r^2 + s^2)(93^2 + 2^2) vaut donc (4\times17) \times (17 \times 509). Mais l’égalité de Brahmagupta donne:

(8^2 + 2^2)(98^2 + 2^2) = (8\times 93 + 2\times 2)^2 + (8\times 2 - 2 \times 93)^2 = 748^2 + 170^2

On en déduit que

748^2 + 170^2 = (4 \times 17) \times (17 \times 509)

et la magie de Noël opère à nouveau car, comme 748 et 170 sont divisibles par 17, on peut tout simplifier par 17^2 !

(\frac{748}{17})^2 + (\frac{170}{17})^2 = 4 \times 509

donc

44^2 + 10^2 = 4 \times 509

A partir de là, inutile de répéter l’étape 2 car on voit directement qu’on peut tout simplifier par 4:

(\frac{44}{2})^2 + (\frac{10}{2})^2 = 509

c’est-à-dire

\boxed{22^2 + 5^2 = 509}

Le cas général

La démonstration dans le cas général reprend les mêmes idées que dans l’exemple précédent et se décompose en trois étapes:

  1. On commence par trouver un multiple de p qui s’écrit comme une somme de deux carrés, et on peut même chercher une relation de la forme u^2 + 1^2 = mp
  2. Si x^2 + y^2 = mp est une décomposition d’un multiple de p alors il existe une décomposition du type x_1^2 + y_1^2 = m_1 p avec m_1 <m (où on dispose de valeurs explicites pour x_1, y_1 et m_1).
  3. En itérant ce procédé, on finit par tomber sur une décomposition de p en une somme de deux carrés.

Pour ne pas alourdir l’article, j’ai mis les détails de la preuve dans le fichier ci-dessous:

Démonstration du théorème des deux carrés de Fermat

Comment trouver un entier u tel que u^2 \equiv -1 \mod[p] ?

Pour trouver la décomposition en somme de deux carrés d’un nombre premier p, nous avons vu que  la 1ère étape consiste à trouver un entier u tel que u^2 \equiv - 1 \mod[p]. Un tel entier existe si, et seulement si, p \equiv 1 \mod[4]. Voici trois méthodes pour trouver un tel entier:

Méthode 1: la méthode naïve

On calcule u^2 pour u=1, 2, 3, ... jusqu’à ce qu’on trouve une valeur u telle que u^2 \equiv -1 \mod[p]. C’est une méthode qui marche bien si p n’est pas très grand mais qui peut être fastidieuse. Par exemple, dans le cas du nombre 509, il faut tester tous les entiers de 1 jusqu’à 208 avant de trouver un entier qui convienne !

Méthode 2: le Théorème de Wilson

Comme on l’a démontré dans le fichier pdf, le théorème de Wilson permet de donner une valeur explicite pour u. Il  s’agit de u = 1 \times 2 \times \cdots \times \frac{p-1}{2} \mod[p] c’est-à-dire \left(\frac{p-1}{2} \right)!. Dans l’exemple du nombre 509, cette méthode nous aurait donné u=301 (et donc 301^2 \equiv - 1 \mod[509]). Le désavantage de cette méthode est que, puisque u est une factorielle, son calcul (même s’il est fait modulo p) peut devenir rapidement long !

Méthode 3: L’algorithme de Shanks

Il existe un algorithme violemment efficace pour calculer une racine carrée modulo p (car c’est bien une racine carrée de -1 (modulo p) que l’on cherche ici…) et qui a été donnée par un certain Shanks en 1972. Je ne vais pas rentrer dans les détails (car ça commence à se compliquer), mais vous pouvez consulter la page Wikipédia à ce sujet (à condition de savoir lire l’Anglais…):  http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

Voici une implémentation en Python qui permet de trouver la décomposition en somme de deux carrés d’un nombre premier, qui utilise l’algorithme de Shanks:

Algorithme de décomposition d’un nombre premier en somme de deux carrés

L’efficacité de l’algorithme de Shanks se voit très bien quand p est très grand (plusieurs dizaines de chiffres). Par exemple, prenez le nombre premier à 100 chiffres suivant:

p = 207472224677348520782169522210760858748099647472 1117292752992589912196684750549658310084416732550077

L’algorithme renvoie quasi-instantanément la décomposition suivante:

p = x^2 + y^2

avec

x = 43983421497074452264774896689221094115373994804726

et

y = 11839800681775608173647727352124286777630222817499

(Si vous ne me croyez pas, faites le calcul par vous-même ! HAHA) Maintenant, essayez de trouver la décomposition en somme de deux carrés d’un nombre premier de ne serait-ce que 20 chiffres avec la méthode de Wilson… Vous en aurez probablement pour un long, très long moment !

Et pour répondre à la question posée au tout début de l’article, la décomposition en somme de deux carrés de p = 1 238 761 est:

1238761 = 269^2 + 1080^2

Note:

Cliquez ici pour lire la lettre de Fermat complète (qui est assez longue mais très intéressante !)

Et joyeux Noël à tous !

Publicités
Cet article, publié dans Arithmétique, est tagué , , , , , , . Ajoutez ce permalien à vos favoris.

7 commentaires pour Le cadeau de Noël de Fermat

  1. Anonyme dit :

    Merci beaucoup pour ce cadeau mathématique, qui fait suite à celui que j’ai reçu hier et que je recommande : http://www.cnrs.fr/insmi/spip.php?article983

  2. Anonyme dit :

    Bonjour.

    Merci pour cet article. Un joli cadeau !

    PS: une petite coquille dans les titres des étapes 1 et 2 où on lit « … un multiple de 401… » au lieu de « … un multiple de 509… ».

    • blogdemaths dit :

      Voilà qui est modifié !
      (J’avais commencé par prendre l’exemple du nombre premier 401 avant de me rendre compte qu’on a la décomposition évidente 401 = 20^2 + 1^2… ce n’était donc pas un exemple très passionnant !)

      Content que ce cadeau plaise à mes lecteurs 😉

  3. J’aime moi aussi cet article! Et, comme à l’ordinaire, je ferai un petit commentaire : de nos jours, l’identité de Brahmagupta est devenue une « trivialité ». Bien entendu qu’en développant ses membres, on constate leur égalité — çà, c’est banal. Ce que je veux dire, c’est qu’aujourd’hui, il est beaucoup plus simple de la trouver : il suffit d’élever au carré l’égalité entre le module du produit de deux nombres complexes et le produit de leurs modules. La même chose avec les quaternions et les octonions nous donnerait des identités faisant intervenir des sommes de quatre puis de huit carrés. Le problème de trouver des identités exprimant un produit de somme de carrés comme une somme de carrés remonte à Hurwitz. Radon s’en est également occupé. Il est loin d’être complètement résolu et, tout récemment, l’utilisation d’algèbres de groupe tordues a permis de trouver de nouvelles familles d’identités de cette sorte. L’idée est toujours celle de Hurwiz : se ramener à des circonstances dans lesquelles la norme d’un produit est égale au produit des normes.

    Bonne continuation dans la rédaction de ce beau blog!

  4. Ping : Le théorème de Wilson | Blogdemaths

  5. Ping : 2017, année des cubes | Blogdemaths

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s