Petit théorème de Fermat : déterminer si entier premier

Contexte

Ce chapitre traite des nombres premiers. Pour rappel, un nombre premier est un nombre possédant exactement deux diviseurs ( $1$ et lui-même).

Exemples

$2,3,5,7,11,…$ sont des nombres premiers.

$0$ et $1$ ne sont pas des nombres premiers, car $0$ possède une infinité de diviseurs et $1$ ne possède qu’un seul diviseur (lui-même).

Note : Il existe une infinité de nombres premiers.

Déterminer si un entier est premier ou non

Tout nombre entier $n$ non-premier plus grand ou égal à $2$ possède un diviseur premier compris entre $2$ et $√n$ .

En conséquence, si un nombre entier $n$ ne possède pas de diviseur premier entre $2$ et $√n$ , alors $n$ est un nombre premier.

Méthode

1.	Liste tous les nombres premiers compris entre $2$ et $√n$ .
2.	Détermine pour chacun d’eux s’il divise $n$ ou non.
3.	Si aucun ne divise $n$ , alors $n$ est premier. Sinon, $n$ n’est pas premier.

Exemple

Détermine si $73$ est premier ou non.

Comme $64<73<81$ , tu peux en déduire que $√64<√73<√81$ et donc que $8<√73<9$ .

Liste tous les nombres premiers compris entre $2$ et $8$ :

$2,3,5,7$

Avec les astuces de divisibilité habituelles, tu sais que ni $2$ , ni $3$ , ni $5$ ne divise $73$ . $7$ ne divise pas non plus $73$ comme le reste de la division de $73$ par $7$ est $3$ et non pas $0$ .

En conclusion, $73$ est un nombre premier.

Le petit théorème de Fermat

Le petit théorème de Fermat énonce que si un nombre premier $p$ ne divise pas un nombre entier $n$ , alors $p$ divise $n^{p-1}-1$ .

Une conséquence du théorème est que, pour n’importe quel nombre entier $n$ , si $p$ est un nombre premier,

alors $p$ divise $n^p-n=n(n^{p-1}-1)$

Exemple

Comme $13$ ne divise pas $17$ , alors $13$ divise $17^{13-1}-1$ . Autrement dit, le reste de la division euclidienne de $17^{12}$ par $13$ est $1$ .