PGCD et divisibilité : recherche par soustractions et Euclide

1. Introduction et problématique

Situation-problème : dans une association sportive, on prépare des lots identiques pour une tombola. On dispose de 252 bracelets et de 180 porte-clés. On veut fabriquer le plus grand nombre possible de lots identiques, sans reste, en mettant le même nombre de bracelets et le même nombre de porte-clés dans chaque lot. Combien de lots peut-on préparer ?

Ce type de question revient à chercher un nombre qui divise exactement 252 et 180. Par exemple, 2 divise les deux nombres, car 252 ÷ 2 = 126 et 180 ÷ 2 = 90. Mais 2 n’est pas forcément le plus grand choix possible. On cherche donc le plus grand diviseur commun aux deux nombres : c’est le PGCD.

En classe de 3e, la notion de PGCD permet de résoudre des problèmes de partage équitable, de simplifier des fractions et de mieux comprendre la divisibilité. Deux méthodes importantes sont étudiées : la méthode par soustractions successives, qui aide à comprendre l’idée, et l’algorithme d’Euclide, qui est plus rapide et plus efficace.

Dans cette leçon, l’objectif est de savoir calculer un PGCD par soustractions successives et par l’algorithme d’Euclide, puis de l’utiliser pour simplifier une fraction jusqu’à obtenir une fraction irréductible.

2. Définition

Définition : Soient deux entiers positifs non nuls a et b. Le PGCD(a ; b), c’est-à-dire le plus grand commun diviseur de a et b, est le plus grand entier qui divise à la fois a et b.

Dire qu’un entier d divise un entier a signifie que la division de a par d donne un reste nul. Autrement dit, il existe un entier k tel que a = d × k. On dit aussi que a est un multiple de d.

Par exemple, 6 divise 42 car 42 = 6 × 7. De même, 6 divise 180 car 180 = 6 × 30. Ainsi, 6 est un diviseur commun de 42 et 180. Mais ce n’est pas forcément le plus grand.

La notation utilisée est : PGCD(a ; b). On lit : « PGCD de a et b ». Par exemple, PGCD(252 ; 180) désigne le plus grand commun diviseur de 252 et 180.

Quelques repères de vocabulaire sont essentiels :

• Diviseur commun : nombre entier qui divise exactement deux entiers.
• PGCD : plus grand de tous les diviseurs communs.
• Division euclidienne : écriture de la forme a = b × q + r, avec 0 ≤ r < b.
• Fraction irréductible : fraction que l’on ne peut plus simplifier par un diviseur commun supérieur à 1.

3. Propriétés et théorèmes

Théorème : Si a et b sont deux entiers positifs avec a ≥ b, et si la division euclidienne de a par b s’écrit a = b × q + r, alors PGCD(a ; b) = PGCD(b ; r).

Ce théorème est la base de l’algorithme d’Euclide. Il affirme que l’on peut remplacer le plus grand des deux nombres par le reste de sa division par le plus petit, sans changer le PGCD.

Exemple avec 252 et 180 :

252 = 180 × 1 + 72, donc PGCD(252 ; 180) = PGCD(180 ; 72).

180 = 72 × 2 + 36, donc PGCD(180 ; 72) = PGCD(72 ; 36).

72 = 36 × 2 + 0, donc l’algorithme s’arrête. Le dernier reste non nul est 36. Ainsi, PGCD(252 ; 180) = 36.

Une autre propriété utile concerne les soustractions successives :

Théorème : Si a ≥ b, alors PGCD(a ; b) = PGCD(a − b ; b).

Cette propriété signifie que soustraire le plus petit nombre au plus grand ne change pas les diviseurs communs. En répétant cette opération, on finit par obtenir deux nombres égaux : cette valeur commune est le PGCD.

4. Démonstration

On veut comprendre pourquoi l’algorithme d’Euclide fonctionne. On part de la division euclidienne de a par b, avec a ≥ b :

a = b × q + r, avec 0 ≤ r < b.

Supposons qu’un entier d divise a et b. Comme d divise b, il divise aussi b × q. Comme d divise a et b × q, il divise leur différence :

a − b × q = r.

Donc tout diviseur commun de a et b est aussi un diviseur commun de b et r.

Réciproquement, supposons qu’un entier d divise b et r. Alors d divise b × q et d divise r. Il divise donc leur somme :

b × q + r = a.

Donc tout diviseur commun de b et r est aussi un diviseur commun de a et b.

Les couples (a ; b) et (b ; r) ont donc exactement les mêmes diviseurs communs. Par conséquent, ils ont le même plus grand diviseur commun :

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

Cette démonstration explique l’idée de l’algorithme d’Euclide : à chaque étape, on remplace un couple de nombres par un couple plus petit, mais qui garde le même PGCD. Comme les restes diminuent, on finit nécessairement par obtenir un reste égal à 0. À ce moment-là, le dernier reste non nul est le PGCD.

5. Méthode pas à pas

Pour calculer un PGCD, on peut utiliser une routine simple : « Je repère / J’applique / Je vérifie ».

1. Je repère : j’identifie les deux entiers positifs non nuls. Je place le plus grand en premier si nécessaire. Je choisis une méthode : les soustractions successives pour comprendre, l’algorithme d’Euclide pour aller plus vite.
2. J’applique par soustractions : je soustrais le plus petit nombre au plus grand, puis je recommence avec les deux nombres obtenus. Je continue jusqu’à obtenir deux nombres égaux. Cette valeur commune est le PGCD.
3. J’applique par Euclide : j’écris la division euclidienne sous la forme a = b × q + r, avec 0 ≤ r < b. Puis je recommence avec b et r.
4. Je m’arrête : l’algorithme d’Euclide s’arrête uniquement lorsque le reste est égal à 0.
5. Je conclus : le PGCD est le dernier reste non nul, et non le reste nul.
6. Je vérifie : je contrôle que le nombre trouvé divise bien les deux nombres de départ.
7. J’utilise le PGCD pour une fraction : pour simplifier une fraction, je divise le numérateur et le dénominateur par leur PGCD. La fraction obtenue est irréductible.

Il faut toujours écrire clairement les calculs. Pour une division euclidienne, on vérifie que le reste est bien plus petit que le diviseur. Par exemple, dans 252 = 180 × 1 + 72, le reste 72 est bien inférieur à 180.

6. Exemple résolu 1 — cas direct

Calculer PGCD(84 ; 36) par l’algorithme d’Euclide.

On commence par diviser le plus grand nombre par le plus petit :

84 = 36 × 2 + 12.

Le reste est 12. D’après le théorème d’Euclide :

PGCD(84 ; 36) = PGCD(36 ; 12).

On poursuit :

36 = 12 × 3 + 0.

Le reste est maintenant égal à 0. L’algorithme s’arrête. Le dernier reste non nul est 12.

Donc PGCD(84 ; 36) = 12.

Vérification : 84 ÷ 12 = 7 et 36 ÷ 12 = 3. Le nombre 12 divise donc bien 84 et 36. Comme l’algorithme d’Euclide garantit que c’est le plus grand diviseur commun, le résultat est correct.

On peut aussi comprendre ce résultat avec les diviseurs. Les diviseurs de 84 sont notamment 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42 et 84. Les diviseurs de 36 sont 1, 2, 3, 4, 6, 9, 12, 18 et 36. Le plus grand diviseur commun est bien 12.

7. Exemple résolu 2 — cas inverse

On veut simplifier la fraction 180 ÷ 252, c’est-à-dire la fraction 180/252. Pour cela, on cherche d’abord PGCD(180 ; 252). Comme l’ordre n’a pas d’importance, PGCD(180 ; 252) = PGCD(252 ; 180).

Utilisons l’algorithme d’Euclide :

252 = 180 × 1 + 72.

180 = 72 × 2 + 36.

72 = 36 × 2 + 0.

Le dernier reste non nul est 36. Donc PGCD(252 ; 180) = 36, et donc PGCD(180 ; 252) = 36.

On divise maintenant le numérateur et le dénominateur par 36 :

180 ÷ 36 = 5.

252 ÷ 36 = 7.

Ainsi, 180/252 = 5/7.

La fraction 5/7 est irréductible, car 5 et 7 n’ont pas de diviseur commun supérieur à 1. Le PGCD de 5 et 7 est 1.

Attention : on aurait pu simplifier d’abord par 2, puis par 2, puis par 3, etc. Mais le PGCD permet de simplifier directement en une seule étape. Il évite de s’arrêter trop tôt avec une fraction encore simplifiable.

8. Exemple résolu 3 — problème concret

Un professeur prépare des pochettes identiques pour ses élèves. Il possède 96 cartes de calcul mental et 72 cartes de géométrie. Il veut utiliser toutes les cartes et préparer le plus grand nombre possible de pochettes identiques. Combien de pochettes peut-il préparer ? Que contiendra chaque pochette ?

Le nombre de pochettes doit diviser 96 et 72. Comme on veut le plus grand nombre possible de pochettes, on cherche PGCD(96 ; 72).

Calcul par l’algorithme d’Euclide :

96 = 72 × 1 + 24.

72 = 24 × 3 + 0.

Le dernier reste non nul est 24. Donc PGCD(96 ; 72) = 24.

Le professeur peut préparer 24 pochettes identiques.

On calcule maintenant le contenu de chaque pochette :

96 ÷ 24 = 4, donc chaque pochette contient 4 cartes de calcul mental.

72 ÷ 24 = 3, donc chaque pochette contient 3 cartes de géométrie.

Conclusion : il peut préparer 24 pochettes identiques, chacune contenant 4 cartes de calcul mental et 3 cartes de géométrie.

Ce type de problème est très fréquent : lorsqu’on cherche à répartir deux quantités en paquets identiques sans reste, le PGCD donne le nombre maximal de paquets.

9. Erreurs classiques à éviter

• Erreur : donner le dernier reste nul comme PGCD — À faire : entourer systématiquement le dernier reste non nul avant la ligne où le reste vaut 0.
• Erreur : s’arrêter dès qu’un reste semble petit — À faire : continuer les divisions euclidiennes jusqu’à obtenir un reste égal à 0.
• Erreur : confondre quotient et reste — À faire : réécrire la forme a = b × q + r et vérifier que 0 ≤ r < b.
• Erreur : simplifier une fraction avec un diviseur commun non maximal et penser avoir terminé — À faire : calculer le PGCD du numérateur et du dénominateur pour obtenir directement une fraction irréductible.
• Erreur : faire trop de soustractions successives avec des nombres éloignés — À faire : passer à l’algorithme d’Euclide, qui regroupe les soustractions grâce à la division euclidienne.
• Erreur : oublier que le PGCD doit diviser les deux nombres — À faire : vérifier à la fin que les deux divisions donnent des entiers.

10. À retenir

• Le PGCD(a ; b) est le plus grand entier qui divise à la fois a et b.
• Un diviseur commun de deux nombres les divise tous les deux sans reste.
• La méthode par soustractions repose sur la propriété PGCD(a ; b) = PGCD(a − b ; b), lorsque a ≥ b.
• L’algorithme d’Euclide repose sur la division euclidienne : a = b × q + r.
• La propriété essentielle est : PGCD(a ; b) = PGCD(b ; r).
• L’algorithme d’Euclide s’arrête quand le reste vaut 0.
• Le PGCD est le dernier reste non nul, jamais le reste nul.
• Pour simplifier une fraction, on divise le numérateur et le dénominateur par leur PGCD.
• Si le PGCD de deux entiers est 1, on dit qu’ils sont premiers entre eux.
• Une fraction est irréductible lorsque le PGCD de son numérateur et de son dénominateur est égal à 1.

11. Exercices d'application

Un PDF d’exercices peut accompagner cette leçon afin de s’entraîner progressivement : repérage des diviseurs communs, calculs par soustractions successives, complétion de divisions euclidiennes, rédaction complète de l’algorithme d’Euclide et simplification de fractions grâce au PGCD.

Aperçu des types d’exercices proposés :

• Repérer les diviseurs communs : lister les diviseurs de deux entiers, puis identifier leur plus grand diviseur commun.
• Calculer par soustractions successives : appliquer la méthode en remplaçant le plus grand nombre par la différence entre les deux nombres.
• Compléter l’algorithme d’Euclide : retrouver un quotient, un reste ou une ligne manquante dans une suite de divisions euclidiennes.
• Écrire l’algorithme d’Euclide : rédiger toutes les étapes pour calculer un PGCD.
• Simplifier une fraction grâce au PGCD : calculer le PGCD du numérateur et du dénominateur, puis donner la fraction irréductible.

Barème possible sur 10 points : identifier correctement les diviseurs communs, 2 points ; effectuer correctement les soustractions successives, 2 points ; poser les divisions euclidiennes dans le bon ordre, 2 points ; déterminer le PGCD comme dernier reste non nul, 2 points ; simplifier une fraction jusqu’à une fraction irréductible, 2 points.

12. Questions fréquentes