PGCD et algorithme d'Euclide : le calcul, sa preuve et les PGCD qui dépendent de n

Le PGCD ouvre la partie arithmétique de l'option maths expertes de terminale. Le programme (BO spécial n° 8 du 25 juillet 2019) range sous la même ligne « PGCD de deux entiers. Algorithme d'Euclide » et demande de savoir déterminer le PGCD de deux entiers ; l'algorithme sert ensuite à fabriquer les coefficients du théorème de Bézout.

Le plus grand diviseur commun, et ses cas limites

Soient a et b deux entiers relatifs non tous deux nuls. L'ensemble de leurs diviseurs communs contient 1 et il est fini, puisque tout diviseur d'un entier non nul n vérifie |d| ≤ |n|. Il a donc un plus grand élément, noté PGCD(a ; b). C'est un entier naturel non nul.

Pour 84 et 30 : les diviseurs positifs de 84 sont 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84, ceux de 30 sont 1, 2, 3, 5, 6, 10, 15, 30. Les diviseurs communs positifs sont 1, 2, 3 et 6, donc PGCD(84 ; 30) = 6. Cette liste devient vite impraticable dès que les nombres grossissent, d'où l'algorithme.

Trois conventions reviennent dans les exercices. Les signes ne comptent pas : PGCD(a ; b) = PGCD(|a| ; |b|), par exemple PGCD(−84 ; 30) = 6. Pour a ≠ 0, PGCD(a ; 0) = |a|, car tout entier divise 0. Enfin, a et b sont dits premiers entre eux lorsque PGCD(a ; b) = 1.

Pourquoi PGCD(a ; b) = PGCD(b ; r)

Soient a ∈ ℤ et b ∈ ℕ*, et a = bq + r la division euclidienne de a par b, avec 0 ≤ r < b. On montre que a et b ont exactement les mêmes diviseurs communs que b et r.

Si d divise a et b, il divise toute combinaison de a et b à coefficients entiers, en particulier r = a − bq. Réciproquement, si d divise b et r, il divise a = bq + r. Les deux ensembles de diviseurs communs sont égaux, donc ils ont le même plus grand élément.

L'algorithme s'arrête : les restes successifs sont des entiers naturels strictement décroissants (chaque reste est inférieur au diviseur, qui était le reste précédent), et une telle suite ne peut pas être infinie. Le dernier reste non nul r_k vérifie PGCD(a ; b) = PGCD(r_k ; 0) = r_k.

Cette preuve donne plus que le PGCD : à chaque étape, l'ensemble des diviseurs communs est conservé. On en déduit que les diviseurs communs de a et b sont exactement les diviseurs de leur PGCD. On en tire aussi PGCD(ka ; kb) = k × PGCD(a ; b) pour tout entier k ≥ 1, puisque multiplier a et b par k multiplie par k chaque ligne de l'algorithme, donc le dernier reste non nul.

Dérouler l'algorithme, puis l'appliquer à des expressions en n

En devoir surveillé, je fais écrire chaque division sous la forme « dividende = quotient × diviseur + reste », une ligne par division, en vérifiant à chaque fois que le reste est positif et strictement inférieur au diviseur. Le diviseur d'une ligne devient le dividende de la suivante, le reste devient le diviseur. On s'arrête au reste nul et on entoure le reste précédent.

Exemple 1 · PGCD(84 ; 30)

Rédaction. 84 = 2 × 30 + 24 ; 30 = 1 × 24 + 6 ; 24 = 4 × 6 + 0. Le dernier reste non nul est 6, donc PGCD(84 ; 30) = 6. On retrouve le résultat de la liste des diviseurs, en trois lignes.

Exemple 2 · PGCD(1 071 ; 462), et une fraction à simplifier

Rédaction. 1 071 = 2 × 462 + 147 ; 462 = 3 × 147 + 21 ; 147 = 7 × 21 + 0. Donc PGCD(1 071 ; 462) = 21. Comme 1 071 = 21 × 51 et 462 = 21 × 22, la fraction 462/1 071 se simplifie en 22/51, qui est irréductible puisque PGCD(51 ; 22) = 1.

Par les décompositions en facteurs premiers, 1 071 = 3² × 7 × 17 et 462 = 2 × 3 × 7 × 11, d'où PGCD = 3 × 7 = 21. Le résultat est le même, mais il faut d'abord trouver le facteur 17, ce que l'algorithme évite. La décomposition est traitée dans l'article sur les nombres premiers et la décomposition.

Exemple 3 · Un PGCD qui dépend de n

Énoncé. Pour n ∈ ℕ, on pose a = n + 3 et b = 2n + 1. Déterminer les valeurs possibles de PGCD(a ; b), puis les entiers n pour lesquels il vaut 5.

Rédaction. Soit d = PGCD(a ; b). Il divise a et b, donc il divise 2a − b = 2(n + 3) − (2n + 1) = 5. Comme d est un diviseur positif de 5, d = 1 ou d = 5.

Si d = 5, alors 5 divise n + 3, donc n ≡ 2 [5]. Réciproquement, si n = 5k + 2 avec k ∈ ℕ, alors n + 3 = 5(k + 1) et 2n + 1 = 10k + 5 = 5(2k + 1) : 5 divise a et b, et comme d ∈ {1 ; 5}, d = 5. Conclusion : PGCD(n + 3 ; 2n + 1) = 5 si n ≡ 2 [5], et 1 sinon. Contrôle : n = 7 donne PGCD(10 ; 15) = 5, n = 0 donne PGCD(3 ; 1) = 1.

La combinaison 2a − b se choisit pour éliminer n. La réciproque est obligatoire : savoir que d divise 5 ne dit pas encore pour quels n il vaut 5.

Le rectangle 84 × 30 découpé en carrés

La figure donne une lecture géométrique de l'exemple 1. Le rectangle de côtés 84 et 30 apparaît d'abord. On y découpe ensuite deux carrés de côté 30 : c'est la division 84 = 2 × 30 + 24, et il reste une bande de 24 sur 30. Dans cette bande se place un carré de côté 24 (30 = 1 × 24 + 6), qui laisse une bande de 24 sur 6. Quatre carrés de côté 6 la remplissent exactement (24 = 4 × 6 + 0) : le reste est nul. Pour finir, le quadrillage de pas 6 recouvre tout le rectangle, en 14 × 5 = 70 carreaux.

Un carré de côté d pave le rectangle sans débord si et seulement si d divise 84 et 30. Le plus grand carré qui y parvient a donc pour côté le PGCD, et le découpage glouton de la figure le trouve sans essayer les diviseurs un par un.

Les erreurs sur le PGCD qui coûtent des points

• Prendre le dernier reste au lieu du dernier reste non nul : le PGCD n'est jamais 0.
• Écrire une division avec un reste trop grand ou négatif, par exemple 84 = 1 × 30 + 54 : ce n'est pas la division euclidienne, et rien ne garantit plus que l'algorithme s'arrête au PGCD.
• Dans un PGCD qui dépend de n, conclure « d divise 5 donc d = 5 » : il reste à trouver les n pour lesquels 5 divise effectivement les deux nombres.
• Croire qu'une égalité au + bv = 5 prouve que le PGCD vaut 5 : elle prouve seulement que le PGCD divise 5.

Trois exercices corrigés sur le PGCD

Exercice 1 · Sept divisions et une fraction irréductible

Énoncé. Calculer PGCD(2 024 ; 1 166) par l'algorithme d'Euclide, puis écrire 1 166/2 024 sous forme irréductible.

Correction. 2 024 = 1 × 1 166 + 858 ; 1 166 = 1 × 858 + 308 ; 858 = 2 × 308 + 242 ; 308 = 1 × 242 + 66 ; 242 = 3 × 66 + 44 ; 66 = 1 × 44 + 22 ; 44 = 2 × 22 + 0. Donc PGCD(2 024 ; 1 166) = 22.

Comme 2 024 = 22 × 92 et 1 166 = 22 × 53, on obtient 1 166/2 024 = 53/92, irréductible : 22 = PGCD(22 × 92 ; 22 × 53) = 22 × PGCD(92 ; 53), donc PGCD(92 ; 53) = 1.

Exercice 2 · PGCD(3n + 1 ; n + 2)

Énoncé. Pour n ∈ ℕ, déterminer selon n le PGCD de 3n + 1 et n + 2.

Correction. Soit d ce PGCD. Il divise 3(n + 2) − (3n + 1) = 5, donc d = 1 ou d = 5.

Si d = 5, 5 divise n + 2, donc n ≡ 3 [5]. Réciproquement, si n = 5k + 3 avec k ∈ ℕ, alors n + 2 = 5(k + 1) et 3n + 1 = 15k + 10 = 5(3k + 2), donc d = 5. Ainsi PGCD(3n + 1 ; n + 2) = 5 si n ≡ 3 [5], et 1 sinon. Pour n = 3 : PGCD(10 ; 5) = 5.

Exercice 3 · Deux entiers de somme 84 et de PGCD 12

Énoncé. Déterminer tous les couples d'entiers naturels (a ; b) tels que a < b, a + b = 84 et PGCD(a ; b) = 12.

Correction. Comme 12 divise a et b, on écrit a = 12a′ et b = 12b′ avec a′, b′ entiers naturels. Alors PGCD(a ; b) = 12 × PGCD(a′ ; b′), donc PGCD(a′ ; b′) = 1. La somme donne 12(a′ + b′) = 84, soit a′ + b′ = 7, avec a′ < b′.

Les couples (a′ ; b′) possibles sont (0 ; 7), (1 ; 6), (2 ; 5), (3 ; 4). Le premier est exclu car PGCD(0 ; 7) = 7 ; les trois autres sont formés d'entiers premiers entre eux. D'où (a ; b) ∈ {(12 ; 72) ; (24 ; 60) ; (36 ; 48)}. Vérification : PGCD(12 ; 72) = 12, PGCD(24 ; 60) = 12, PGCD(36 ; 48) = 12.