1

Un entier naturel $\mathbf{n}$ est premier lorsqu’il possède exactement deux diviseurs positifs : $1$ et lui‑même.
Pour savoir si $\mathbf{n}$ est premier, il suffit de tester s’il est divisible par des entiers compris entre $2$ et $\sqrt{\mathbf{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 $\mathbf{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 à $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{P}\mathrm{G}\mathrm{C}\mathrm{D}$ de deux entiers.

4

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

✔ calculer des puissances modulo $p$ en simplifiant les calculs.