critère d'Euler

Élevons au carré les nombres 1, 2 et 3, puis regardons seulement leurs restes dans la division par 7. On obtient 1, 4 et 2 : ce sont les trois carrés non nuls possibles modulo 7. Le critère d’Euler évite de dresser cette liste. Pour un nombre qui n’est pas multiple de 7, il suffit de calculer sa puissance troisième : un reste 1 signale un carré, tandis qu’un reste 6, c’est-à-dire −1 modulo 7, signale un non-carré.

Le critère d’Euler caractérise les résidus quadratiques modulo un nombre premier impair. Soit p ce nombre premier et soit a un entier non divisible par p. L’entier a est un résidu quadratique modulo p lorsqu’il existe un entier k dont le carré a le même reste que a dans la division par p : $k^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)k^2\; \backslash equiv\; a\; \backslash pmod\; p$.

La puissance de a d’exposant (p − 1)/2 donne alors exactement l’un des deux restes 1 ou −1. L’entier a est un résidu quadratique modulo p si et seulement si $a^{(p-1)\mathrm{/}2}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)a^\{(p-1)/2\}\; \backslash equiv\; 1\; \backslash pmod\; p$. Il est un non-résidu quadratique modulo p si et seulement si $a^{(p-1)\mathrm{/}2}\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)a^\{(p-1)/2\}\; \backslash equiv\; -1\; \backslash pmod\; p$. Ces deux équivalences fournissent un verdict, et pas seulement une condition nécessaire. Le cas où p divise a est séparé : la puissance vaut alors 0 modulo p.

Le symbole de Legendre condense les trois verdicts 1, −1 et 0. L’idée se prolonge à l’étude des résidus de puissances supérieures. Employée comme test avec un module supposé premier, elle mène aussi aux pseudo-premiers d’Euler et aux pseudo-premiers d’Euler-Jacobi, qui sont en réalité composés.

Soit p un nombre premier impair et a un entier que p ne divise pas. Alors a est un carré modulo p si et seulement si $a^{(p-1)\mathrm{/}2}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)a^\{(p-1)/2\}\; \backslash equiv\; 1\; \backslash pmod\; p$. S’il n’est pas un carré modulo p, la même puissance est congrue à −1 modulo p. Le calcul se fait par exponentiation modulaire : on réduit les résultats intermédiaires modulo p, sans développer l’entier gigantesque que la puissance pourrait produire.

Le module p doit être premier et impair. Il faut aussi vérifier que a n’est pas divisible par p ; son reste doit donc appartenir à 1, 2, …, p − 1. Sous ces hypothèses, le résultat 1 ou −1 détermine si a possède une racine carrée modulo p, mais il ne fournit pas cette racine.

Avec le module composé 15, le nombre 2 donne 2⁷ ≡ 8 modulo 15 : le verdict attendu n’est ni 1 ni −1. Le critère ne s’applique donc pas. Il faut alors étudier les facteurs premiers du module ou employer un outil adapté aux congruences modulo un entier composé.

On travaille modulo le nombre premier p = 7 et l’on teste successivement a = 2 puis a = 3. L’exposant du critère vaut (7 − 1)/2 = 3.

1. Pour a = 2, on calcule 2³ = 8, donc 2³ ≡ 1 modulo 7. Le critère annonce que 2 est un résidu quadratique.

2. Le contrôle direct retrouve une racine : 3² = 9 ≡ 2 modulo 7. Les carrés de 1, 2 et 3 donnent respectivement les restes 1, 4 et 2 ; les carrés de 4, 5 et 6 répètent ces valeurs. La figure synthétise ce contrôle et le test de puissance.

3. Pour a = 3, on obtient 3³ = 27 ≡ 6 modulo 7. Or 6 représente −1 modulo 7 : le critère annonce que 3 n’est pas un résidu quadratique.

4. La liste des carrés non nuls, {1, 2, 4}, confirme le résultat : 2 y figure, mais pas 3. Les deux verdicts ont ainsi été contrôlés indépendamment.

Pour savoir rapidement si le carré d’un entier inconnu x peut être congru à un entier a non divisible par un nombre premier impair p, on calcule la puissance du critère. Un résultat −1 exclut toute solution ; un résultat 1 confirme l’existence d’une racine, sans la construire.

Lorsque p est grand, l’exponentiation modulaire remplace la liste de tous les carrés. On réduit après chaque multiplication, ce qui garde des nombres maniables. Si une racine explicite est demandée, il faut ensuite utiliser un algorithme d’extraction de racine modulo p.

Dans un test de primalité fondé sur le critère d’Euler, pour un module candidat impair n et une base a tels que pgcd(a, n) = 1, un résultat incompatible avec le verdict attendu du test prouve que n est composé. Un résultat compatible ne prouve pas à lui seul qu’il est premier, car certains nombres composés imitent le comportement attendu.

Le critère d’Euler ne se confond pas avec le petit théorème de Fermat. Pour un nombre premier p et un entier a non divisible par p, celui-ci donne a^p−1 ≡ 1 modulo p ; le critère d’Euler utilise le demi-exposant et distingue carrés et non-carrés. Modulo 7, l’entier a = 3 satisfait Fermat, mais sa puissance troisième vaut −1.

Il ne se confond pas non plus avec un algorithme qui calcule une racine carrée modulaire. Pour a = 2 modulo 7, le critère affirme qu’une racine existe ; le contrôle séparé montre que 3 et 4 sont des racines.

Pour un nombre premier impair p et un entier a, si p divise a, la puissance est congrue à 0, et non à 1 ou −1. Ainsi, avec a = 7 et p = 7, le calcul donne 0. Il faut traiter ce cas avant d’appliquer la branche binaire du critère.

Le module 2 est premier, mais l’exposant (p − 1)/2 n’est pas un entier positif utilisable comme dans l’énoncé. Le seul reste non nul vaut 1 et est déjà un carré ; on traite donc p = 2 séparément.

Avec un module composé, obtenir le reste attendu ne certifie pas la primalité. Les nombres composés qui passent un test dérivé sont des pseudo-premiers d’Euler ; la variante formulée avec le symbole de Jacobi conduit aux pseudo-premiers d’Euler-Jacobi. Il faut multiplier les contrôles ou employer un test de primalité plus robuste.

Le verdict −1 est une classe de congruence, pas nécessairement le reste affiché par un calcul. Modulo 7, le reste canonique 6 représente −1. Il faut comparer les valeurs modulo p avant de conclure.

Le symbole de Legendre écrit en un seul symbole le verdict du critère, y compris le cas où le nombre premier divise l’entier testé.

La congruence modulo n précise le langage des restes employé dans chaque calcul et éclaire pourquoi 6 et −1 représentent la même classe modulo 7.

Le petit théorème de Fermat replace le demi-exposant d’Euler dans une propriété plus générale des puissances modulo un nombre premier.