Algorithme 1 : L'Algorithme d'EUCLIDE
$a$ et $b$ étant des entiers naturels non nuls.
On sait qu'il existe des entiers naturels $q$ et $r$ tels que $a = b q + r$ où $0 \leq r < b$
L'on a ainsi effectué la division euclidienne de $a$ par $b$.
$q$ s'appelle le quotient de la division euclidienne. Dans le tableur Excel, $q$ s'obtient par $ent(a,b)$ $r$ s'appelle le reste de la division euclidienne. Dans le tableur Excel, $r$ s'obtient par $mod(a,b)$
Le PGCD de deux nombres est le dernier reste non nul de la succession de divisions que l'on effectue dans l'algorithme d'Euclide.
Voici une feuille de calcul Excel réalisant cet algorithme :
Voici les formules utilisées dans cette feuille :
Algorithme 2 : L'algorithme de la différence
Il est basé sur la propriété suivante :
Soient $a$ et $b$ des entiers naturels non nuls avec $a > b$. Alors le PGCD de $a$ et de $b$ est égal au PGCD de $b$ et de $a - b$
|
d = pgcd(810 ; 450) |
810 - 450 = 360 |
|
d = pgcd(450 ; 360) |
450 - 360 = 90 |
|
d = pgcd(360 ; 90 ) |
360 - 90 = 270 |
|
d = pgcd(90 ; 270) = pgcd(270 ; 90) |
270 - 90 = 180 |
|
d = pgcd(90 ; 180) = pgcd(180 ; 90) |
180 - 90 = 90 |
|
d = pgcd(90 ; 90) |
90 - 90 = 0 |
|
le pgcd est donc 90 |
|
La feuille de calcul suivante utilise cet algorithme :
Voici les formules utilisées dans cette feuille :
On peut améliorer cette feuille en remarquant que dès que b est égal à 1 alors le pgcd est a
Auteur : Christian CYRILLE Groupe IREM Kabrit Bwa