3e ➗ Arithmétique Étape 6 / 7 du parcours

PGCD et fractions irréductibles

Le PGCD de deux nombres : le calculer avec les diviseurs, la décomposition ou l’algorithme d’Euclide, puis rendre une fraction irréductible.

📚 Avant de commencer, il faut savoir : Décomposition en facteurs premiers , Fractions égales et simplification

Le PGCD est le plus grand nombre qui divise deux nombres à la fois.

Un fleuriste a 84 roses et 60 tulipes. Il veut des bouquets tous identiques, en utilisant toutes les fleurs.

Le PGCD de 84 et 60 vaut 12 : il fait 12 bouquets de 7 roses et 5 tulipes. Bonus : il simplifie aussi les fractions, $\frac{60}{84} = \frac{5}{7}$ .

Diviseurs communs et PGCD

Définition

Un diviseur commun à deux nombres entiers $a$ et $b$ est un nombre qui divise à la fois $a$ et $b$ .

Le PGCD de $a$ et $b$ est leur Plus Grand Commun Diviseur. On le note $\text{PGCD}(a\,;b)$ .

Pour le fleuriste :

diviseurs de 84 : 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84 ;
diviseurs de 60 : 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.

Les diviseurs communs sont 1, 2, 3, 4, 6 et 12. Donc $\text{PGCD}(84\,;60) = 12$ : il peut faire 12 bouquets, chacun avec $84 \div 12 = 7$ roses et $60 \div 12 = 5$ tulipes.

Méthode 1 : avec la décomposition en facteurs premiers

Lister tous les diviseurs devient vite long. Plus rapide : on décompose les deux nombres et on garde les facteurs premiers communs.

PGCD(84 ; 60)

$84 = 2^2 \times 3 \times 7$
$60 = 2^2 \times 3 \times 5$

Les facteurs communs sont $2^2$ et $3$ (on prend chaque facteur commun avec le plus petit exposant).

$\text{PGCD}(84\,;60) = 2^2 \times 3 = 12$ .

Méthode 2 : l’algorithme d’Euclide, en images

Le carreleur a une autre méthode. Il doit couvrir une pièce de 84 dm sur 60 dm avec des carreaux carrés tous identiques, les plus grands possibles, sans les couper. Il commence par poser le plus grand carré possible (60 × 60), puis dans le morceau restant (60 × 24) les plus grands carrés possibles (24 × 24), et ainsi de suite. Le dernier carré qui remplit exactement le morceau restant a pour côté le PGCD !

Clique sur « Découper » pour voir les étapes. Change les dimensions : à chaque étape, on écrit une division euclidienne. Le pointillé final montre que le petit carré pave tout le rectangle.

Algorithme d’Euclide

Pour calculer $\text{PGCD}(a\,;b)$ avec $a > b$ :

on effectue la division euclidienne de $a$ par $b$ : $a = b \times q + r$ ;
on remplace $a$ par $b$ , et $b$ par le reste $r$ ;
on recommence jusqu’à obtenir un reste nul.

Le PGCD est le dernier reste non nul.

Un peu d’histoire

Cet algorithme a plus de 2 300 ans ! On le trouve, vers 300 av. J.-C., dans les Éléments d’Euclide, le grand livre de mathématiques de l’Antiquité grecque. Euclide ne faisait pas de divisions : il retranchait le petit nombre du grand, encore et encore, ce qui revient au même. L’informaticien Donald Knuth l’a surnommé « le grand-père de tous les algorithmes », car c’est le plus ancien algorithme non trivial encore utilisé aujourd’hui. Et il sert toujours : ta carte bancaire et les messageries chiffrées utilisent des cousins de l’algorithme d’Euclide pour protéger tes données.

PGCD(1 053 ; 325) avec Euclide

$1\,053 = 325 \times 3 + 78$
$325 = 78 \times 4 + 13$
$78 = 13 \times 6 + 0$

Le dernier reste non nul est 13 : $\text{PGCD}(1\,053\,;325) = 13$ . Trois lignes seulement, même avec de grands nombres !

Pourquoi c’est vrai ?— facultatif, à sauter en première lecture

Pourquoi PGCD $(a\,;b)$ = PGCD $(b\,;r)$ quand $a = b \times q + r$ ? Il suffit de montrer que $a$ et $b$ ont exactement les mêmes diviseurs communs que $b$ et $r$ .

Si $d$ divise $a$ et $b$ , alors il divise $r = a - b \times q$ (une différence de multiples de $d$ est un multiple de $d$ ).
Si $d$ divise $b$ et $r$ , alors il divise $a = b \times q + r$ .

Les deux couples ont donc la même liste de diviseurs communs, et en particulier le même plus grand. À chaque étape, les nombres diminuent sans que le PGCD change ; quand le reste devient nul, PGCD $(d\,;0) = d$ : c’est le dernier reste non nul.

Rendre une fraction irréductible

Définition

Une fraction est irréductible lorsque son numérateur et son dénominateur n’ont pas d’autre diviseur commun que 1. On dit qu’ils sont premiers entre eux.

Simplifier en une seule étape

En divisant le numérateur et le dénominateur par leur PGCD, on obtient directement la fraction irréductible.

Simplifier 1 053/325

On a trouvé $\text{PGCD}(1\,053\,;325) = 13$ . Donc :

\frac{1\,053}{325} = \frac{1\,053 \div 13}{325 \div 13} = \frac{81}{25}

$81 = 3^4$ et $25 = 5^2$ n’ont aucun facteur commun : la fraction $\dfrac{81}{25}$ est bien irréductible.

Attention

Si tu simplifies par un diviseur commun qui n’est pas le PGCD (par exemple par 2 pour $\dfrac{84}{60}$ ), la fraction obtenue $\dfrac{42}{30}$ n’est pas encore irréductible : il faut continuer.
Deux nombres premiers entre eux ne sont pas forcément premiers : 8 et 15 ne sont pas premiers, mais $\text{PGCD}(8\,;15) = 1$ .
Dans l’algorithme d’Euclide, le PGCD est le dernier reste non nul, pas le reste nul ni le dernier quotient.

À quoi ça sert dans la vraie vie ?

Préparer des lots identiques : une association a 126 cahiers et 90 stylos pour des kits scolaires identiques. $\text{PGCD}(126\,;90) = 18$ : 18 kits de 7 cahiers et 5 stylos.
Carreler sans découpe : une terrasse de 4,20 m sur 3,15 m, soit 420 cm sur 315 cm, peut être couverte de dalles carrées de 105 cm au plus, car $\text{PGCD}(420\,;315) = 105$ (4 × 3 = 12 dalles).
Simplifier un rapport d’écran : un écran de 1 920 × 1 080 pixels a pour format $\dfrac{1\,920}{1\,080}$ . Avec $\text{PGCD} = 120$ , on obtient $\dfrac{16}{9}$ : c’est le format « 16/9 » écrit sur les télés.
Découper du tissu : une couturière veut couper un coupon de 150 cm sur 90 cm en carrés identiques les plus grands possibles pour un patchwork : des carrés de 30 cm, car $\text{PGCD}(150\,;90) = 30$ , soit 15 carrés.
Programmer : l’algorithme d’Euclide, vieux de plus de 2 300 ans, est encore utilisé chaque jour par les ordinateurs, notamment pour chiffrer les communications sur Internet.

🎯 Quiz : vérifie ce que tu as compris

Quel est le PGCD de 24 et 36 ?
Avec l’algorithme d’Euclide : 98 = 70 × 1 + 28 ; 70 = 28 × 2 + 14 ; 28 = 14 × 2 + 0. Quel est le PGCD de 98 et 70 ?
La fraction 35/48 est-elle irréductible ?
Quelle est la forme irréductible de 84/126 ?
Un pâtissier a 108 macarons au chocolat et 72 à la framboise. Il fait des boîtes identiques avec tous les macarons. Combien de boîtes au maximum ?
Un mur de 240 cm sur 180 cm est recouvert de carreaux carrés identiques, les plus grands possibles, sans découpe. Quel est le côté d’un carreau (en cm) ?