50 clés pour comprendre les maths
62
nous avons d’abord décomposé les deux nombres en produit de facteurs premiers : 18 = 2 × 3 × 3 et 84 = 2 × 2 × 3 × 7. Nous avons ensuite observé que le
nombre 2 leur est commun et qu’il est aussi la plus grande puissance de 2 qui
les divise l’un et l’autre. En revanche, si 7 divise 84, il ne divise pourtant pas 18
et ne peut donc pas figurer dans la liste des facteurs premiers du pgcd. Nous en
avons conclu que 2 × 3 = 6 est le plus grand nombre qui les divise tous les deux.
Peut-on se dispenser de jongler ainsi avec les facteurs ? Imaginez les calculs si
nous voulions trouver pgcd(17 640, 54 054). Il faudrait commencer par factoriser
les deux nombres, et ce ne serait que le début. Il doit bien exister une méthode
plus simple !
L’algorithme Il y a mieux en effet. L’algorithme d’Euclide apparaît dans les
Éléments, Livre 7, Proposition 2 : « Étant donnés deux entiers positifs non premiers
entre eux, trouver leur plus grand commun diviseur. »
L’algorithme d’Euclide est d’une efficacité admirable et remplace avantageusement
toute cette recherche laborieuse de facteurs par une simple soustraction. Voyons
comment ça marche.
Il s’agit de calculer d = pgcd(18, 84). On divise d’abord 84 par 18. La division ne
tombe pas juste mais il y va 4 fois et il reste 12 :
84 = (4 × 18) + 12.
Comme d doit être à la fois diviseur de 84 et de 18, il doit diviser le reste, à savoir
12. Par conséquent, d = pgcd(12, 18). On peut répéter le processus et diviser 18
par 12 :
18 = (1 × 12) + 6.
Il reste alors 6, et donc d = pgcd(6, 12). En divisant 12 par 6, on a un reste de 0 de
sorte que d = pgcd(0, 6). 6 est le plus grand nombre qui divise à la fois 0 et 6, et c’est
donc la réponse à notre problème.
Si on calcule d = pgcd(17 640, 54 054), on a successivement 1 134, 630, 504, 126 et
0 pour restes, ce qui nous donne d = 126.
Utilisations du pgcd Le pgcd peut être utilisé dans la solution d’équations
lorsque les solutions doivent nécessairement être des nombres entiers. On les
appelle les équations diophantiennes, d’après le nom de l’ancien mathématicien
grec Diophante d’Alexandrie.
Imaginons Marie-Chantal qui part comme chaque année passer ses vacances à la
Barbade. Elle envoie Pierre, son majordome, à l’aéroport pour emmener toutes ses
valises, qui pèsent chacune ou bien 18 kg ou bien 84 kg. Il lui fait savoir que le
poids total à l’enregistrement était de 652 kg. Lorsqu’il revient à Monaco, Paul, le
fils de Pierre, âgé de 9 ans, s’écrie soudain : « Ce n’est pas possible parce que le pgcd
6 n’est pas un diviseur de 652. » Paul laisse entendre qu’en réalité, le poids total
serait plutôt de 642 kg.
62
nous avons d’abord décomposé les deux nombres en produit de facteurs premiers : 18 = 2 × 3 × 3 et 84 = 2 × 2 × 3 × 7. Nous avons ensuite observé que le
nombre 2 leur est commun et qu’il est aussi la plus grande puissance de 2 qui
les divise l’un et l’autre. En revanche, si 7 divise 84, il ne divise pourtant pas 18
et ne peut donc pas figurer dans la liste des facteurs premiers du pgcd. Nous en
avons conclu que 2 × 3 = 6 est le plus grand nombre qui les divise tous les deux.
Peut-on se dispenser de jongler ainsi avec les facteurs ? Imaginez les calculs si
nous voulions trouver pgcd(17 640, 54 054). Il faudrait commencer par factoriser
les deux nombres, et ce ne serait que le début. Il doit bien exister une méthode
plus simple !
L’algorithme Il y a mieux en effet. L’algorithme d’Euclide apparaît dans les
Éléments, Livre 7, Proposition 2 : « Étant donnés deux entiers positifs non premiers
entre eux, trouver leur plus grand commun diviseur. »
L’algorithme d’Euclide est d’une efficacité admirable et remplace avantageusement
toute cette recherche laborieuse de facteurs par une simple soustraction. Voyons
comment ça marche.
Il s’agit de calculer d = pgcd(18, 84). On divise d’abord 84 par 18. La division ne
tombe pas juste mais il y va 4 fois et il reste 12 :
84 = (4 × 18) + 12.
Comme d doit être à la fois diviseur de 84 et de 18, il doit diviser le reste, à savoir
12. Par conséquent, d = pgcd(12, 18). On peut répéter le processus et diviser 18
par 12 :
18 = (1 × 12) + 6.
Il reste alors 6, et donc d = pgcd(6, 12). En divisant 12 par 6, on a un reste de 0 de
sorte que d = pgcd(0, 6). 6 est le plus grand nombre qui divise à la fois 0 et 6, et c’est
donc la réponse à notre problème.
Si on calcule d = pgcd(17 640, 54 054), on a successivement 1 134, 630, 504, 126 et
0 pour restes, ce qui nous donne d = 126.
Utilisations du pgcd Le pgcd peut être utilisé dans la solution d’équations
lorsque les solutions doivent nécessairement être des nombres entiers. On les
appelle les équations diophantiennes, d’après le nom de l’ancien mathématicien
grec Diophante d’Alexandrie.
Imaginons Marie-Chantal qui part comme chaque année passer ses vacances à la
Barbade. Elle envoie Pierre, son majordome, à l’aéroport pour emmener toutes ses
valises, qui pèsent chacune ou bien 18 kg ou bien 84 kg. Il lui fait savoir que le
poids total à l’enregistrement était de 652 kg. Lorsqu’il revient à Monaco, Paul, le
fils de Pierre, âgé de 9 ans, s’écrie soudain : « Ce n’est pas possible parce que le pgcd
6 n’est pas un diviseur de 652. » Paul laisse entendre qu’en réalité, le poids total
serait plutôt de 642 kg.