Nombres premiers

À retenir. Un entier $n\geq2$ est premier s'il n'admet que deux diviseurs positifs : $1$ et $n$. $2$ est le seul premier pair. Un entier $n>1$ non premier admet un diviseur premier $\leq\sqrt{n}$. Il existe une infinité de nombres premiers (Euclide).

À retenir. Tout entier $n\geq2$ s'écrit de façon unique comme produit de nombres premiers. Si $n=p_1^{a_1}\cdots p_k^{a_k}$, il possède $(a_1+1)\cdots(a_k+1)$ diviseurs positifs. Le PGCD s'obtient avec les plus petits exposants, le PPCM avec les plus grands.

À retenir. Si $p$ est premier et $a$ n'est pas multiple de $p$ : $a^{p-1}\equiv1\;[p]$. Pour tout entier $a$ : $a^p\equiv a\;[p]$. On l'utilise pour réduire un exposant modulo $p-1$.