Exercices — PGCD, théorèmes de Bézout et de Gauss, nombres premiers

1. On enchaîne les divisions euclidiennes, chaque diviseur devenant le nouveau dividende :

$322 = 70 \times 4 + 42 \qquad 70 = 42 \times 1 + 28 \qquad 42 = 28 \times 1 + 14 \qquad 28 = 14 \times 2 + 0$

Le dernier reste non nul est $14$ : $\operatorname{pgcd}(322\,;\,70) = 14$.

2. On divise numérateur et dénominateur par le PGCD : $322 = 14 \times 23$ et $70 = 14 \times 5$, donc :

$\frac{322}{70} = \frac{23}{5}$

Cette fraction est irréductible : $23$ et $5$ sont premiers entre eux (leur PGCD vaut $1$, ce sont d’ailleurs deux nombres premiers distincts).

3. Non : leur PGCD vaut $14 \neq 1$. « Premiers entre eux » signifie exactement « PGCD égal à $1$ ».

Réflexe à retenir : dans l’algorithme d’Euclide, le PGCD est le dernier reste non nul — pas le dernier quotient, ni le dernier reste (qui vaut $0$). Et diviser par le PGCD rend toujours une fraction irréductible.

1. $51 = 22 \times 2 + 7$, puis $22 = 7 \times 3 + 1$, puis $7 = 1 \times 7 + 0$. Le dernier reste non nul est $1$ : $\operatorname{pgcd}(51\,;\,22) = 1$, les nombres sont premiers entre eux.

2. On isole les restes en partant de l’avant-dernière ligne :

$1 = 22 - 7 \times 3 \qquad \text{et} \qquad 7 = 51 - 22 \times 2$

d’où, en remplaçant $7$ :

$1 = 22 - 3 \times (51 - 2 \times 22) = 7 \times 22 - 3 \times 51$

Le couple $(u\,;\,v) = (-3\,;\,7)$ convient. Vérification : $51 \times (-3) + 22 \times 7 = -153 + 154 = 1$ ✓.

3. L’égalité $7 \times 22 = 1 + 3 \times 51$ se traduit par $22 \times 7 \equiv 1 \pmod{51}$ : le nombre $7$ est un inverse de $22$ modulo $51$. On multiplie alors les deux membres de la congruence par $7$ :

$22x \equiv 3 \pmod{51} \iff 7 \times 22x \equiv 21 \pmod{51} \iff x \equiv 21 \pmod{51}$

Les solutions sont les entiers $x = 21 + 51k$, $k \in \mathbb{Z}$. Vérification : $22 \times 21 = 462 = 9 \times 51 + 3 \equiv 3 \pmod{51}$ ✓.

Réflexe à retenir : la remontée de Bézout se fait en isolant les restes ligne par ligne, de bas en haut — et un couple de Bézout pour $(a\,;\,n)$ premiers entre eux te donne gratuitement l’inverse de $a$ modulo $n$ : c’est l’arme qui transforme $ax \equiv b$ en $x \equiv ub$.

1. $\operatorname{pgcd}(5\,;\,7) = 1$ (deux nombres premiers distincts), et $1$ divise $4$ : l’équation admet donc des solutions entières.

2. $5 \times 3 + 7 \times (-2) = 15 - 14 = 1$ ✓. En multipliant les deux membres par $4$ :

$5 \times 12 + 7 \times (-8) = 4$

donc $(x_0\,;\,y_0) = (12\,;\,-8)$ est une solution particulière de $(E)$.

3. Si $5x + 7y = 4$, on soustrait l’égalité $5 \times 12 + 7 \times (-8) = 4$ :

$5(x - 12) + 7(y + 8) = 0 \qquad \text{c'est-à-dire} \qquad 5(x - 12) = -7(y + 8)$

Ainsi $7$ divise $5(x - 12)$. Comme $7$ est premier avec $5$, le théorème de Gauss donne : $7$ divise $x - 12$.

4. D’après la question 3, $x = 12 + 7k$ avec $k \in \mathbb{Z}$. En reportant dans $5(x - 12) = -7(y + 8)$ : $5 \times 7k = -7(y + 8)$, d’où $y + 8 = -5k$, c’est-à-dire $y = -8 - 5k$. Réciproquement, pour tout $k \in \mathbb{Z}$ :

$5(12 + 7k) + 7(-8 - 5k) = 60 + 35k - 56 - 35k = 4$

donc tous ces couples sont bien solutions. Conclusion :

$\mathcal{S} = \left\{(12 + 7k\,;\,-8 - 5k),\ k \in \mathbb{Z}\right\}$

Réflexe à retenir : le plan Bézout → solution particulière → soustraction → Gauss → réciproque se déroule à l’identique dans toutes les équations $ax + by = c$. Ne saute jamais la réciproque : c’est elle qui garantit qu’on a exactement les solutions, ni plus ni moins.

1. On divise par les premiers successifs :

$360 = 2 \times 180 = 2^2 \times 90 = 2^3 \times 45 = 2^3 \times 3^2 \times 5 \qquad \text{et} \qquad 84 = 2^2 \times 21 = 2^2 \times 3 \times 7$

2. Le PGCD s’obtient en gardant les facteurs premiers communs, chacun avec le plus petit exposant : facteurs communs $2$ (exposants $3$ et $2$) et $3$ (exposants $2$ et $1$) :

$\operatorname{pgcd}(360\,;\,84) = 2^2 \times 3 = 12$

Par Euclide : $360 = 84 \times 4 + 24$, puis $84 = 24 \times 3 + 12$, puis $24 = 12 \times 2 + 0$ : dernier reste non nul $12$ ✓.

3. Pour $221$ : on teste les premiers jusqu’à $\sqrt{221} \approx 14{,}9$, soit $2, 3, 5, 7, 11, 13$. Et $221 = 13 \times 17$ : pas premier. Pour $223$ : $\sqrt{223} \approx 14{,}9$ également ; $223$ est impair, sa somme de chiffres $7$ n’est pas divisible par $3$, il ne finit ni par $0$ ni par $5$, et $223 = 7 \times 31 + 6 = 11 \times 20 + 3 = 13 \times 17 + 2$ : aucun premier jusqu’à $13$ ne le divise, donc $223$ est premier.

Réflexe à retenir : pour tester la primalité de $n$, il suffit d’essayer les diviseurs premiers jusqu’à $\sqrt{n}$ — au-delà, tout diviseur aurait un « partenaire » plus petit que $\sqrt{n}$, déjà testé. Et la décomposition en facteurs premiers donne le PGCD sans aucune division euclidienne.

1. Petit théorème de Fermat : si $p$ est premier et ne divise pas $a$, alors $a^{p-1} \equiv 1 \pmod p$ (et pour tout entier $a$ : $a^p \equiv a \pmod p$). Ici $13$ est premier et ne divise pas $2$, donc :

$2^{13 - 1} = 2^{12} \equiv 1 \pmod{13}$

2. On divise l’exposant par $12$ : $2026 = 12 \times 168 + 10$. Alors :

$2^{2026} = \left(2^{12}\right)^{168} \times 2^{10} \equiv 1^{168} \times 2^{10} \equiv 2^{10} \pmod{13}$

Or $2^{10} = 1\,024 = 13 \times 78 + 10$, donc $2^{2026} \equiv 10 \pmod{13}$ : le reste est $10$.

3. On applique la deuxième version du théorème avec $p = 7$, valable pour tout entier $n$ (divisible par $7$ ou non) :

$n^7 \equiv n \pmod 7 \qquad \text{donc} \qquad n^7 - n \equiv 0 \pmod 7$

c’est-à-dire que $7$ divise $n^7 - n$, pour tout $n \in \mathbb{N}$.

Réflexe à retenir : modulo un premier $p$, Fermat te donne l’exposant qui « remet le compteur à $1$ » : c’est $p - 1$, pas $p$. Ensuite, même scénario que pour toutes les grandes puissances : division euclidienne de l’exposant, puis compatibilité des congruences. Et la version $a^p \equiv a \pmod p$, valable sans condition, expédie les divisibilités du type $n^p - n$.