Petit théorème de Fermat et tests de primalité
L'essentiel du cours (2 notions)
Petit théorème de Fermat
Propriété : Soit $p$ un nombre premier. Si $p \nmid a$, alors $a^{p-1} \equiv 1 \; [p]$. Pour tout entier $a$, $a^p \equiv a \; [p]$.
Méthode : Pour simplifier $a^n \; [p]$ ($p \nmid a$), effectuer la division euclidienne $n = (p-1)q + r$. Alors $a^n \equiv a^r \; [p]$.
Exemple : Modulo $13$ premier : $100 = 12 \times 8 + 4 \implies 2^{100} \equiv 2^4 \equiv 3 \; [13]$.
Témoins et nombres de Carmichael
Définition : Si $a^{n-1} \not\equiv 1 \; [n]$, $a$ est un témoin de Fermat ($n$ est composé). Un composé $n$ n'ayant aucun témoin premier avec lui est un nombre de Carmichael.
Propriété : Un seul témoin $a$ prouve que $n$ est composé. L'absence de témoin pour certains $a$ ne garantit pas la primalité.
Exemple : Pour $n = 561 = 3 \times 11 \times 17$ (composé), $a^{560} \equiv 1 \; [561]$ pour tout $a$ premier avec $561$.
On cherche à déterminer un entier naturel $k$ compris entre $1$ et $11$ vérifiant la relation suivante :
$$2^{120+k} \equiv 5 \pmod{13}$$Pour déterminer cet entier $k$, suivre la méthode suivante :
- En utilisant le petit théorème de Fermat, justifier que $2^{120} \equiv 1 \pmod{13}$.
- En déduire que $2^{120+k} \equiv 2^k \pmod{13}$.
- En calculant les puissances successives de $2$ modulo $13$, déterminer la valeur de l'entier $k$.
Saisir la valeur de k.
On considère l'entier $A = 2^{38} + k$, où $k$ est un entier vérifiant $0 \leqslant k \leqslant 12$.
En appliquant le petit théorème de Fermat avec le nombre premier $13$, déterminer la valeur de $k$ pour laquelle l'entier $A$ est divisible par $13$.
Saisir la valeur de l'entier $k$.
Soit $n$ un entier naturel tel que $1 \le n \le 9$.
On sait que le reste de la division euclidienne de $7^{2027 + n}$ par $11$ est égal à $2$.
Saisir la valeur de l'entier $n$.
On considère un entier naturel non nul $N$.
On sait que le reste de la division euclidienne de $N$ par $18$ est égal à $5$, et que l'entier $7^N + N$ est divisible par $19$.
Déterminer le plus petit entier naturel non nul $N$ vérifiant ces conditions.