Critère de primalité de Fermat

• Condition suffisante ($\impliedby$) :
  Supposons qu'il existe un entier $a$ tel que $1 < a < n$ et $a^{n-1} \not\equiv 1 \pmod n$.
  Le Petit Théorème de Fermat énonce que si un entier $p$ est premier, alors pour tout entier $a$ non divisible par $p$, on a $a^{p-1} \equiv 1 \pmod p$.
  Par contraposée, puisque nous avons un entier $a$ strictement compris entre $1$ et $n$ (donc non multiple de $n$) qui ne vérifie pas la congruence de Fermat, l'entier $n$ ne peut pas être premier. Il est donc composé.


• Condition nécessaire ($\implies$) :
  Supposons que $n$ est un entier composé. Montrons qu'il existe au moins un témoin de Fermat.
  Puisque $n$ est composé, il admet au moins un diviseur strict $d$ tel que $1 < d < n$.
  Posons $a = d$. Montrons par l'absurde que $a^{n-1} \not\equiv 1 \pmod n$.
  Si nous supposions le contraire, c'est-à-dire $a^{n-1} \equiv 1 \pmod n$, il existerait un entier $k$ tel que : \[ a^{n-1} = 1 + kn \iff a \cdot a^{n-2} - kn = 1 \] D'après le théorème de Bachet-Bézout, cette identité de la forme $au + nv = 1$ impliquerait que $a$ et $n$ sont premiers entre eux, soit $\text{pgcd}(a, n) = 1$.
  Or, par construction, $a$ est un diviseur de $n$. Donc $\text{pgcd}(a, n) = a > 1$.
  C'est une contradiction. Par conséquent, l'hypothèse est fausse et on a bien $a^{n-1} \not\equiv 1 \pmod n$. Le diviseur $d$ constitue un témoin de Fermat parfait.