Petit théorème de Fermat et démonstration

Le petit théorème de Fermat, énoncé en 1640, par Pierre de Fermat, dispose de nombreuses applications, à la fois en arithmétique modulaire et en cryptographie.

Le petit théorème de Fermat. Si $p$ est un nombre premier et $a\in \mathbb{N}$, alors :

Démonstration

Soit $p$ un nombre premier. Pour démontrer le petit théorème de Fermat, nous allons procéder par récurrence sur $a$.

L'hypothèse de récurrence $H_a$ au rang $a\in \mathbb{N}$ est :

Initialisation

Pour $a=0$, $0^p=0$ donc $0^p\equiv 0[p]$ et $H_0$ est vraie.

Hérédité

Supposons $H_a$ vraie pour un $a\in \mathbb{N}$, et montrons que $H_{a+1}$ est vraie.

Partons de $(a+1{)}^p$ et développons :

Remarquons que pour $k\in [[1,p-1]]$, $p$ divise $\left(\genfrac{}{}{0ex}{}{p}{k}\right)$ puisque :

• $p$ divise $k!\left(\genfrac{}{}{0ex}{}{p}{k}\right)=p(p-1)...(p-k+1)$,
• $p$ est premier avec $k!$.

Grâce à cette remarque :

Par hypothèse de récurrence :

Finalement, $H_{a+1}$ est vraie.