PGCD

Discussions générales concernant les mathématiques.
[participation réservée aux membres inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
Matt

PGCD

Message non lu 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 ?
Ash'Ka

Message non lu par Ash'Ka »

C'est pas l'algorithme d'Euclide le plus puissant pour trouver le pgcd?
Matt

Message non lu par Matt »

Oui, vous avez raison! Pouvez vous me l'expliquer SVP ?
Ash'Ka

Message non lu 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
matt pas connecté !

Message non lu par matt pas connecté ! »

merci ! :D