Exercice 24 Nombres de Carmichaël

1. (a) On divise successivement par les premiers : $561=3\times 187$, puis $187=11\times 17$. $$\boxed{561=3\times 11\times 17}$$ En particulier, $\boxed{561 \text{ n'est pas premier.}}$

(b) Ici $n-1=560$, et l'on teste chaque facteur premier : $$3-1=2 \text{ et } 560=2\times 280 \qquad\qquad 11-1=10 \text{ et } 560=10\times 56$$

(c) Soit $a$ un entier premier avec $561$, c'est-à-dire n'ayant aucun diviseur commun avec $561$ autre que $\pm 1$. Comme $561=3\times 11\times 17$, cela signifie qu'aucun des nombres premiers $3$, $11$ et $17$ ne divise $a$. Le petit théorème de Fermat donne donc : $$a^{2}\equiv 1\;[3] \qquad a^{10}\equiv 1\;[11] \qquad a^{16}\equiv 1\;[17]$$ On élève alors chaque congruence à la puissance voulue, en utilisant les quotients de la question précédente : $$a^{560}=\left(a^{2}\right)^{280}\equiv 1\;[3] \qquad a^{560}=\left(a^{10}\right)^{56}\equiv 1\;[11] \qquad a^{560}=\left(a^{16}\right)^{35}\equiv 1\;[17]$$ Ainsi $a^{560}-1$ est divisible par $3$, par $11$ et par $17$. Ces trois nombres premiers étant distincts, leur produit divise $a^{560}-1$ (lemme d'Euclide, comme à l'exercice 11) : $$\boxed{a^{560}\equiv 1\;[561]}$$ En multipliant par $a$, il vient $a^{561}\equiv a\;[561]$, c'est-à-dire que $561$ divise $a^{561}-a$. Comme $561$ n'est pas premier : $$\boxed{561 \text{ est un nombre de Carmichaël.}}$$

2. On reprend le même raisonnement.

(a) $1\,105=5\times 221=5\times 13\times 17$, donc $\boxed{1\,105=5\times 13\times 17 \text{ n'est pas premier.}}$

(b) $n-1=1\,104$, et : $$5-1=4 \text{ et } 1\,104=4\times 276 \qquad\qquad 13-1=12 \text{ et } 1\,104=12\times 92$$

(c) Soit $a$ premier avec $1\,105$, c'est-à-dire non divisible par $5$, $13$ et $17$. Par le petit théorème de Fermat appliqué à $5$, $13$ et $17$ : $$a^{1104}=\left(a^{4}\right)^{276}\equiv 1\;[5] \qquad a^{1104}=\left(a^{12}\right)^{92}\equiv 1\;[13] \qquad a^{1104}=\left(a^{16}\right)^{69}\equiv 1\;[17]$$ Les trois facteurs premiers étant distincts : $$\boxed{a^{1104}\equiv 1\;[1\,105],\ \text{donc } 1\,105 \text{ est un nombre de Carmichaël.}}$$

3. Le petit théorème de Fermat affirme que si $n$ est premier et $a$ premier avec $n$, alors $a^{\,n-1}\equiv 1\;[n]$. La réciproque serait : « si $a^{\,n-1}\equiv 1\;[n]$ pour tout $a$ premier avec $n$, alors $n$ est premier. »

Les nombres $561$ et $1\,105$ vérifient l'hypothèse de cette réciproque pour tout $a$ premier avec eux, et ne sont pourtant pas premiers. $$\boxed{\text{La réciproque du petit théorème de Fermat est fausse.}}$$

Comparaison avec l'exercice 23. Un nombre de Poulet, comme $341$, met le test en défaut pour la seule base $a=2$ : il suffirait d'essayer $a=3$ pour le démasquer, car $3^{340}\not\equiv 1\;[341]$. Un nombre de Carmichaël est bien plus retors : aucune base première avec lui ne permet de le détecter. C'est pourquoi les tests de primalité modernes ne se contentent pas de la congruence de Fermat.