PGCD
|
I) Rappels et vocabulaire
Définition
Soient \(a\) et \(b\) deux entiers. On dit que \(a\) est divisible par
\(b\), que \(b\) est un diviseur
de \(a\), et que \(a\) est un multiple
de \(b\) si le ratio \(\displaystyle \frac{a}{b}\)
est un entier.
Exemple 1 :
Prenons \(a=48\) et \(b=6\).
\(\displaystyle \frac{48}{6}=8\)
8 est un entier.
On peut ainsi écrire que 48 est divisible par 6, que 6 est un diviseur de 48 ou encore que 48 est un multiple de 6.
Définition
Un entier
est dit premier lorsqu'il
n'a que deux diviseurs : 1 et lui-même.
Exemple 2 :
5 est premier car il n'est divisible que par 1 et lui-même (5).
6 n'est pas premier car il est divisible par 1, 2, 3 et 6.
Voici les nombres premiers jusqu'à 100 : 2, 3, 5, 7, 11, 13, 17, 19, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97.
Rappel des critères élémentaires de divisibilité
- 2 s'il est pair
- 3 si la somme de ses chiffres est divisible par 3
- 4 si le nombre formé par le chiffre des dizaines et des unités est lui-même divisible par 4
- 5 si le chiffre de ses unités est 0 ou 5
- 9 si la somme de ses chiffres est divisible par 9
- 11 si la différence entre la somme des chiffres de rang pair et la somme des chiffres de rang impair est un multiple de 11
- 25 lorsque les deux chiffres de droite du nombre sont 00, 25, 50 ou 75
- 100 lorsque le nombre se termine par 00
- 3 si la somme de ses chiffres est divisible par 3
- 4 si le nombre formé par le chiffre des dizaines et des unités est lui-même divisible par 4
- 5 si le chiffre de ses unités est 0 ou 5
- 9 si la somme de ses chiffres est divisible par 9
- 11 si la différence entre la somme des chiffres de rang pair et la somme des chiffres de rang impair est un multiple de 11
- 25 lorsque les deux chiffres de droite du nombre sont 00, 25, 50 ou 75
- 100 lorsque le nombre se termine par 00
Propriété
Pour trouver tous les diviseurs d'un nombre, il convient
d'essayer
tous les premiers entiers jusqu'à la partie entière de la racine de ce
nombre.
Exemple 3 : Cherchons tous les diviseurs de 210.
\(\sqrt{210}\approx 14.49\), par conséquent, on va tester tous les premiers entiers jusqu'à 14.
210 ÷ 1 = 210 donc 1 est un diviseur de 210. 210 est aussi un diviseur de 210 car 210 ÷ 210 = 1.
210 ÷ 2 = 105 donc 2 est un diviseur de 210. 105 est aussi un diviseur de 210 car 210 ÷ 105 = 2.
210 ÷ 3 = 70 donc 3 et 70 sont des diviseurs de 210.
210 ÷ 4 = 52.5 donc 4 n'est pas un diviseur de 210.
210 ÷ 5 = 42 donc 5 et 42 sont des diviseurs de 210.
210 ÷ 6 = 35 donc 6 et 35 sont des diviseurs de 210.
210 ÷ 7 = 30 donc 7 et 30 sont des diviseurs de 210.
210 ÷ 8 = 26.25 donc 8 n'est pas un diviseur de 210.
210 ÷ 9 ≈ 23.33 donc 9 n'est pas un diviseur de 210.
210 ÷ 10 = 21 donc 10 et 21 sont des diviseurs de 210.
210 ÷ 11 ≈ 19.09 donc 11 n'est pas un diviseur de 210.
210 ÷ 12 = 17.5 donc 12 n'est pas un diviseur de 210.
210 ÷ 13 ≈ 16.15 5 donc 13 n'est pas un diviseur de 210.
210 ÷ 14 = 15 donc 15 et 14 sont des diviseurs de 210.
Conclusion : tous les diviseurs de 210 sont : 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105 et 210.
Définition
On dit que \(c\) est un diviseur
commun de \(a\) et \(b\) si \(c\) divise à la fois \(a\) et \(b\).
Exemple 4 :
Cherchons les diviseurs communs de 12 et 18.
On cherche dans un premier temps tous les diviseurs de 12 : 1, 2, 3, 4, 6 et 12
... et ceux de 18 : 1, 2, 3, 6, 9 et 18.
Les diviseurs communs de 12 et 18 sont ceux qui figurent à la fois dans les deux listes (écrits en rouge) : 1, 2, 3 et 6.
II) PGCD de deux nombres
A) Définition du PGCD
Définition
Le Plus Grand
Diviseur Commun (PGCD) de deux entiers \(a\) et \(b\) est,
comme son nom l'indique, le plus grand diviseur commun de ces deux
nombres. On le note \(PGCD(a,b)\).
Exemple 5 :
En reprenant l'exemple 4, nous avons vu que 1, 2, 3 et 6 étaient les quatre diviseurs communs de 12 et 18.
Par conséquent, le plus grand d'entre eux est 6 :
PGCD (12, 18) = 6
Définition
En particulier, si le PGCD de deux entiers \(a\) et \(b\) est
égal à 1, on dit que \(a\) et \(b\) sont premiers entre eux.
Calculons le PGCD de 14 et 25.
On cherche tout d'abord les diviseurs de 14 : 1, 2, 7 et 14
... et ceux de 25 : 1, 5 et 25.
Or le seul diviseur commun à ces deux entiers est 1 :
PGCD(14 ; 25) = 1
Par conséquent, 14 et 25 sont premiers entre eux.
B) Méthode de calcul
La méthode de calcul du PGCD utilisée jusqu'à présent est juste, mais nécessite beaucoup de calculs : il faut en effet déterminer pour chaque nombre tous leurs diviseurs, puis regarder quels sont ceux qui sont communs. Nous allons voir deux méthodes plus rapides : celles par soustractions successives et l'algorithme d'Euclide.1) Méthode par soustractions successives
Définition
Lorsque \(c\) est un
diviseur commun de \(a\) et de \(b\), alors \(c\) est aussi un diviseur de \(a-b\) (théorème admis).
Par conséquent, lorsque \(a>b\), le PGCD de \(a\) et \(b\) est également le PGCD de \(a-b\) et de \(b\) :
\(PGCD(a,b) = PGCD(a-b,b)\)
Par conséquent, lorsque \(a>b\), le PGCD de \(a\) et \(b\) est également le PGCD de \(a-b\) et de \(b\) :
Cela nous donne une nouvelle méthode de calcul du PGCD.
Exemple 7 :
Calculons le PGCD de 68 et de 24 :
PGCD(68, 24) = PGCD(68 - 24, 24) = PGCD(44, 24)
PGCD(44, 24) = PGCD(44 - 24, 24) = PGCD(20, 24)
PGCD(20, 24) = PGCD(20, 24 - 20) = PGCD(20, 4)
PGCD(20, 4) = PGCD(20 - 4, 4) = PGCD(16, 4)
PGCD(16, 4) = PGCD(16 - 4, 4) = PGCD(12, 4)
PGCD(12, 4) = PGCD(12 - 4, 4) = PGCD(8, 4)
PGCD(8, 4) = PGCD(8 - 4, 4) = PGCD(4, 4)
PGCD(4, 4) = 4 (le plus grand diviseur commun à 4 et 4 est bien évidemment 4)
Le PGCD de 68 et 24 est égal à 4.
On peut également rédiger le calcul du PGCD de la façon suivante :
68 - 24 = 44
44 - 24 = 20
24 - 20 = 4
20 - 4 = 16
16 - 4 = 12
12 - 4 = 8
8 - 4 = 4
La première étape consiste à faire la différence entre les deux nombres dont on cherche le PGCD.
Ensuite, on effectue une succession de soustractions entre les deux nombres touchant le signe "=" de chaque équation, de sorte que le signe de cette différence soit positif.
On s'arrête lorsqu'on obtient deux nombres identiques de part et d'autres du signe "=". Dans l'exemple, il s'agit de 4 (en caractère gras). Par conséquent, le PGCD de 68 et 24 est égal à 4.
2) Méthode par l'algorithme d'Euclide
La méthode de l'algorithme
d'Euclide permet d'accélérer la méthode précédente.
Exemple 8 :
En reprenant l'exemple 7 du calcul du PGCD entre 68 et 24 :
68 = 24 × 2 + 20
24 = 20 × 1 + 4
20 = 4 × 5 + 0
Le PGCD est le dernier reste non nul, soit 4 (en caractère gras).
Par rapport à la méthode par soustractions successives, on gagne du temps : il n'y a en effet que 3 lignes de calcul au lieu de 7.
Les deux premières lignes de la méthode soustractive peuvent en effet être remplacées par une seule : 20 est le reste de la division euclidienne de 68 par 24.
Théorème
Si \(a=bq+r\), alors \(PGCD(a,b)=PGCD(b,r)\).
Exemple 8 :
En reprenant l'exemple 7 du calcul du PGCD entre 68 et 24 :
68 = 24 × 2 + 20
24 = 20 × 1 + 4
20 = 4 × 5 + 0
Le PGCD est le dernier reste non nul, soit 4 (en caractère gras).
Par rapport à la méthode par soustractions successives, on gagne du temps : il n'y a en effet que 3 lignes de calcul au lieu de 7.
Les deux premières lignes de la méthode soustractive peuvent en effet être remplacées par une seule : 20 est le reste de la division euclidienne de 68 par 24.
III) Cas pratiques
A) Simplification de fractions
Propriété
Une fraction est irréductible
lorsque son numérateur et son dénominateur sont premiers entre eux.
Autrement dit, tant que le PGCD du numérateur et du dénominateur n'est pas égal à 1, alors il est possible de simplifier la fraction.
Pour la simplifier au maximum, il suffit de diviser le numérateur et le dénominateur par leur PGCD.
Autrement dit, tant que le PGCD du numérateur et du dénominateur n'est pas égal à 1, alors il est possible de simplifier la fraction.
Pour la simplifier au maximum, il suffit de diviser le numérateur et le dénominateur par leur PGCD.
On souhaite rendre irréductible la fraction suivante :
\(\displaystyle \frac{156}{24}\)
Pour cela, on va calculer le PGCD du numérateur et du dénominateur, c'est-à-dire : PGCD(156,24).
156 = 24 × 6 + 12
24 = 12 × 2 + 0
Le PGCD de 156 et 24 est le dernier reste non nul, c'est-à-dire 12 (en caractère gras).
Pour rendre la fraction irréductible, on divise le numérateur et le dénominateur par 12 :
\(\displaystyle \frac{156}{24}=\frac{156\div 12}{24\div 12}=\frac{13}{2}\)
La fraction irréductible est \(\displaystyle \frac{13}{2}\).
B) Résolution de problèmes
Exemple 10 :Un fleuriste dispose de 256 roses blanches et de 192 roses rouges. Il souhaite faire le plus grand nombre de bouquets identiques en utilisant toutes les roses. Combien de bouquets pourra-t-il composer ? Combien de roses blanches et rouges contient chaque bouquet ?
Solution :
Soit N le nombre de bouquets.
N divise 256, car le fleuriste utilise toutes les roses blanches (sinon, il en aurait en trop).
N divise également 192, car le fleuriste utilise toutes les roses rouges.
Par conséquent, N est un diviseur commun de 192 et 256.
Comme le fleuriste souhaite effectuer le plus grand nombre de bouquets identiques, alors ce nombre est égal au plus grand diviseur commun de 192 et 256 :
N = PGCD(192,256)
Calcul du PGCD de 192 et 256 :
256 = 192 × 1 + 64
192 = 64 × 3 + 0
Le PGCD de 192 et 256 est le dernier reste non nul, c'est-à-dire 64 (en caractère gras).
Par conséquent, le fleuriste pourra au maximum composer 64 bouquets identiques en utilisant toutes les fleurs.
Nombre de roses blanches dans un bouquet :
\(\displaystyle \frac{256}{64}=4\)
Nombre de roses rouges dans un bouquet :
\(\displaystyle \frac{192}{64}=3\)
Chaque bouquet est composé de 4 roses blanches et de 3 roses rouges.