Euclide

[Luna]

Bonjour sos maths, je suis un train de faire un exercice de maths et je suis bloquer à des questions et je ne vois pas trop comment faire pouvez vous m’aidez s’il vous plaît ?
Alors il y a une question qui est d’expliquer simplement l’algorithme et j’ai commencer par mettre :
Le but est de trouver le PGCD de à et b nommé g
On part de 1 car le plus petit PGCD possible est 1
Sauf que je ne vois pas comment je peux expliquer le reste.

Pour une aitres question on me demande de montre pourquoi ça ne marche pas pour 0 et 5 :
Moi j’aurais dit car 0 n’est pas divisible mais je sais pas trop comment faire .

Et une après question qui est de proposer une modification pour pallier cette erreur
Sauf que je ne vois pas trop
Merci
Luna

[SoS-Math(33)]

Bonsoir Luna,
dans ton algorithme d est le diviseur et g le PGCD.
Au départ g = 1 et d = 2
A chaque étape le programme teste si d divise a, si oui il va tester si d divise aussi b, si oui alors d est un diviseur commun de a et b dans ce cas g=d
Si d n'est pas un diviseur de a ou de b il passe au nombre suivant ( d+1 ) et il recommence.
Si d divise à la fois a et b alors on regarde si est aussi un diviseur de (a:d) et de (b:d) et ainsi de suite.

Si tu prends par exemple 12 et 6 ; 2 divise 12 et 6 donc g passe à 2
ensuite on teste sur 6 et 3 mais 2 ne divise pas 3 donc on passe à 3
3 divise 6 et 3 donc g passe à 2x3=6
ensuite on teste sur 2 et 1 mais 3 est plus grand que 2 donc le programme s’arrête et donne g = 6 soit PGCD(12;6)=6
Comprends tu un peu mieux l'algorithme?

[Luna]

A d’accord oui, il comprend mieux l’algorithme, cependant je ne vois pas pourquoi il ne fonctionnerais pas avec 0 et 5 ?

[SoS-Math(33)]

A l'initialisation d=2 et dès le premier test 2>0 donc l'algorithme donne directement g=1
Or le PGCD de 0 et 5 n'existe pas donc l'algorithme ne marche pas ( il ne donne pas le bon résultat). Je pense que c'est comme ça qu'il faut comprendre la question.

[Luna]

Daccord merci beaucoup

[SoS-Math(33)]

Bonne soirée
A bientôt sur le forum
SoS-math