L’algorithme d’Euclide 61
810
Al-Khwarizmi donne le nom
« algorithme » aujourd’hui
utilisé en mathématiques.
1202
Fibonacci publie un travail
sur les congruences dans
son Liber Abaci.
Dans les années 1970
Le théorème chinois est utilisé en
cryptographie.
défaut dans cette recette, c’est une boucle comme il en existe en informatique, c’est-à-dire un outil pour traiter la récursivité. Il faut espérer
qu’ il ne sera pas nécessaire de cuire la dinde plus d’une fois.
En mathématiques, il y a aussi des ingrédients : ce sont les nombres.
L’algorithme d’Euclide est conçu pour calculer le plus grand diviseur
commun (que l’on écrit pgcd). Le pgcd de deux entiers est le plus grand
nombre qui les divise l’un et l’autre. Comme exemple, nous choisirons
les deux nombres 18 et 84.
Le plus grand diviseur commun Le pgcd de notre exemple
est le plus grand nombre qui divise exactement 18 et 84. Le nombre 2
divise à la fois 18 et 84, mais 3 également. Par conséquent, 6 divise
aussi les deux nombres. Existe-t-il un nombre plus grand qui les divise
tous deux ? Nous pourrions essayer 9 ou 18. Après vérification, ils ne
sont pas des diviseurs de 84 et donc 6 est le plus grand nombre qui les
divise tous les deux. On peut conclure que 6 est le pgcd de 18 et 84, et
on l’écrit pgcd(18, 84) = 6.
Le pgcd peut être comparé à un carrelage de cuisine. Il correspond à la
taille du plus grand carreau qui permettra de recouvrir un mur rectangulaire de 18 unités de largeur et de 84 unités de longueur, sachant qu’il
est interdit de couper les carreaux utilisés. Dans cet exemple, il est clair
qu’un carreau de 6 × 6 fera l’affaire.
Le plus grand diviseur commun est parfois appelé le
« plus grand facteur commun ». Il est également lié
à un concept voisin, celui de « plus petit multiple
commun » (ppcm). Le ppcm de 18 et 84 est le plus
petit nombre divisible par 18 et 84. Ce lien entre le
ppcm et le pgcd est mis en évidence lorsque l’on multiplie le ppcm de deux nombres positifs par leur pgcd :
le résultat obtenu est égal à celui du produit des deux
nombres eux-mêmes. Ici, ppcm(18, 84) = 252, et on
peut vérifier que 6 × 252 = 1 512 = 18 × 84.
Géométriquement, le ppcm correspond à la taille
du côté du plus petit carré qui peut être carrelé au
moyen de carreaux rectangulaires de 18 × 84. Étant
donné que ppcm(a,b) = ab/ pgcd(a,b), nous allons
rechercher le pgcd. On a déjà calculé pgcd(18, 84) = 6, mais pour cela, il
nous a fallu connaître les diviseurs communs de 18 et de 84. En résumé,
Carrelage d’un carré
avec des rectangles
de 18 × 84
84
252
252
84
18
18
810
Al-Khwarizmi donne le nom
« algorithme » aujourd’hui
utilisé en mathématiques.
1202
Fibonacci publie un travail
sur les congruences dans
son Liber Abaci.
Dans les années 1970
Le théorème chinois est utilisé en
cryptographie.
défaut dans cette recette, c’est une boucle comme il en existe en informatique, c’est-à-dire un outil pour traiter la récursivité. Il faut espérer
qu’ il ne sera pas nécessaire de cuire la dinde plus d’une fois.
En mathématiques, il y a aussi des ingrédients : ce sont les nombres.
L’algorithme d’Euclide est conçu pour calculer le plus grand diviseur
commun (que l’on écrit pgcd). Le pgcd de deux entiers est le plus grand
nombre qui les divise l’un et l’autre. Comme exemple, nous choisirons
les deux nombres 18 et 84.
Le plus grand diviseur commun Le pgcd de notre exemple
est le plus grand nombre qui divise exactement 18 et 84. Le nombre 2
divise à la fois 18 et 84, mais 3 également. Par conséquent, 6 divise
aussi les deux nombres. Existe-t-il un nombre plus grand qui les divise
tous deux ? Nous pourrions essayer 9 ou 18. Après vérification, ils ne
sont pas des diviseurs de 84 et donc 6 est le plus grand nombre qui les
divise tous les deux. On peut conclure que 6 est le pgcd de 18 et 84, et
on l’écrit pgcd(18, 84) = 6.
Le pgcd peut être comparé à un carrelage de cuisine. Il correspond à la
taille du plus grand carreau qui permettra de recouvrir un mur rectangulaire de 18 unités de largeur et de 84 unités de longueur, sachant qu’il
est interdit de couper les carreaux utilisés. Dans cet exemple, il est clair
qu’un carreau de 6 × 6 fera l’affaire.
Le plus grand diviseur commun est parfois appelé le
« plus grand facteur commun ». Il est également lié
à un concept voisin, celui de « plus petit multiple
commun » (ppcm). Le ppcm de 18 et 84 est le plus
petit nombre divisible par 18 et 84. Ce lien entre le
ppcm et le pgcd est mis en évidence lorsque l’on multiplie le ppcm de deux nombres positifs par leur pgcd :
le résultat obtenu est égal à celui du produit des deux
nombres eux-mêmes. Ici, ppcm(18, 84) = 252, et on
peut vérifier que 6 × 252 = 1 512 = 18 × 84.
Géométriquement, le ppcm correspond à la taille
du côté du plus petit carré qui peut être carrelé au
moyen de carreaux rectangulaires de 18 × 84. Étant
donné que ppcm(a,b) = ab/ pgcd(a,b), nous allons
rechercher le pgcd. On a déjà calculé pgcd(18, 84) = 6, mais pour cela, il
nous a fallu connaître les diviseurs communs de 18 et de 84. En résumé,
Carrelage d’un carré
avec des rectangles
de 18 × 84
84
252
252
84
18
18