PGCD

Discussions générales concernant les mathématiques.
[ce forum est modéré par les modérateurs globaux du site]
Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Pour obtenir de l'aide sur un exercice ou un problème, consulter cette section. (ce forum est destiné aux discussions plutôt théoriques)

PGCD

Messagepar Matt » Dimanche 13 Novembre 2005, 12:24

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 ?
Matt
Hecto-utilisateur
 
Messages: 97
Inscription: Vendredi 28 Octobre 2005, 17:54

Publicité

Messagepar Ash'Ka » Dimanche 13 Novembre 2005, 12:38

C'est pas l'algorithme d'Euclide le plus puissant pour trouver le pgcd?
Experience the Brilliance
Ash'Ka
Hecto-utilisateur
 
Messages: 99
Inscription: Jeudi 15 Septembre 2005, 14:31
Localisation: Region Parisienne

Messagepar Matt » Dimanche 13 Novembre 2005, 14:18

Oui, vous avez raison! Pouvez vous me l'expliquer SVP ?
Matt
Hecto-utilisateur
 
Messages: 97
Inscription: Vendredi 28 Octobre 2005, 17:54

Messagepar Ash'Ka » Lundi 14 Novembre 2005, 00:05

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
Experience the Brilliance
Ash'Ka
Hecto-utilisateur
 
Messages: 99
Inscription: Jeudi 15 Septembre 2005, 14:31
Localisation: Region Parisienne

Messagepar matt pas connecté ! » Lundi 14 Novembre 2005, 19:02

merci ! :D
matt pas connecté !
 


Retourner vers Tribune des mathématiques

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 6 invités