LEÇON 1: Algorithme d’Euclide, algorithme des soustractions et le plus grand commun diviseur
OBJECTIFS PÉDAGOGIQUES :
- Utiliser l’algorithme d’Euclide, l’algorithme des soustractions pour calculer le PGCD de deux nombres entiers naturels ;
- Résoudre des problèmes faisant appel au PGCD.
PRÉREQUIS
- Décomposer en produit des facteurs premiers les nombres 48 et 32, puis en déduire leur PGCD
- Effectuer la division euclidienne de 56 par 24.
Solution
-
48 = $latex 2^4 \times 3$ et 32 = $latex 2^5$ ;
Le PGCD de 48 et 32 est $latex 2^4 = 16$
NB : le PGCD de deux entiers naturels est le produit des facteurs communs à ces deux nombres.
2) 56 = 24 × 2 + 8
SITUATION PROBLÈME
Le père d’Agnès élève de la classe de troisième a le projet de carreler le sol de son salon de dimensions
4,62 m × 5,61 m à l’aide des carreaux. Il ne voudrait pas des coupes de carreaux, ni d’espaces entre deux
carreaux consécutifs posés au sol. Il fait appel à sa fille Agnès pour déterminer le nombre de carreaux
minimum nécessaire pour la réalisation de ce projet. Aider Agnès à déterminer ce nombre de carreau.
ACTIVITÉ D’APPRENTISSAGE
-
Déterminer le PGCD de 462 et 561 à l’aide de la décomposition en produit des facteurs premiers.
-
a) Compléter le tableau ci-dessous.
| a | 561 | 462 | 363 | | | | | | | |
| b | 462 | | 99 | | | | | | | 33 |
| a − b | 99 | 363 | | | | | | | | 0 |
b) Comparer le dernier résultat non nul de a − b au PGCD de 561 et 462.
3) a) Compléter le tableau ci-dessous. r est le reste de la division de a par b.
b) Comparer le dernier reste non nul au PGCD de 561 et 462.
4) On pose L la longueur en cm et l la largeur en cm du salon du père de Agnès.
-
Que représente le PGCD $(L ; l)$ ?
-
Effectuer les opérations :
$latex \dfrac{L}{PGCD(L,l)}$
et
$latex \dfrac{l}{PGCD(L,l)}$.
Que représentent ces résultats respectivement pour la longueur et pour la largeur ?
-
Détermine alors le nombre de carreaux nécessaires pour carreler le salon du père d’Agnès.
SOLUTION :
1) 561 = $latex 3 \times 11 \times 17$ et 462 = $latex 2 \times 3 \times 7 \times 11$
PGCD(561 ; 462) = 33
2) a) Complétons le tableau
| a | 561 | 462 | 363 | 264 | 165 | 99 | 66 | 33 |
| b | 462 | 99 | 99 | 99 | 66 | 33 | 33 | 33 |
| a − b | 99 | 363 | 264 | 165 | 66 | 33 | 33 | 0 |
b) Le dernier résultat non nul de a − b est 33 qui est égal au PGCD de 561 et 462.
3) a) Complétons le tableau. r est le reste de la division de a par b.
| a | 561 | 462 | 99 | 66 |
| b | 462 | 99 | 66 | 33 |
| r | 99 | 66 | 33 | 0 |
b) Le dernier reste non nul de a par b est 33 qui est égal au PGCD de 561 et 462.
4) a) Le PGCD $(L ; l)$ représente la longueur du côté du carreau.
D’où la longueur du côté des carreaux est 33 cm.
b)
$latex \dfrac{L}{PGCD(L,l)}=\dfrac{561}{33}=17$
et
$latex \dfrac{l}{PGCD(L,l)}=\dfrac{462}{33}=14$.
17 représente le nombre de carreaux minimum nécessaires à utiliser dans le sens de la longueur et
14 représente le nombre de carreaux minimum à utiliser dans le sens de la largeur.
c) Le nombre de carreau minimal à utiliser est
$latex 17 \times 14 = 238$ carreaux.
RÉSUMÉ
Soient a, b, q et d des nombres entiers naturels non nuls.
-
On dit que d est un diviseur commun de a et b
si d est un diviseur de a et b.
-
On appelle plus grand commun diviseur de a et b et on note
PGCD(a ; b) le plus grand entier des diviseurs communs de a et b.
-
On appelle plus petit commun multiple de a et b et on note
PPCM(a ; b) le plus petit entier non nul des multiples communs de a et b.
Pour déterminer le PGCD de deux nombres entiers naturels non nuls tels que
a > b, on peut soit utiliser l’algorithme des soustractions successives,
soit utiliser l’algorithme d’Euclide ou encore des divisions euclidiennes successives :
ALGORITHME DES SOUSTRACTIONS SUCCESSIVES
On effectue des soustractions successives de a par b comme l’indique le tableau
de la question 2 de l’activité. Le PGCD(a ; b) est le dernier résultat non nul de
a − b.
Exemple : Déterminons le PGCD (168 ; 120).
168 − 120 = 48 ;
120 − 48 = 72 ;
72 − 48 = 24 ;
48 − 24 = 24 ;
24 − 24 = 0.
Donc PGCD(168 ; 120) = 24 car le résultat de la dernière différence non nulle est 24.
ALGORITHME D’EUCLIDE
On effectue les divisions euclidiennes successives de a par b comme l’indique
le tableau de la question 3 de l’activité. Le PGCD(a ; b) est le dernier reste non nul.
Cet algorithme est basé sur la propriété suivante :
si a = bq + r, alors
PGCD(a ; b) = PGCD(b ; r)
où r est le reste de la division euclidienne de a par b.
Exemple : Déterminons le PGCD (375 ; 2020).
2020 = 5 × 375 + 145 ;
375 = 2 × 145 + 85 ;
145 = 1 × 85 + 60 ;
85 = 1 × 60 + 25 ;
60 = 2 × 25 + 10 ;
25 = 2 × 10 + 5 ;
10 = 2 × 5 + 0.
Donc le PGCD (375 ; 2020) = 5 car le dernier reste non nul des divisions est 5.
REMARQUE
-
Si b est un diviseur de a, alors PGCD(a ; b) = b.
-
PGCD(a ; b) = 1 équivaut à
$latex \dfrac{a}{b}$
est irréductible et on dit que les nombres a et b
sont premiers entre eux.
PGCD(a ; 1) = 1.
EXERCICE D’APPLICATION :
-
Déterminer à l’aide de l’algorithme des soustractions successives le
PGCD(31 ; 14).
-
Déterminer à l’aide de l’algorithme d’Euclide le
PGCD(3,750).
-
Une entreprise de fabrication des produits alimentaires a fabriqué
700 bonbons chocolat et 450 les bonbons de cœurs.
-
Déterminer le nombre de paquet maximum identique contenant à la fois
les deux marques de bonbons.
-
Déterminer le nombre de bonbons chocolat que contient chaque paquet.
SOLUTION
1. Déterminons le PGCD(31 ; 14) à l’aide
de l’algorithme des soustractions.
| a | 31 | 17 | 14 | 11 | 8 | 5 | 3 | 2 | 1 |
| b | 14 | 14 | 3 | 3 | 3 | 3 | 2 | 1 | 1 |
| a − b | 17 | 3 | 11 | 8 | 5 | 2 | 1 | 1 | 0 |
Donc PGCD(31 ; 14) = 1.
2. Déterminons le (300 ; 75) à l’aide de
l’algorithme d’Euclide.
Donc PGCD(300 ; 75) = 150.
