L'algorithme des soutractions successives et d'Euclide.

[Lola]

Bonjour,

J'étudie en classe le PGCD, mais ma professeur de maths m'a donné un devoir maison à faire sur l'algorithme par soustractions successives et l'algorithme d'Euclide.

Elle nous a donné un exemple :
Calcule du PGCD de 117 et 91 (par l'algorithme des soutractions successives).
117-91=26
91-26=65
65-26=39
39-26=13
26-13=13
Or PGCD de 13 et de 13 est 13 alors le PGCD (117;91) = 13

J'ai compris comment on faisait, mais je n'ai pas compris ce passage de la phrase : Or PGCD de 13 et de 13 est 13

Je dois alors calculer le PGCD de 90 et 75. J'ai fais cela :
90-75 =15
75-15=60
60-15=45
45-15=30
30-15=15
Mais je ne comprend toujours pas la phrase reponse ! Est-ce que je dois mettre : Or PGCD de 15 et de 15 est 15 ?
Merci d'avance pour votre réponse !

D'autre part, elle nous a aussi donné un exemple pour calculerle PGCD par l'algorithme d'Euclide. Le voici :
Calcul du PGCD d 117 et 91 (par l'algorithme d'Euclide).
117=91x1+26
91=26x3+13
26=13x2+0
Le PGCD de 26 et 13 est 13 alors PGCD (117;91)=13

Comme pour le précédent, j'ai compris les calculs et le résultat, mais toujours pas la phrase qui dit : Le PGCD de 26 et 13 est 13

Ici, je dois calculer le PGCD de 90 et 75. Voilà mon exercice :
90=75x1+15
75=15x5+0

Sachant qu'il faut mettre la meme phrase réponse que la prof, je ne sais pas comment faire car je ne comprend pas. Les calculs, les résultats et la façon de faire, je comprend très bien, mais le début de la phrase réponse non. Pourriez-vous m'expliquer ce que veut dire ce que je ne comprend pas, et m'aider à l'appliquer sur les 2 exercices ?
Merci beaucoup, bonne soirée.
Lola.

[SoS-Math(7)]

Bonsoir Lola,

Pour comprendre la phrase réponse de ton professeur, il faut revenir à la propriété :

a et b étant deux nombres entiers strictement positifs tels que a>b alors PGCD(a,b)=PGCD(b, a-b)

Ce qui signifie que le PGCD de deux nombres est le PGCD du plus petit des deux nombres et de la différence des deux nombres. Lors de l'algorithme, tu appliques cette propriété à chaque ligne de raisonnement.

117-91=26 Donc d=PGCD(117 ; 91)=PGCD(91 ; 26)
91-26=65 Donc d=PGCD(26 ; 65)
65-26=39 Donc d=PGCD(26 ; 39)
39-26=13 Donc d=PGCD(26 ; 13)
26-13=13 Donc d=PGCD(13 ; 13) je pense que tu comprends bien que le pgcd(13;13)=13 ce qui explique la conclusion...
Or PGCD de 13 et de 13 est 13 alors le PGCD (117;91) = 13

Pour l'algorithme d'Euclide, c'est la même chose, tout vient de la propriété suivante :

a et b étant deux nombres entiers strictement positifs tels que a>b alors PGCD(a,b)=PGCD(b, r) où r est le reste de la division euclidienne de a par b

Ce qui signifie que le PGCD de deux nombres est le PGCD du plus petit des deux nombres et du reste de la division euclidienne des deux nombres. Là encore, lors de l'algorithme, tu appliques cette propriété à chaque ligne de raisonnement.

117=91x1+26 Donc d=PGCD(117 ; 91)=PGCD(91 ; 26)
91=26x3+13 Donc d=PGCD(26 ; 13) La conclusion de ton professeur peut s'écrire à ce niveau.
26=13x2+0 Donc d=PGCD(13 ; 0) je pense que tu sais que tous les nombres divisent 0, donc le plus grand diviseur commun à 13 et à 0 est 13 d'où PGCD(117;91)=13

J'espère que mon explication éclairera ta recherche.
A bientôt sur SOS Math

[Lola]

Bonjour,

Tout d'abord, merci pour votre rapidité !
Je crois que j'ai enfin compris !

J'ai une derniere question !
Il faut calculer le PGCD de 1024 et 264 par l'algorithme des soustractions successives, puis par l'algorithme d'Euclide.
J'ai donc fais cela :
1024-264=760
760-264=496
496-264=232
264-232=32
232-32=200
200-32=168
168-32=136
136-32=104
104-32=72
72-32=40
40-32=8
32-8=24
24-8=16
16-8=8
J'ai trouvé que le PGCD (1024;264)=8

Et par l'algorithme d'Euclide :
1024=264x1+760
760=264x2+232
264=232x1+32
232=32x7+8
32=8x4+0.
Le dernier reste non nul est 8, odnc PGCD (104;264)=8.
Jusque là, tout va bien ! Mais la consigne est de comparer les deux méthodes de calcul du PGCD de 1024 et 264.
Dois-je comparer les resultats avec les calculs ?

Merci beaucoup, bonne journée.

[SoS-Math(1)]

Bonjour Lola,
Il faut comparer les résultats: heureusement que l'on trouve le même.
Mais il faut aussi comparer les étapes.
Par exemple,
760=264x2+232
pour l'algorithme d'Euclide et
760-264=496
496-264=232
pour l'algorithme des soustractions.
Il semblerait que l'on retrouve les étapes de l'algorithme d'Euclide dans l'algorithme des soustractions.
Bon courage.

[Lola]

Bonsoir,

Merci pour vos réponses.
Je n'hésiterai pas à revenir sur ce forum si j'en ai besoin.

Je partagerai ma note avec vous ;)

Bonne soirée.
Lola

[SoS-Math(1)]

Bonjour Lola,
à bientôt donc.
SoS-Math.

[Lola]

Bonsoir,
Me revoilà déjà ! Rassurez-vous, c'est n'est pas quelque chose que je n'ai pas compris !

J'ai la fraction suivante :
391/493
Il faut calculer le PGCD.

J'ai donc fais ceci:
493=391x1+102
391=102x3+85
102=85x1+17
85=17x5+0
Le PGCD est donc 17.

Il faut rendre la fraction irréductible, j'ai donc divisé le numérateur et le dénominateur par leur PGCD :
391:17 = 23
493:17=29
J'ai précisé que j'avais divisé par leur PGCD. Pensez-vous que c'est suffisant ou dois-je expliquer pourquoi j'ai divisé par leur PGCD ?
Merci, bonne soirée.
Lola.

[SoS-Math(1)]

Bonjour Lola,
Cela me semble suffisant.
A bientôt.

[Lola]

Bonsoir,
Merci beaucoup.

Bonne continuation, bonne soirée.
Lola.

[SoS-Math(7)]

A bientôt Lola sur SOS Math