Algorithme d´Euclide

tout le monde me dit ça
mais je connais pas !

a, b E IN

a = bq + r / q E Z et 0(=)< r < b

PGCD(a,b) = PGCD(b,r)

Ainsi de suite, jusqu´au dernier reste non nul

T´es en quelle classe?

3ème collège
heu pardon j´ai rien compris

Normal, c´est du programme de spécialité maths de Terminale S...

En gros tu divises par les restes jusqu´au dernier reste non nul, c´est ton PGCD

Exemple: On cherche le PGCD(46;16)

46 divisé par 16 c´est 2 et il reste 14
16 divisé par 14 c´est 1 et il reste 02
14 divisé par 02 c´est 7 et il reste 00

Ton PGCD c´est 2
En même temps c´est un exemple pourri car les deux nombres sont pairs

*

* Skayah profil
* Posté le 26 novembre 2007 à 21:01:06 avertir modérateur
* Normal, c´est du programme de spécialité maths de Terminale S...

Euh on l´apprend aussi au collège. J´m´en souviens, c´était même au brevet. Mais ce n´est pas expliqué de façon littérale...

+1
Oui oui, je m´en rappelle aussi, mais on ne nous expliquait pas avec les a/b et le reste r etc..
C´était juste une méthode à appliquer bêtement

comme t´as dit, ici les nombres sont pairs, par contre lorsque t´as par exemple 126; 90 ?

Exactement.

126 et 90 sont pairs aussi

peu importe, 7; 8 par exsemple

PGCD ( 2250, 630 ) = 125
Correcte ?

L´algorithme d´Euclide est bien lorsque ça se termine en 2 trois lignes, sinon vaut mieux utiliser la décomposition en facteurs
premiers

utilise l´algorithme des différences

plus grand nombre - plus petit nombre = résultat

2ème plus grand - plus petit = 2ème résultat

ainsi de suite jusqu´à trouver le PGCD

Le truc que tu peux faire c´est de décomposé en facteur premier et je comparé...tu prends le plus petit...