Théorème 1Réciprocité quadratique

Théorèmes de Fermat et d'Euler

Pour $n \geqslant 1$ et $a, b \in {\mathbb Z}$ , on écrit $a \equiv b \pmod n$ , et l'on dit que $a$ est congru à $b$ modulo $n$ , lorsque $n$ divise $a - b$ , c'est-à-dire lorsque $a$ et $b$ ont la même classe dans ${\mathbb Z/n\mathbb Z}$ . Les congruences modulo $n$ s'additionnent et se multiplient, puisque la projection de $\mathbb Z$ sur $\mathbb Z/n\mathbb Z$ est un morphisme d'anneaux (Anneau quotient).

Comme au nœud Produits semi-directs, $(\mathbb Z/n\mathbb Z)^\times$ est le groupe des éléments inversibles de l'anneau $\mathbb Z/n\mathbb Z$ , et $\varphi(n)$ désigne, comme au nœud Groupes cycliques, le nombre d'entiers $k \in \{1, \dots, n\}$ premiers à $n$ .

Énoncé

(i) La classe $\bar a$ est inversible dans $\mathbb Z/n\mathbb Z$ si et seulement si $a \wedge n = 1$ . Le groupe $(\mathbb Z/n\mathbb Z)^\times$ a donc $\varphi(n)$ éléments.

(ii) Euler. Si $a \wedge n = 1$ , alors $a^{\varphi(n)} \equiv 1 \pmod n$ .

(iii) Fermat. Si $p$ est un nombre premier, alors $a^p \equiv a \pmod p$ pour tout $a \in \mathbb Z$ , et $a^{p-1} \equiv 1 \pmod p$ si $p$ ne divise pas $a$ .

Démonstration

(i) Si $\bar a\bar u = \bar 1$ , il existe $v \in \mathbb Z$ tel que $au - 1 = nv$ , d'où $au + n(-v) = 1$ , et $a \wedge n = 1$ par le théorème de Bézout (PGCD, Bézout, (ii)). Réciproquement, une relation $au + nv = 1$ donne $\bar a\bar u = \bar 1$ .

La condition $a \wedge n = 1$ ne dépend que de la classe de $a$ , puisque l'idéal $(a + kn)\mathbb Z + n\mathbb Z$ est égal à $a\mathbb Z + n\mathbb Z$ pour tout $k \in \mathbb Z$ .

Comme $\bar n = \bar 0$ , les classes $\bar 1, \dots, \bar n$ sont, à l'ordre près, les $n$ éléments $\bar 0, \dots, \overline{n - 1}$ de $\mathbb Z/n\mathbb Z$ , deux à deux distincts (ℤ/nℤ). Les inversibles sont donc les classes des entiers $k \in \{1, \dots, n\}$ premiers à $n$ , au nombre de $\varphi(n)$ .

(ii) Dans un groupe fini $G$ , tout élément $x$ vérifie $x^{|G|} = e$ (Groupes cycliques, (i)). Pour $G = (\mathbb Z/n\mathbb Z)^\times$ , d'ordre $\varphi(n)$ par (i), et $x = \bar a$ , c'est l'égalité $\bar a^{\varphi(n)} = \bar 1$ .

(iii) Les seuls diviseurs positifs de $p$ étant $1$ et $p$ , les entiers de $\{1, \dots, p\}$ premiers à $p$ sont $1, \dots, p - 1$ , et $\varphi(p) = p - 1$ . Si $p$ ne divise pas $a$ , le pgcd $a \wedge p$ , diviseur positif de $p$ différent de $p$ , vaut $1$ , et (ii) donne $a^{p-1} \equiv 1$ ; en multipliant par $a$ , $a^p \equiv a$ . Si $p$ divise $a$ , les deux membres de $a^p \equiv a$ sont congrus à $0$ .

□

Remarque

L'exposant $\varphi(n)$ est un multiple de l'ordre de $\bar a$ , pas toujours cet ordre. Modulo $11$ , on a $2^{10} = 1024 = 93 \cdot 11 + 1$ , et $2$ est d'ordre exactement $10$ ; modulo $12$ , où $\varphi(12) = 4$ , on a déjà $5^2 = 25 = 2 \cdot 12 + 1$ .

Remarque

L'erreur la plus répandue est de lire le théorème de Fermat comme un critère de primalité. La réciproque est fausse : $341 = 11 \cdot 31$ n'est pas premier, et pourtant $2^{340} \equiv 1 \pmod{341}$ .

Il y a pire : pour $561 = 3 \cdot 11 \cdot 17$ , la congruence $a^{560} \equiv 1 \pmod{561}$ vaut pour tout $a$ premier à $561$ . Le théorème de Wilson, lui, caractérise exactement les nombres premiers par une congruence, comme l'établira le nœud voisin (Wilson, (ii)), mais il est inutilisable en pratique.

Remarque

La preuve passe par le théorème de Lagrange. On peut aussi démontrer $a^p \equiv a$ par récurrence sur $a \geqslant 0$ , à partir de $(a + 1)^p \equiv a^p + 1 \pmod p$ , que donne le binôme de Newton en caractéristique $p$ (Binôme de Newton, (iv)) ; le cas $a < 0$ s'en déduit, puisque $a^p \equiv (a + kp)^p$ .

Remarque

Fermat énonce le théorème, sans démonstration, dans une lettre à Frénicle de Bessy du 18 octobre 1640 ; Euler en rédige en 1736 la première démonstration, publiée en 1741, et l'étend plus tard aux modules quelconques par la fonction $\varphi$ qui porte son nom.

Repose sur

Entiers de Gauss et théorème des deux carrés

Sert à

Résidus quadratiques, critère d'Euler