algorithme de Serret

Prenons le nombre premier 13. Treize objets se partagent en un carré de 3 sur 3 et un carré de 2 sur 2 : 9 + 4 = 13. La figure matérialise cette décomposition en deux groupes carrés.

L’algorithme de Serret transforme cette observation en démarche constructive. Pour un nombre premier qui laisse un reste de 1 lorsqu’on le divise par 4, il garantit qu’une telle écriture existe. Sa démarche permet aussi d’obtenir les deux entiers dont les carrés donnent le nombre de départ.

L’algorithme de Serret est une démonstration constructive du résultat des deux carrés pour une famille de nombres premiers. Le nombre de départ, noté p, doit être premier et congru à 1 modulo 4, c’est-à-dire laisser le reste 1 dans la division par 4.

La procédure produit alors deux entiers, notés a et b, qui vérifient $p=a^2+b^{2}p=a^2+b^2$. Le mot « constructif » est décisif : la preuve donne une démarche explicite pour atteindre une représentation, au lieu d’établir seulement son existence. Échanger a et b, ou changer le signe de l’un d’eux, conserve la même somme de carrés.

La propriété avait été énoncée par Fermat puis prouvée par Euler. Serret en a publié en 1848 une version algorithmique sous le titre Sur un théorème relatif aux nombres entiers. L’algorithme désigne donc la construction, tandis que l’égalité obtenue exprime le résultat arithmétique qu’elle certifie.

Soit p un nombre premier. Si $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)p\backslash equiv\; 1\backslash pmod\{4\}$, alors l’algorithme construit deux entiers a et b tels que :

Le point d’arrêt est une paire d’entiers dont les carrés, additionnés, redonnent exactement p. Cette conclusion garantit une égalité entière, sans approximation. Une substitution dans l’égalité fournit le contrôle final.

La donnée nécessaire est un entier p qui satisfait deux contrôles séparés : p est premier, puis le reste de sa division par 4 vaut 1. La sortie attendue est une paire d’entiers a et b vérifiant exactement l’égalité p = a² + b².

Le nombre 2 fournit un contre-cas instructif : il est premier et 2 = 1² + 1², mais son reste modulo 4 vaut 2. L’hypothèse de Serret n’est donc pas satisfaite, même si la conclusion existe ici directement. De même, 9 laisse le reste 1 modulo 4, mais il n’est pas premier ; cette seule congruence ne suffit pas pour appliquer l’algorithme. Dans ces cas, on vérifie la décomposition directement ou l’on emploie un critère adapté à l’entier considéré.

Cet exemple guide le contrôle de la conclusion associée à l’algorithme de Serret pour p = 13 ; il ne déroule pas les opérations de la construction historique. On vérifie la primalité de 13, son reste dans la division par 4, puis l’égalité obtenue. Pour ce petit cas, une recherche parmi les carrés suffit à retrouver et contrôler la représentation.

1. Vérifier la primalité : aucun entier premier inférieur ou égal à √13, soit 2 puis 3, ne divise 13.

2. Effectuer la division par 4 : 13 = 4 × 3 + 1. Ainsi, 13 est congru à 1 modulo 4.

3. Examiner les carrés non négatifs qui ne dépassent pas 13 : 0, 1, 4 et 9.

4. Former la somme 9 + 4 = 13, puis reconnaître 9 = 3² et 4 = 2². On obtient donc a = 3 et b = 2.

Le contrôle final se refait par substitution : 3² + 2² = 9 + 4 = 13. Les deux conditions de départ et l’égalité de sortie sont bien vérifiées.

Pour représenter un nombre premier comme somme de deux carrés, on commence par regarder son reste modulo 4. Si ce reste vaut 1, l’algorithme de Serret fournit le cadre constructif ; sinon, son hypothèse n’est pas remplie.

Pour étudier une preuve d’existence, on repère ce qu’elle livre effectivement. Une preuve seulement existentielle garantit une paire ; une preuve constructive comme celle de Serret donne une démarche pour l’obtenir.

Pour contrôler un résultat calculé, on élève les deux entiers au carré et on additionne. L’égalité exacte avec le nombre premier valide la sortie ; un simple accord approché ne suffit pas dans ce problème d’entiers.

Le théorème des deux carrés de Fermat. Il énonce la propriété arithmétique pour les nombres premiers concernés. L’algorithme de Serret se distingue par son caractère constructif : dans le cas de 13, il ne s’agit pas seulement de savoir que deux carrés existent, mais d’obtenir 3 et 2.

Une recherche exhaustive. Tester toutes les paires jusqu’à trouver 3² + 2² = 13 vérifie ce petit exemple. Cela ne suffit pas à identifier la construction historique de Serret : le critère distinctif est la démarche algorithmique explicite qui accompagne la preuve générale.

Le premier exceptionnel 2. Le seuil p = 2 rappelle que l’hypothèse « reste 1 modulo 4 » est suffisante dans le cadre annoncé, mais ne décrit pas tous les nombres premiers représentables : 2 = 1² + 1² se traite directement.

La primalité oubliée. Le nombre 9 vérifie 9 = 4 × 2 + 1, mais il est composé. Le reste 1 ne permet donc pas, à lui seul, d’invoquer l’algorithme de Serret ; il faut d’abord contrôler que le nombre est premier.

Plusieurs écritures pour une même paire. Les sorties (3, 2), (2, 3), (−3, 2) et (3, −2) donnent toutes 13 après élévation au carré. Il faut comparer les représentations sans tenir compte de l’ordre ni des signes lorsque seule la somme des carrés importe.

Le glossaire arithmétique modulaire précise le langage des restes utilisé dans la condition p congru à 1 modulo 4.

La fiche nombre premier permet de reprendre le premier contrôle exigé avant d’appliquer l’algorithme.

L’article Une histoire de l'arithmétique modulaire replace le calcul sur les congruences dans un cadre historique plus large.