Applications : test de Fermat, Mersenne, RSA~1 min
Si l'on trouve un entier $a$, $1\lt a\lt n$, tel que $\boldsymbol{a^{n-1}\not\equiv1\ [n]}$, alors $n$ n'est pas premier ($a$ est un témoin de Fermat). La réciproque est fausse : $2^{340}\equiv1\ [341]$ alors que $341=11\times31$ ; le test rend la primalité probable, il ne la prouve jamais.
Nombres de Mersenne $M_n=2^n-1$ : $M_2=3$, $M_3=7$, $M_5=31$, $M_7=127$ sont premiers, mais $M_{11}=2047=23\times89$ ne l'est pas. Si $n=ab$ est composé, $2^a-1$ divise $2^n-1$ (factorisation de $x^b-1$) : $M_n$ premier $\Rightarrow$ $n$ premier, sans réciproque. Les plus grands premiers connus sont des nombres de Mersenne.
Principe du chiffrement RSA (problème possible du programme). Deux premiers $p\neq q$, $n=pq$ ; $e$ premier avec $(p-1)(q-1)$ et $d$ inverse de $e$ modulo $(p-1)(q-1)$. Clé publique $(n,e)$ : $c\equiv m^e\ [n]$. Clé privée $d$ : $m\equiv c^d\ [n]$. La correction $m^{ed}\equiv m\ [n]$ repose sur Fermat modulo $p$ et modulo $q$, puis sur Gauss ($p\wedge q=1$) ; la sécurité, sur la difficulté de factoriser $n$.