1

Un entier naturel \boldsymbol{n} est premier lorsqu'il possède exactement deux diviseurs positifs : \boldsymbol{1} et lui‑même.
Pour savoir si \boldsymbol{n} est premier, il suffit de tester s'il est divisible par des entiers compris entre \boldsymbol{2} et \boldsymbol{\sqrt{n}}. Cela permet de :

✔ déterminer si l'entier n est un nombre premier ou non ;
✔ trouver un diviseur de n afin de déterminer ensuite une factorisation de l'entier n.

2

Le crible d'Eratosthène permet de connaître l'ensemble des nombres premiers inférieurs ou égaux à un entier \boldsymbol{n}.
Cela permet de :

✔ savoir facilement si un nombre inférieur ou égal à n est premier ou non ;
✔ savoir quels sont les diviseurs premiers potentiels d'un nombre n et faciliter ainsi les tests de primalité.

3

Tout entier naturel supérieur ou égal à \boldsymbol{2} se décompose de façon unique en produit de nombres premiers.
Cela permet de :

✔ déterminer l'ensemble des diviseurs d'un entier, en les énumérant à l'aide d'un arbre ;
✔ déterminer le nombre de diviseurs, en regardant uniquement les exposants apparaissant dans la décomposition ;
✔ déterminer le \mathrm{PGCD} de deux entiers.

4

Le petit théorème de Fermat : si \boldsymbol{p} est un nombre premier et si \boldsymbol{a} est un entier non divisible par \boldsymbol{p}, alors \boldsymbol{a^{p-1} \equiv 1[p]}.
Cela permet de :

✔ calculer des puissances modulo p en simplifiant les calculs.