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

Étape 1

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

Étape 2

On effectue la division euclidienne de l'exposant $38$ par $12$ : $$38 = 12 \times 3 + 2$$

Étape 3

En appliquant les propriétés des congruences : $$2^{38} = (2^{12})^3 \times 2^2 \equiv 1^3 \times 4 \pmod{13}$$ d'où : $$2^{38} \equiv 4 \pmod{13}$$

Étape 4

L'entier $A = 2^{38} + k$ est donc congru modulo $13$ à : $$A \equiv 4 + k \pmod{13}$$

Étape 5

Par conséquent, $13$ divise $A$ si et seulement si $4 + k \equiv 0 \pmod{13}$, ce qui équivaut à $k \equiv -4 \pmod{13}$, c'est-à-dire $k \equiv 9 \pmod{13}$. Comme $k$ appartient à l'ensemble $\{0, 1, \dots, 12\}$, l'unique valeur possible est $k = 9$.