Page 1 sur 1

PGCD

MessagePosté: Dimanche 13 Novembre 2005, 12:24
par Matt
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 ?

MessagePosté: Dimanche 13 Novembre 2005, 12:38
par Ash'Ka
C'est pas l'algorithme d'Euclide le plus puissant pour trouver le pgcd?

MessagePosté: Dimanche 13 Novembre 2005, 14:18
par Matt
Oui, vous avez raison! Pouvez vous me l'expliquer SVP ?

MessagePosté: Lundi 14 Novembre 2005, 00:05
par 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

MessagePosté: Lundi 14 Novembre 2005, 19:02
par matt pas connecté !
merci ! :D