Petit théorème de Fermat : exercices corrigés (Terminale expertes)

Le nombre $11$ est premier et $11$ ne divise pas $2$. Le petit théorème de Fermat donne $2^{10} \equiv 1 \pmod{11}$.

On remarque que $50 = 10 \times 5$.

Donc $2^{50} = (2^{10})^5 \equiv 1^5 = 1 \pmod{11}$.

Le reste cherché est $1$.

Le nombre $7$ est premier et ne divise pas $4$. Donc $4^6 \equiv 1 \pmod 7$.

Division euclidienne : $100 = 6 \times 16 + 4$.

On en déduit $4^{100} = (4^6)^{16} \times 4^4 \equiv 4^4 \pmod 7$.

On calcule $4^2 = 16 \equiv 2$, puis $4^4 \equiv 2^2 = 4 \pmod 7$.

Le reste cherché est $4$.

Le nombre $7$ est premier et ne divise ni $2$ ni $3$. Donc $2^6 \equiv 1$ et $3^6 \equiv 1 \pmod 7$.

Comme $100 = 6 \times 16 + 4$, on a $2^{100} \equiv 2^4$ et $3^{100} \equiv 3^4 \pmod 7$.

On calcule $2^4 = 16 = 2 \times 7 + 2$, donc $2^4 \equiv 2$.

On calcule $3^4 = 81 = 11 \times 7 + 4$, donc $3^4 \equiv 4$.

Alors $2^{100} + 3^{100} \equiv 2 + 4 = 6 \pmod 7$.

Le reste cherché est $6$.

Le nombre $13$ est premier et ne divise pas $3$. Donc $3^{12} \equiv 1 \pmod{13}$.

Division euclidienne : $2026 = 12 \times 168 + 10$, car $12 \times 168 = 2016$.

Donc $3^{2026} \equiv 3^{10} \pmod{13}$.

On remarque que $3^3 = 27 = 2 \times 13 + 1$, donc $3^3 \equiv 1$.

Alors $3^{10} = (3^3)^3 \times 3 \equiv 3 \pmod{13}$.

Le reste cherché est $3$.

Le nombre $17$ est premier et ne divise pas $5$. Donc $5^{16} \equiv 1 \pmod{17}$.

On écrit $5^{16} = 5 \times 5^{15}$. Ainsi $5^{15}$ est un inverse de $5$ modulo $17$.

On calcule : $5^2 = 25 \equiv 8$, puis $5^4 \equiv 64 \equiv 13$ (car $64 - 51 = 13$), puis $5^8 \equiv 169 \equiv 16$ (car $169 - 153 = 16$).

Comme $15 = 8 + 4 + 2 + 1$, on a $5^{15} \equiv 16 \times 13 \times 8 \times 5 \pmod{17}$.

On remplace $16$ par $-1$ : $5^{15} \equiv -13 \times 8 \times 5 = -520$. Or $520 = 17 \times 30 + 10$, donc $5^{15} \equiv -10 \equiv 7$.

Vérification : $5 \times 7 = 35 = 2 \times 17 + 1$, donc $5 \times 7 \equiv 1 \pmod{17}$.

On a $u = 7$.

Le nombre $11$ est premier et ne divise pas $6$. Donc $6^{10} \equiv 1 \pmod{11}$ et $6^9$ est un inverse de $6$.

On calcule : $6^2 = 36 \equiv 3$, $6^4 \equiv 9$, $6^8 \equiv 81 \equiv 4$ (car $81 - 77 = 4$), puis $6^9 \equiv 4 \times 6 = 24 \equiv 2$.

Contrôle : $6 \times 2 = 12 \equiv 1 \pmod{11}$, donc $2$ est bien l'inverse de $6$.

On multiplie $6x \equiv 5$ par $2$ : $12x \equiv 10$, soit $x \equiv 10 \pmod{11}$.

Vérification : $6 \times 10 = 60 = 5 \times 11 + 5$, donc $6 \times 10 \equiv 5$.

L'ensemble des solutions est $x = 10 + 11k$ avec $k \in \mathbb{Z}$, et la solution entre $0$ et $10$ est $10$.

Question 1. On a $2^{10} = 1024 = 3 \times 341 + 1$, donc $2^{10} \equiv 1 \pmod{341}$. Alors $2^{340} = (2^{10})^{34} \equiv 1 \pmod{341}$.

Cette égalité ne prouve pas que $341$ est premier : on sait que $341 = 11 \times 31$ est composé, et pourtant la condition est vérifiée pour $a = 2$. La condition de Fermat est nécessaire, pas suffisante.

Question 2, modulo $11$. Le nombre $11$ est premier et ne divise pas $3$, donc $3^{10} \equiv 1$. Comme $340 = 10 \times 34$, on a $3^{340} \equiv 1 \pmod{11}$.

Modulo $31$. Le nombre $31$ est premier, donc $3^{30} \equiv 1$. On écrit $340 = 30 \times 11 + 10$, donc $3^{340} \equiv 3^{10} \pmod{31}$.

On calcule : $3^3 = 27 \equiv -4$, puis $3^9 \equiv (-4)^3 = -64 \equiv -2$ (car $-64 + 62 = -2$), puis $3^{10} \equiv -6 \equiv 25 \pmod{31}$. Ainsi $3^{340} \equiv 25 \pmod{31}$.

Question 3. On cherche $x$ tel que $x \equiv 1 \pmod{11}$ et $x \equiv 25 \pmod{31}$. On pose $x = 25 + 31k$. Comme $25 \equiv 3$ et $31 \equiv 9 \pmod{11}$, la condition devient $3 + 9k \equiv 1$, soit $9k \equiv 9$, donc $k \equiv 1 \pmod{11}$. Pour $k = 1$, on obtient $x = 56$.

Vérification : $56 = 5 \times 11 + 1$ et $56 = 31 + 25$. Comme $11$ et $31$ sont premiers entre eux, le reste de $3^{340}$ modulo $341$ est $56$.

Ce reste n'est pas $1$. Or si $341$ était premier, on devrait avoir $a^{340} \equiv 1 \pmod{341}$ pour tout $a$ plus petit que $341$ ³. Donc $341$ n'est pas premier.

Question 1, premier cas : si $p$ divise $n$, alors $p$ divise $n^{13}$ et $n$, donc $p$ divise $n^{13} - n$.

Second cas : si $p$ ne divise pas $n$, le théorème de Fermat donne $n^{p-1} \equiv 1 \pmod p$. Comme $p-1$ divise $12$, on écrit $12 = (p-1)m$, donc $n^{12} = (n^{p-1})^m \equiv 1 \pmod p$. En multipliant par $n$, on obtient $n^{13} \equiv n \pmod p$.

Question 2. On ajoute $1$ aux diviseurs de $12$ : $2, 3, 4, 5, 7, 13$. Les nombres premiers sont $2, 3, 5, 7$ et $13$ ($4$ n'est pas premier).

Question 3. Ces cinq nombres premiers sont distincts, donc leur produit $2 \times 3 \times 5 \times 7 \times 13 = 2730$ divise $n^{13} - n$ (un entier divisible par plusieurs nombres premiers distincts l'est par leur produit).

Pour $n = 2$ : $2^{13} - 2 = 8192 - 2 = 8190 = 3 \times 2730$.

Pour $n = 3$ : $3^{13} - 3 = 1\,594\,323 - 3 = 1\,594\,320 = 584 \times 2730$.

Tout entier $d$ qui convient divise $8190$ et $1\,594\,320$, donc divise leur PGCD. Comme $\operatorname{PGCD}(3, 584) = 1$ (car $584$ n'est pas multiple de $3$), ce PGCD vaut $2730$.

Le plus grand entier cherché est donc $d = 2730$.