Terminale

PGCD, théorèmes de Bézout et de Gauss — Exercices d'application

1. PGCD et algorithme d’Euclide

↩ Revoir le cours

Exercice 1 — ⭐

Calcule, par l’algorithme d’Euclide, $\text{PGCD}(1\,071\,;\,462)$ et $\text{PGCD}(2\,027\,;\,1\,000)$ .
Rends irréductible la fraction $\dfrac{1\,071}{462}$ .
Montre que, pour tout entier $n$ , $\text{PGCD}(3n + 1\,;\,n) = 1$ .

Voir le corrigé

$1\,071 = 462 \times 2 + 147$ ; $462 = 147 \times 3 + 21$ ; $147 = 21 \times 7 + 0$ : PGCD $= 21$ . $2\,027 = 1\,000 \times 2 + 27$ ; $1\,000 = 27 \times 37 + 1$ ; $27 = 1 \times 27 + 0$ : PGCD $= 1$ .
$\dfrac{1\,071}{462} = \dfrac{21 \times 51}{21 \times 22} = \dfrac{51}{22}$ .
$3n + 1 = 3 \times n + 1$ : $\text{PGCD}(3n + 1\,;\,n) = \text{PGCD}(n\,;\,1) = 1$ .

2. Entiers premiers entre eux

↩ Revoir le cours

Exercice 2 — ⭐⭐

Les entiers $221$ et $187$ sont-ils premiers entre eux ?
Soit $n$ un entier naturel. On pose $a = 2n + 3$ et $b = n + 1$ . Montre que tout diviseur commun de $a$ et $b$ divise $1$ . Que peut-on en conclure ?
Soit $n \geqslant 1$ . Montre que $\text{PGCD}(n^2 + n\,;\,2n + 1) = 1$ .

Voir le corrigé

$221 = 187 \times 1 + 34$ ; $187 = 34 \times 5 + 17$ ; $34 = 17 \times 2$ : PGCD $= 17$ . Non ( $221 = 13 \times 17$ , $187 = 11 \times 17$ ).
Un diviseur commun $d$ divise $a - 2b = 2n + 3 - 2n - 2 = 1$ : $a$ et $b$ sont premiers entre eux, pour tout $n$ .
On remarque que $(2n + 1)^2 - 4(n^2 + n) = 4n^2 + 4n + 1 - 4n^2 - 4n = 1$ . C’est une relation de Bézout : $(n^2 + n) \times (-4) + (2n + 1) \times (2n + 1) = 1$ , avec $-4$ et $2n + 1$ entiers. Donc $n^2 + n$ et $2n + 1$ sont premiers entre eux.

3. Théorème de Bézout

↩ Revoir le cours

Exercice 3 — ⭐⭐

Détermine un couple d’entiers $(u\,;\,v)$ tel que $23u + 17v = 1$ .
En déduire un inverse de $23$ modulo $17$ , puis résous $23x \equiv 4\ [17]$ .
Vérifie ton résultat de la question 1 avec la fonction euclide_etendu du cours.

Voir le corrigé

$23 = 17 + 6$ ; $17 = 6 \times 2 + 5$ ; $6 = 5 + 1$ . En remontant : $1 = 6 - 5 = 6 - (17 - 2 \times 6) = 3 \times 6 - 17 = 3(23 - 17) - 17 = 3 \times 23 - 4 \times 17$ . Couple : $(3\,;\,-4)$ .
$23 \times 3 \equiv 1\ [17]$ : $3$ est un inverse de $23$ modulo $17$ . $23x \equiv 4 \iff x \equiv 3 \times 4 = 12\ [17]$ (on multiplie par $3$ ; c’est une équivalence car on peut remultiplier par $23$ ).
euclide_etendu(23, 17) renvoie (1, 3, -4).

Exercice 4 — ⭐⭐⭐

Chiffrement affine. On code chaque lettre par son rang $x$ ( $A = 0$ , …, $Z = 25$ ), puis on la remplace par la lettre de rang $y$ , reste de $7x + 3$ modulo $26$ .

Code le mot « OUI ».
Justifie que $7$ et $26$ sont premiers entre eux et trouve un inverse de $7$ modulo $26$ .
Exprime $x$ en fonction de $y$ modulo $26$ et décode la lettre « K ».
Pourquoi la clé $y \equiv 2x + 3\ [26]$ serait-elle une mauvaise idée ?

Voir le corrigé

O ( $14$ ) : $7 \times 14 + 3 = 101 \equiv 23$ → X. U ( $20$ ) : $143 \equiv 13$ → N. I ( $8$ ) : $59 \equiv 7$ → H. « OUI » devient « XNH ».
$26 = 7 \times 3 + 5$ , $7 = 5 + 2$ , $5 = 2 \times 2 + 1$ : PGCD $= 1$ . En remontant : $1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7$ . Donc $7 \times (-11) \equiv 1\ [26]$ : un inverse est $-11 \equiv 15$ (vérification : $7 \times 15 = 105 = 4 \times 26 + 1$ ).
$y \equiv 7x + 3 \iff 7x \equiv y - 3 \iff x \equiv 15(y - 3)\ [26]$ . K ( $10$ ) : $x \equiv 15 \times 7 = 105 \equiv 1$ → B.
$2$ et $26$ ne sont pas premiers entre eux : $2x + 3$ ne prend que des valeurs impaires modulo $26$ , deux lettres différentes (par exemple $x = 0$ et $x = 13$ ) ont le même code, et on ne peut pas décoder.

4. Théorème de Gauss

↩ Revoir le cours

Exercice 5 — ⭐⭐

On sait que $15$ divise $4n$ . Montre que $15$ divise $n$ .
Détermine les entiers $x$ tels que $9x \equiv 0\ [12]$ .
Montre que, pour tout entier $n$ , $n^5 - n$ est divisible par $30$ (on admettra que $n^5 - n$ est divisible par $2$ , par $3$ et par $5$ — on le démontrera avec le petit théorème de Fermat).

Voir le corrigé

$15 \mid 4n$ et $\text{PGCD}(15\,;\,4) = 1$ : par Gauss, $15 \mid n$ .
$12 \mid 9x \iff 4 \mid 3x$ (on divise par $3$ : $12k = 9x \iff 4k = 3x$ ). $4$ est premier avec $3$ , donc $4 \mid x$ : les solutions sont les multiples de $4$ .
$2$ et $3$ sont premiers entre eux et divisent $n^5 - n$ : $6 \mid n^5 - n$ . Puis $6$ et $5$ sont premiers entre eux et divisent $n^5 - n$ : $30 \mid n^5 - n$ .

5. Équations diophantiennes ax + by = c

↩ Revoir le cours

Exercice 6 — ⭐⭐

L’équation $6x + 15y = 4$ a-t-elle des solutions entières ?
Résous dans $\mathbb{Z}^2$ l’équation $5x - 8y = 1$ (on remarquera que $5 \times 5 - 8 \times 3 = 1$ ).
Résous dans $\mathbb{Z}^2$ l’équation $5x - 8y = 3$ .

Voir le corrigé

$\text{PGCD}(6\,;\,15) = 3$ ne divise pas $4$ : aucune solution.
Solution particulière $(5\,;\,3)$ . Si $5x - 8y = 1$ , alors $5(x - 5) = 8(y - 3)$ . $8$ divise $5(x - 5)$ et est premier avec $5$ : $x - 5 = 8k$ , puis $y - 3 = 5k$ . Réciproquement, $5(5 + 8k) - 8(3 + 5k) = 1$ . Solutions : $(5 + 8k\,;\,3 + 5k)$ , $k \in \mathbb{Z}$ .
$(15\,;\,9)$ est une solution particulière ( $3$ fois la précédente). Même raisonnement : $(15 + 8k\,;\,9 + 5k)$ , $k \in \mathbb{Z}$ , que l’on peut aussi écrire $(-1 + 8k'\,;\,-1 + 5k')$ avec $k' = k + 2$ .

Exercice 7 — ⭐⭐⭐

Problème de monnaie. Un distributeur ne rend que des pièces de $2$ € et des billets de $5$ €.

Écris l’équation qui traduit « rendre $n$ euros avec $x$ pièces et $y$ billets ». Pourquoi a-t-elle des solutions dans $\mathbb{Z}^2$ pour tout $n$ ?
Trouve toutes les façons de rendre $37$ € (avec $x \geqslant 0$ et $y \geqslant 0$ ).
Écris une fonction Python qui affiche toutes les façons de rendre n euros.

Voir le corrigé

$2x + 5y = n$ . $\text{PGCD}(2\,;\,5) = 1$ divise tout entier $n$ .
Solution particulière : $2 \times 16 + 5 \times 1 = 37$ . $2(x - 16) = 5(1 - y)$ , d’où $x = 16 + 5k$ , $y = 1 - 2k$ . Avec $x \geqslant 0$ et $y \geqslant 0$ : $k \geqslant -3{,}2$ et $k \leqslant 0{,}5$ , soit $k \in \{-3\,;\,-2\,;\,-1\,;\,0\}$ : $(1\,;\,7)$ , $(6\,;\,5)$ , $(11\,;\,3)$ , $(16\,;\,1)$ .

def rendus(n):
    for y in range(n // 5 + 1):
        if (n - 5 * y) % 2 == 0:
            print((n - 5 * y) // 2, "pièces et", y, "billets")

rendus(37)

Exercice 8 — ⭐⭐⭐

On cherche les entiers $N$ tels que $N \equiv 2\ [5]$ et $N \equiv 3\ [7]$ (« lemme chinois »).

Montre que $N$ vérifie les deux conditions si et seulement si il existe des entiers $x$ et $y$ tels que $N = 5x + 2 = 7y + 3$ , c’est-à-dire $5x - 7y = 1$ .
Résous $5x - 7y = 1$ (on remarquera que $5 \times 3 - 7 \times 2 = 1$ ).
En déduire que les solutions sont les entiers $N \equiv 17\ [35]$ .

Voir le corrigé

$N \equiv 2\ [5] \iff N = 5x + 2$ ; $N \equiv 3\ [7] \iff N = 7y + 3$ . Les deux ensemble : $5x + 2 = 7y + 3 \iff 5x - 7y = 1$ .
$5(x - 3) = 7(y - 2)$ ; $7$ premier avec $5$ divise $x - 3$ : $x = 3 + 7k$ , $y = 2 + 5k$ . Réciproquement ces couples conviennent.
$N = 5x + 2 = 5(3 + 7k) + 2 = 17 + 35k$ : $N \equiv 17\ [35]$ . (Vérification : $17 = 3 \times 5 + 2 = 2 \times 7 + 3$ .)