Exercice 50

Si $n$ n'est pas premier, il s'écrit $n = ab$ avec $1 < a < n$. Alors $a$ figure dans le produit $(n - 1)!$, donc $a \mid (n - 1)!$. Si l'on avait $(n - 1)! \equiv -1 \;[n]$, l'entier $a$, qui divise $n$, diviserait $(n - 1)! + 1$, donc $1$ : c'est absurde.

Si $n = p$ est premier. Pour $p = 2$ et $p = 3$, on a $1! = 1 \equiv -1 \;[2]$ et $2! = 2 \equiv -1 \;[3]$. Soit $p \geqslant 5$. D'après la proposition 12, chaque $k \in [\![1\,;p - 1]\!]$ admet un inverse modulo $p$, et un seul dans $[\![1\,;p - 1]\!]$, que l'on note $k'$. On a $k' = k$ si et seulement si $k^{2} \equiv 1$, c'est-à-dire $p \mid (k - 1)(k + 1)$, soit $k \in \{1, p - 1\}$ par le lemme d'Euclide. Les entiers de $[\![2\,;p - 2]\!]$ se regroupent donc en paires $\{k, k'\}$ de produit congru à $1$, et $$(p - 1)! = 1 \times \Big(\prod_{k = 2}^{p - 2} k\Big) \times (p - 1) \equiv 1 \times 1 \times (-1) \;[p].$$

$$\boxed{n \text{ premier} \iff (n - 1)! \equiv -1 \;[n]}$$ Pour $p = 7$, les paires sont $\{2, 4\}$ et $\{3, 5\}$, et $6! = 720 = 7 \times 103 - 1$. ✓

À retenir. Ce critère de primalité est exact mais inutilisable en pratique : calculer $(n - 1)!$ modulo $n$ demande $n - 2$ multiplications, bien plus que les essais de divisions jusqu'à $\sqrt{n}$.