I- À quoi sert le PGCD ?

PGCD signifie Plus Grand Commun Diviseur. Le PGCD de deux nombres entiers est leur plus grand diviseur commun. En pratique, le PGCD permet de résoudre des problèmes dans lesquels on cherche à :
- partager deux quantités en parts égales, sans reste ;
- faire des groupes ou des paquets identiques ;
- déterminer le nombre maximum de groupes identiques ;
- déterminer la plus grande taille possible pour découper ou ranger des objets sans reste.

Lorsqu'un problème parle de :
- « partager équitablement sans reste » ;
- « faire des paquets identiques » ;
- « faire le plus grand nombre de groupes possibles » ;
- « trouver la plus grande taille possible » ;
il peut s'agir d'un problème de PGCD.

II- Le PGCD par la méthode de décomposition en produits de facteurs premiers 

1- Les nombres premiers : les briques de construction

Un nombre premier est un nombre entier supérieur à 1 qui possède exactement deux diviseurs : 1 et lui-même. Quelques nombres premiers à connaître : 2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 ; 23 ; 29 ; …
Pour calculer un PGCD par décomposition en facteurs premiers, on suit trois étapes :

a. Décomposer chaque nombre en facteurs premiers.
b. Chercher les facteurs premiers communs.
c. Multiplier les facteurs communs.

On peut imaginer que chaque nombre est construit avec des « briques ». Pour trouver le PGCD, on conserve uniquement les briques que les deux nombres possèdent en commun.

2- Calculer un PGCD en 3 étapes

Exemple : calculons le PGCD de 462 et 561.

Étape 1 : Décomposer 462

On divise successivement par des nombres premiers.
462 ÷ 2 = 231
231 n'est pas divisible par 2.
La somme de ses chiffres est :
2 + 3 + 1 = 6
Donc 231 est divisible par 3 :
231 ÷ 3 = 77
77 n'est pas divisible par 3 ni par 5.
On teste 7 :
77 ÷ 7 = 11
11 est un nombre premier :
11 ÷ 11 = 1
Donc :
462 = 2 × 3 × 7 × 11


Étape 2 : Décomposer 561
561 n'est pas divisible par 2.
La somme de ses chiffres est :
5 + 6 + 1 = 12
Donc 561 est divisible par 3 :
561 ÷ 3 = 187
187 n'est pas divisible par 3, ni par 5, ni par 7.
On teste 11 :
187 ÷ 11 = 17
17 est un nombre premier :
17 ÷ 17 = 1
Donc :
561 = 3 × 11 × 17

Étape 3 : Chercher les facteurs communs
On compare les deux décompositions :
462 = 2 × 3 × 7 × 11
561 = 3 × 11 × 17
Les facteurs premiers communs sont 3 et 11. C'est-à-dire que 3 et 11 se retrouvent en même temps parmi les diviseurs de 262 et 561.

On les multiplie alors 3 et 11.

PGCD(462 ; 561) = 3 × 11
PGCD(462 ; 561) = 33

À retenir
Pour calculer le PGCD par décomposition en facteurs premiers, on cherche les facteurs communs et on les multiplie.
Pour que les divisions soient plus faciles, on fait souvent comme sur la feuille suivante.

II- LE PGCD PAR LES MÉTHODES DE SOUSTRACTION ET LES DIVISIONS D'EUCLIDE

Il existe plusieurs méthodes pour calculer le PGCD de deux nombres. Voici deux méthodes fondées sur le principe des divisions successives.

Méthode A : Les soustractions successives

Cette méthode consiste à soustraire le plus petit nombre du plus grand, puis à recommencer avec le résultat obtenu et le plus petit nombre.
Elle est surtout pratique lorsque les nombres sont relativement petits.

Exemple : calculons le PGCD de 12 et 8
12 − 8 = 4
On recommence avec 8 et 4 :
8 − 4 = 4
On recommence avec 4 et 4 :
4 − 4 = 0
On s'arrête.
Le PGCD est le dernier nombre non nul obtenu :
PGCD(12 ; 8) = 4

À retenir
Avec la méthode des soustractions, on soustrait le plus petit nombre du plus grand jusqu'à obtenir 0. Le dernier nombre non nul est le PGCD.

Méthode B : Les divisions successives d'Euclide

Cette méthode est généralement plus rapide, notamment lorsque les nombres sont grands.
On divise le plus grand nombre par le plus petit et on cherche le reste.
Puis on recommence avec :
l'ancien diviseur et le reste obtenu.
On continue jusqu'à obtenir un reste égal à 0.
Le dernier reste non nul est le PGCD.

Exemple : calculons le PGCD de 150 et 60
On effectue la division :
150 ÷ 60 = 2, reste 30
On recommence avec 60 et 30 :
60 ÷ 30 = 2, reste 0
On s'arrête.
Le dernier reste non nul est 30.
Donc :
PGCD(150 ; 60) = 30

À retenir
Avec l'algorithme d'Euclide, on divise, on prend le reste, on recommence et on s'arrête lorsque le reste est 0. Le dernier reste non nul est le PGCD.

III- Utiliser le PGCD dans un problème

Exemple :
Un salon mesure 462 cm sur 561 cm. On veut le carreler avec des carreaux carrés les plus grands possibles, sans découper aucun carreau.

1. Quelle doit être la longueur du côté d'un carreau ?
On cherche la plus grande longueur qui divise à la fois 462 et 561.
On calcule donc :
PGCD(462 ; 561) = 33
Le côté de chaque carreau mesure donc 33 cm.
2. Combien faut-il de carreaux dans chaque direction ?
Sur le côté de 462 cm :
462 ÷ 33 = 14
Il faut donc 14 carreaux.
Sur le côté de 561 cm :
561 ÷ 33 = 17
Il faut donc 17 carreaux.

3. Combien faut-il de carreaux au total ?
14 × 17 = 238
Il faut donc 238 carreaux.