Test de primalité de Fermat

Ah je crois que j'ai (partiellement) répondu à mon interrogation en posant la question : si $n$ est un nombre de Carmichael, alors pour $ a, 1<a<n$ et premier avec $n$, on aurait $a^{n-1} \equiv 1 \mod n$, donc pour une grande majorité des nombres $a$ inférieurs à $n$, (faisant croire que $n$ est premier), tandis que si $n$ est composé, il y a peu de chances en choisissant $a$ au hasard qu'on ait $a^{n-1} \equiv 1 \mod n$ ?

Mais en choisissant $a$ au hasard entre $2$ et $n-1$, alors $a^{n-1} \equiv 1 \mod n$ ne prouverait quand même pas que $n$ est premier (si on savait que ce n'est pas un nombre de Carmichael) ?

Merci d'avance.

D'abord merci. Un nombre de Carmichael est composé par définition. Non il ne passe pas forcément le test de primalité de Fermat qui est :
s'il existe $a, 1<a<n$ et $a^{n-1} \not \equiv 1 \mod n$, alors $n$ est composé $(1)$.

En effet, on se met dans la situation où on ne sait rien sur $n$ et on teste un entier $a$ au hasard. On peut tomber sur un entier $a$ non premier avec $n$ (puisqu'il est composé), alors $n$ va échouer au test de Fermat car la condition $(1)$ sera réalisée.

Pour qu'un test de primalité puisse détecter à coup sûr un entier $n$ premier, il faudrait :
- soit quelque chose comme : si $\forall a, 1<a<n$, ... par exemple $a^{n-1} \equiv 1 \mod n$, alors $n$ est premier : ça ne va pas, car il faudrait tester tous les entiers $a$ et on n'en teste qu'un seul,
- soit quelque chose comme : si $\exists a, 1<a<n$, ... par exemple $a^{n-1} \equiv 1 \mod n$, alors $n$ est premier : ça va à peu près, car il faut tomber sur le bon $a$, et on n'en teste qu'un seul.

Mais avec le test de Fermat, on ne peut pas arriver avec ce genre de 2ème condition :
- le test de Fermat $(1)$ : ne va pas, il ne détecte que les composés,
- sa contraposée : si $n$ est premier , ..., ne donne rien,
- la réciproque du test de Fermat est vraie : si $n$ est composé, alors $\exists a, 1<a<n$ et $a^{n-1} \not \equiv 1 \mod n$,
- la contraposée de la réciproque est vraie : si $\forall a, 1<a<n$ et $a^{n-1} \equiv 1 \mod n$, alors $n$ est premier.
Pour les deux derniers, La Palisse n'aurait pas dit mieux : si $n$ est composé, il existe des entiers $a$ non premiers à $n$, $1<a<n$, (les diviseurs de $n$ et leurs multiples), tels que $a^{n-1} \not \equiv 1 \mod n$, et de surcroit, il faudrait tester tous les entiers $a$.
Ce n'est donc pas les nombres de Carmichael qui empêchent quoi que ce soit.

Le petit théorème de Fermat dit précisément :
si $n$ est premier, alors $\forall a$, $a$ premier avec $n, a^{n-1} \equiv 1 \mod n$.
Sa réciproque est fausse, à cause des nombres de Carmichael :
si $\forall a$, $a$ premier avec $n, a^{n-1} \equiv 1 \mod n$, alors $n$ est premier : les nombres de Carmichael vérifient l'hypothèse et ne sont pas premiers.
Mais je ne vois toujours pas, en ayant au préalable éliminé tous les nombres de Carmichael, faire en sorte que ce test, ou un test qui découle du petit théorème de Fermat, détecte un $n$ premier (d'abord il faut un : si $\exists a$, tel que ...., alors $n$ est premier, ensuite on ne sait rien sur $a$, notamment s'il est premier avec $n$ ...).

Merci de m'avoir lue.

Non, ce n'est pas ça non plus, contre-exemple : $ 6^{34} \equiv 1 \mod 35$.