fermat

petit théorème de Fermat

Théorème :
Si $p$ est un nombre premier, alors pour tout entier $a$ on a :
$a^p ≡ a (p)$
$a^{p-1} ≡ 1 (p)$
( voir congruence )

Démonstration du théorème :

• Si $a$ n'est pas premier avec $p$, comme $p$ est un nombre premier, alors $a$ est un multiple de $p$, donc $a$ et $a^{p}$ ont le même reste nul dans la division par $p$ donc $a^{p} ≡ a (p)$
  

• Supposons donc $a$ premier avec $p$, donc $a$ n'est pas un multiple de $p$.
  démontrons d'abord le résultat suivant :
  $(a+1)^p ≡ a^p+1(p)$
  la formule du binôme de newton donne :
  $(a+1)^p=\displaystyle\sum_{k=0}^p\displaystyle\binom{p}{k}a^k$
  $(a+1)^p=a^p+1+\displaystyle\sum_{k=1}^p\displaystyle\binom{p}{k}a^k$
  $\displaystyle\binom{p}{k}=\dfrac{p(p-1)\cdots (p-k+1)}{k!}$ donc $k!\displaystyle\binom{p}{k}=p(p-1)\cdots (p-k+1)$
  $p$ divise $k!\displaystyle\binom{p}{k}$ or $p$ est premier avec $k!$ donc $p$ divise $\displaystyle\binom{p}{k}$
  $p$ divise donc $(a+1)^p-a^p-1$ par conséquent :
  $(a+1)^p-a^p-1 ≡ 0 (p)$
  il en résulte $(a+1)^p ≡ a^p+1 (p)$
  
  il ne suffit plus que démontrer par récurrence que : $a^p ≡ a (p)$ en utilisant la propriété précédente.
  supposons que l'on a : $a^p ≡ a (p)$ pour un certain rang a et démontrons que l'on a alors : $(a + 1)^p ≡ a + 1 (p)$
  $(a + 1)^p ≡ a^p + 1^p (p)$ puisque $p$ est premier
  or $a^p ≡ a (p)$
  $a^p + 1≡ a + 1 (p)$ donc : $(a + 1)^p ≡ a + 1 (p)$