L’algorithme d’Euclide 63
Paul sait qu’il existe une solution en nombres entiers à l’équation 18x + 84y = c si et
seulement si le pgcd 6 est un diviseur du nombre c. Il ne l’est pas pour c = 652 mais il
l’est pour 642. Paul n’a même pas besoin de savoir combien de valises x, y des deux
poids indiqués Marie-Chantal a l’intention d’emmener à la Barbade.
Le théorème chinois Lorsque le pgcd de deux nombres est égal à 1, on dit
que ces nombres sont « premiers entre eux ». Ils n’ont pas besoin d’être premiers
eux-mêmes mais ils doivent l’être l’un pour l’autre. Par exemple, pgcd(6, 35) = 1,
même si 6 et 35 ne sont ni l’un ni l’autre des nombres premiers. Nous aurons besoin
de cette définition pour le théorème chinois.
Examinons un autre problème : André ne sait pas combien il possède de bouteilles
de vin, mais, lorsqu’il les range par deux, il en reste 1. Lorsqu’il les dispose en rangées de cinq dans son casier à bouteilles, il en reste 3. Combien de bouteilles a-t-il ?
On sait que la division par 2 donne un reste de 1 et que la division par 5 donne un
reste de 3. La première condition nous permet d’éliminer tous les nombres pairs. En
examinant les nombres impairs, on trouve rapidement que 13 fait l’affaire (on peut
dire sans risque d’erreur qu’André a plus de trois bouteilles, nombre qui satisfait
lui aussi les conditions). Mais d’autres nombres conviendraient aussi, à savoir tous
ceux qui appartiennent en fait à une suite complète qui commence ainsi : 13, 23,
33, 43, 53, 63, 73, 83…
Ajoutons maintenant une autre condition. Le nombre recherché doit donner un
reste de 3 lorsqu’on le divise par 7 (les bouteilles sont arrivées par caisses de 7 et
il y en avait 3 de plus). Si l’on parcourt la suite 13, 23, 33, 43, 53, 63… pour tenir
compte de ce détail, on trouve que le nombre 73 fait l’affaire, mais on note que 143
aussi, tout comme 213 et tout nombre qui s’obtient en additionnant les multiples
de 70 à ces nombres.
En termes mathématiques, nous avons trouvé les solutions garanties par le théorème des restes chinois, qui dit aussi que deux solutions quelconques diffèrent d’un
multiple de 2 × 5 × 7 = 70. Si André a entre 150 et 250 bouteilles, alors le théorème établit la solution à 213 bouteilles. Pas mal pour un théorème découvert au
iii
e siècle !
l’idée clé
en route vers le plus grand
Paul sait qu’il existe une solution en nombres entiers à l’équation 18x + 84y = c si et
seulement si le pgcd 6 est un diviseur du nombre c. Il ne l’est pas pour c = 652 mais il
l’est pour 642. Paul n’a même pas besoin de savoir combien de valises x, y des deux
poids indiqués Marie-Chantal a l’intention d’emmener à la Barbade.
Le théorème chinois Lorsque le pgcd de deux nombres est égal à 1, on dit
que ces nombres sont « premiers entre eux ». Ils n’ont pas besoin d’être premiers
eux-mêmes mais ils doivent l’être l’un pour l’autre. Par exemple, pgcd(6, 35) = 1,
même si 6 et 35 ne sont ni l’un ni l’autre des nombres premiers. Nous aurons besoin
de cette définition pour le théorème chinois.
Examinons un autre problème : André ne sait pas combien il possède de bouteilles
de vin, mais, lorsqu’il les range par deux, il en reste 1. Lorsqu’il les dispose en rangées de cinq dans son casier à bouteilles, il en reste 3. Combien de bouteilles a-t-il ?
On sait que la division par 2 donne un reste de 1 et que la division par 5 donne un
reste de 3. La première condition nous permet d’éliminer tous les nombres pairs. En
examinant les nombres impairs, on trouve rapidement que 13 fait l’affaire (on peut
dire sans risque d’erreur qu’André a plus de trois bouteilles, nombre qui satisfait
lui aussi les conditions). Mais d’autres nombres conviendraient aussi, à savoir tous
ceux qui appartiennent en fait à une suite complète qui commence ainsi : 13, 23,
33, 43, 53, 63, 73, 83…
Ajoutons maintenant une autre condition. Le nombre recherché doit donner un
reste de 3 lorsqu’on le divise par 7 (les bouteilles sont arrivées par caisses de 7 et
il y en avait 3 de plus). Si l’on parcourt la suite 13, 23, 33, 43, 53, 63… pour tenir
compte de ce détail, on trouve que le nombre 73 fait l’affaire, mais on note que 143
aussi, tout comme 213 et tout nombre qui s’obtient en additionnant les multiples
de 70 à ces nombres.
En termes mathématiques, nous avons trouvé les solutions garanties par le théorème des restes chinois, qui dit aussi que deux solutions quelconques diffèrent d’un
multiple de 2 × 5 × 7 = 70. Si André a entre 150 et 250 bouteilles, alors le théorème établit la solution à 213 bouteilles. Pas mal pour un théorème découvert au
iii
e siècle !
l’idée clé
en route vers le plus grand