Fermat premier par premier : $42\mid n^7-n$

La stratégie. Le petit théorème de Fermat travaille modulo chaque nombre premier séparément ; la proposition « si $a$ et $b$ sont premiers entre eux et divisent $n$, alors $ab$ divise $n$ » recolle les morceaux — à condition que les modules soient premiers entre eux deux à deux.

Un lemme. Soit $p$ premier et $k\ge 1$ tel que $p-1$ divise $k-1$. Alors $n^k\equiv n[p]$ pour tout entier $n$. En effet, écrivons $k-1=(p-1)j$. Si $p\mid n$, les deux membres sont congrus à $0$. Sinon, par le petit théorème de Fermat, $n^{p-1}\equiv 1[p]$, donc $n^k=n\cdot {\left(n^{p-1}\right)}^j\equiv n\cdot 1=n[p]$.

a) Le cas de $42$. Pour $k=7$, $k-1=6$ est divisible par $p-1$ pour $p=2$ ($1\mid 6$), $p=3$ ($2\mid 6$) et $p=7$ ($6\mid 6$). Le lemme donne $n^7\equiv n$ modulo $2$, modulo $3$ et modulo $7$ : chacun de ces trois premiers divise $n^7-n$. Recollons : $2$ et $3$ sont premiers entre eux et divisent $n^7-n$, donc $6$ le divise ; $6$ et $7$ sont premiers entre eux et le divisent, donc $42$ le divise. $42\mid n^7-n$ pour tout $n$.

b) Le cas de $2730$. Pour $k=13$, $k-1=12$, dont les diviseurs sont $1,2,3,4,6,12$ ; les premiers $p$ tels que $p-1$ soit l'un d'eux sont $p=2,3,5,7,13$ — et $4+1=5$, $6+1=7$, $12+1=13$ sont bien premiers, tandis que $3+1=4$ ne l'est pas. Par le lemme, chacun de $2,3,5,7,13$ divise $n^{13}-n$ ; ils sont premiers entre eux deux à deux (premiers distincts), et le recollement, appliqué quatre fois, donne $2730\mid n^{13}-n$. Le nombre $2730$ est exactement le produit des premiers $p$ tels que $p-1\mid 12$ ; de même $42$ est le produit des premiers $p$ tels que $p-1\mid 6$, à savoir $2$, $3$, $7$. (Un premier qui ne vérifie pas cette condition ne divise pas $n^k-n$ pour tout $n$ ; par exemple $11\nmid 2^{13}-2=8190=11\times 744+6$.)

c) Deux à deux, ou dans leur ensemble. $6\wedge 10=2$, $6\wedge 15=3$, $10\wedge 15=5$ : aucun couple n'est premier entre eux. Mais $6\wedge 10\wedge 15=(6\wedge 10)\wedge 15=2\wedge 15=1$ : ils sont premiers entre eux dans leur ensemble. Chacun divise $30$, et pourtant $6\times 10\times 15=900$ ne divise pas $30$.

Pourquoi. Le recollement du a) enchaîne « $a\mid N$, $b\mid N$, $a\wedge b=1$ donc $ab\mid N$ », puis « $ab\mid N$, $c\mid N$, $ab\wedge c=1$ donc $abc\mid N$ » : à chaque étape il faut que le produit déjà formé soit premier avec le module suivant, ce qui est garanti si les modules sont premiers entre eux deux à deux (le cours : $a\wedge c=1$ et $b\wedge c=1$ entraînent $ab\wedge c=1$). Avec $6,10,15$, la première étape échoue déjà : $6\wedge 10=2\ne 1$, et de fait $60\nmid 30$. En termes de valuations : ce qui divise $N$, c'est le PPCM des modules, dont la valuation en $p$ est le maximum des valuations ; le PPCM égale le produit si et seulement si aucun premier n'apparaît dans deux modules — c'est-à-dire si et seulement si les modules sont premiers entre eux deux à deux.

Ce que l'exercice installe. Fermat ne parle que d'un nombre premier à la fois ; pour un module composé, on factorise, on travaille premier par premier, on recolle — et le recollement a une condition précise, « deux à deux », qu'il faut vérifier et non supposer. C'est le principe qui justifie le chiffrement RSA : Fermat modulo $p$, Fermat modulo $q$, recollement modulo $pq$.