Exercice 36 Le petit théorème de Fermat par la méthode d'Euler

a) Pour $a\in\{1,\dots,p-1\}$, $p$ ne divise ni $a$ ni $x$, donc ne divise pas $ax$ (lemme d'Euclide) : $r(a)\in\{1,\dots,p-1\}$. Si $r(a)=r(b)$, alors $p$ divise $ax-bx=(a-b)x$, donc $p$ divise $a-b$ ; comme $|a-b|<p$, on a $a=b$. L'application $r$ est donc injective de $\{1,\dots,p-1\}$ dans lui-même ; un ensemble fini ayant autant d'éléments au départ qu'à l'arrivée, elle est bijective.

b) En multipliant les $p-1$ congruences $ax\equiv r(a)\;[p]$ (Proposition 1), on obtient $(p-1)!\,x^{p-1}\equiv\prod_{a=1}^{p-1}r(a)\;[p]$. Comme $r$ est une bijection, le produit des $r(a)$ est celui des entiers de $1$ à $p-1$, soit $(p-1)!$. Ainsi $p$ divise $(p-1)!\left(x^{p-1}-1\right)$. Or $p$ ne divise aucun des facteurs de $(p-1)!$, donc ne divise pas $(p-1)!$, et le lemme d'Euclide donne que $p$ divise $x^{p-1}-1$ : $\boxed{x^{p-1}\equiv 1\;[p]}$.

Cette démonstration, due à Euler, n'utilise pas les coefficients binomiaux : c'est une alternative à celle du cours.