Salut à tous ! Voila, j'ai lu la discussion du Pgcd où Nightmare apparait (voir message PGCD) et je me demandais comment fonctionnait l'algorithme de Erastothène ?
Connaissez vous d'autres techniques pour trouver le PGCD ?
Merci pour vos éventuelles réponses :D
[edit Nirosis] Pourquoi écrire en police 18 et en rouge ?
PGCD
-
Ash'Ka
Bah l'algorithme d'euclide repose sur le fait que :
Soit $a,b\in\Z$ ($a|b = a$ divise $b$)
Si $d|a$ et $d|b$ alors pour tout $n,m \in Z,d|na + mb$
On sait qu'il existe un unique coupe $(q,r)\in\N^2$ avec $r < b$ tel que
$a = qb + r$
Soit $d$ un diviseur de $a$ et $b$
alors $d$ divise r
Mais puisque $d|r$ et $d|b$
et qu'il existe un unique couple $(q_1,r_1)$ avec $r_1 < r$ tel que
$b = q_1r + r_1$
alors $d|r_1$ et on itère jusqu'à ce que le reste soit nul.
Puis par récurrence fini, on montre ainsi que pgcd(a,b) = dernier reste non nul
exemple :
prenons 12 et 15
15 = 12 + 3
12 = 4*3 + 0
le dernier reste non nul est 3 donc pgcd(12,15) = 3
Prenons 125 et 14
125 = 14*9 - 1
donc pgcd(125,14) = 1
121 et 132
132 = 121 + 11
121 = 11*11 + 0
donc pgcd(121,132) = 11
Soit $a,b\in\Z$ ($a|b = a$ divise $b$)
Si $d|a$ et $d|b$ alors pour tout $n,m \in Z,d|na + mb$
On sait qu'il existe un unique coupe $(q,r)\in\N^2$ avec $r < b$ tel que
$a = qb + r$
Soit $d$ un diviseur de $a$ et $b$
alors $d$ divise r
Mais puisque $d|r$ et $d|b$
et qu'il existe un unique couple $(q_1,r_1)$ avec $r_1 < r$ tel que
$b = q_1r + r_1$
alors $d|r_1$ et on itère jusqu'à ce que le reste soit nul.
Puis par récurrence fini, on montre ainsi que pgcd(a,b) = dernier reste non nul
exemple :
prenons 12 et 15
15 = 12 + 3
12 = 4*3 + 0
le dernier reste non nul est 3 donc pgcd(12,15) = 3
Prenons 125 et 14
125 = 14*9 - 1
donc pgcd(125,14) = 1
121 et 132
132 = 121 + 11
121 = 11*11 + 0
donc pgcd(121,132) = 11