PGCD de 2 nombres
Un fleuriste a reçu une commande de 126 iris et 210 roses. Il utilise toutes ses fleurs pour réaliser des bouquets contenant le même nombre d'iris et de roses. Il peut par exemple réaliser 21 bouquets de 6 iris et 10 roses.
Question
Quel est le plus grand nombre possible de bouquets qu'il peut réaliser. Donner la composition de chaque bouquet.
Indice
Le nombre d'iris dans un bouquet divise le nombre d'iris total et de même pour les roses.
Solution
On cherche le plus grand diviseur commun entre 126 et 210.
Méthode : Trouver les diviseurs d'un nombre : astuce 1
Pour trouver tous les diviseurs d'un nombre, un algorithme naïf consiste à les tester tous du plus petit au plus grand.
Néanmoins on peut l'améliorer significativement en faisant la remarque suivante : si \(n=a\times b\), alors un des diviseurs de \(n\) est inférieur à \(\sqrt n\) tandis que l'autre est supérieur à \(\sqrt n\). Si \(a \leqslant \sqrt n\) divise \(n\), alors \(b = \dfrac n a \geqslant \sqrt n\) est son diviseur associé.
Par conséquent, pour être certain d'avoir tous les diviseurs de \(n\), il suffit de tester les candidats jusqu'à \(\sqrt n\).
Méthode : Trouver les diviseurs d'un nombre : astuce 2
Une autre remarque permettant de gagner du temps est que si un nombre ne divise pas \(n\), aucun de ses multiples ne peut être un diviseur de \(n\).
En pratique, dès qu'on tombe sur un nombre qui n'est pas un diviseur, on élimine tous ses multiples de la liste des nombres à tester !
Simulation : Exemple pour 126
\sqrt {126} \approx 11,22 donc on teste les entiers de 1 à 11 :
1 divise 126 ==> l={1, 126}
2 divise 126 ==> {1, 2, 63 126}
3 divise 126 ==> {1, 2, 3, 42, 63 126}
4 ne divise pas 126 ==> on élimine 8
5 ne divise pas 126 ==> on élimine 10
6 divise 126 ==> {1, 2, 3, 6, 21, 42, 63 126}
7 divise 126 ==> {1, 2, 3, 6, 7, 18, 21, 42, 63 126}
8 éliminé
9 divise 126 ==> {1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63 126}
10 éliminé
11 ne divise pas 126 et on s'arrête.
Complément :
Il ne nous a suffi que 6 étapes pour lister tous les diviseurs de 126 au lieu de tester naïvement 126 candidats.
Solution
Les diviseurs de 126 sont : 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, 126
Les diviseurs de 210 sont : 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210
Le plus grand diviseur commun entre 126 et 210 est 42.
On note \(PGCD(126, 210) = 42\)
On peut donc faire 42 bouquets au maximum. Chaque bouquet contiendra alors 3 iris et 5 roses.
Question
Donner toutes les compositions florales possibles. Que peut-on dire de chacune de ces compositions par rapport au nombre de bouquets ?
Indice
Rappel : Le nombre de bouquets est un diviseur du nombre d'iris et de roses.
Chaque composition florale correspond à un diviseur commun entre 126 et 210.
Solution
Mettons en évidence les diviseurs communs de 126 et 210 :
Les diviseurs de 126 sont : 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, 126
Les diviseurs de 210 sont : 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210
Si p désigne le nombre de bouquets, voici toutes les compositions possibles :
p=1 donne 126 iris et 210 roses
p=2 donne 63 iris et 105 roses
p=3 donne 42 iris et 70 roses
p=6 donne 21 iris et 35 roses
p=7 donne 18 iris et 30 roses
p=14 donne 9 iris et 15 roses
p=21 donne 6 iris et 10 roses
p=42 donne 3 iris et 5 roses
Remarque :
On remarque que le nombre de bouquets pour toutes les compositions possibles est en fait un diviseur de 42. La liste des diviseurs de 42 donne toutes les compositions possibles.
Conclusion
C'est donc ici le nombre 42 qui est la réponse à toutes les questions dans cet exercice. Le PGCD de 2 nombres est donc une opération extrêmement utile en arithmétique.