Exercice : Petit théorème de Fermat et tests de primalité

Étape 1

Le nombre $13$ est un nombre premier et ne divise pas $2$. D'après le petit théorème de Fermat, on a : $$2^{13-1} \equiv 1 \pmod{13} \quad \text{soit} \quad 2^{12} \equiv 1 \pmod{13}$$

Étape 2

Comme $120 = 12 \times 10$, on applique les propriétés des congruences : $$2^{120} = (2^{12})^{10} \equiv 1^{10} \equiv 1 \pmod{13}$$

Étape 3

On en déduit la simplification suivante : $$2^{120+k} = 2^{120} \times 2^k \equiv 1 \times 2^k \equiv 2^k \pmod{13}$$ L'égalité $2^{120+k} \equiv 5 \pmod{13}$ équivaut donc à trouver un entier $k$ compris entre $1$ et $11$ tel que $2^k \equiv 5 \pmod{13}$.

Étape 4

Calculons les puissances successives de $2$ modulo $13$ :

Étape 5

$2^1 \equiv 2 \pmod{13}$

Étape 6

$2^2 \equiv 4 \pmod{13}$

Étape 7

$2^3 \equiv 8 \pmod{13}$

Étape 8

$2^4 = 16 \equiv 3 \pmod{13}$

Étape 9

$2^5 = 2 \times 3 \equiv 6 \pmod{13}$

Étape 10

$2^6 = 2 \times 6 = 12 \equiv 12 \pmod{13}$

Étape 11

$2^7 = 2 \times 12 = 24 \equiv 11 \pmod{13}$

Étape 12

$2^8 = 2 \times 11 = 22 \equiv 9 \pmod{13}$

Étape 13

$2^9 = 2 \times 9 = 18 \equiv 5 \pmod{13}$

Étape 14

On obtient bien $2^9 \equiv 5 \pmod{13}$. La valeur de l'entier $k$ est donc $9$.