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

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$$​ .