Bonjour !
Besoin d'un petit peu d'aide. Je suis en terminale S, et j'ai un exo sur le PGCD (maths spé), je n'arrive pas à m'en sortir.
Je vous le met ici :
Soit a et b deux entiers naturels tels que 0<b<a. On considère l'algorithme suivant :
ENTRÉE : Saisir a, saisir b
TRAITEMENT : Tantque b ne divise pas a faire :
c reçoit max(b,a-b)
b reçoit min(b;a-b)
a reçoit c
Fin Tantque
SORTIE : Afficher b
Question : Justifier que cet algorithme s'arrête et qu'il affiche le PGCD de a et b.
Pour l'instant la seule chose que j'ai remarqué c'est que cela ressemble à la détermination du PGCD en faisant des soustractions successives (j'ai trouvé cela ici : http://mathematiques3.free.fr/2troisieme/arithmetique/arit010.php )Le problème c'est que quand on utilise cette méthode on prend le dernier résultat différent de 0 or ici on cherche jusqu'à ce que b divise a.
Quelqu'un pourrait m'aider ?
Merci beaucoup!
Bonjour,
Si b divise a, quel est le PGCD de a et b ?
Essaye avec 432 et 240, en faisant les soustraction.
Si tu le fais à la main , tu vas arriver à 144 et 48, sans voir que 48 divise 144.
Tu vas donc continuer jusqu'à 0.
Mais si tu avais vu que 48 divise 144, tu aurais pu conclure toutde suite que le PGCD de 432 et 240 est 48.
Si b divise a, alors pgcd(a;b)=b
Donc en fait il s'agit de la même méthode que les différences successives sauf qu'à chaque boucle on regarde si b divise a (donc on regarde si le pgcd est b) ?
Si c'est ça je pense avoir compris la méthode mais je ne vois pas trop comment l'expliquer.
Je propose une formulation :
On sait que si un nombre en divise 2 autres, il en divise une combinaison linéaire, plus particulièrement leur différence.
On cherche donc le PGCD aux deux nombres en faisant des différences jusqu'à ce que l'un divise l'autre. En effet, quand on arrive à b divise a, pgcd(a;b)=b
Oui ; il faut aussi justifier que cet algorithme s'arrête.
Je n'ai pas trop le temps d'expliquer. A chaque étape, b est remplacé par un entier au moins inférieur ou égal à l'ancienne valeur de b-1 ou de a-1 .
Il me semble plus facile de travailler sur a :
On a toujours 0 < b < a :
C'est vrai au départ ; puis 0 < min(b;a-b) < max(b,a-b) ; donc nouvelle valeur de b < nouvelle valeur de a
A chaque étape, la nouvelle valeur de a est max(b,a-b) qui est strictement inférieur à a .
La nouvelle valeur de a est donc inférieure ou égale à a-1.
Il y a donc moins de a étapes.
Je recommence en complétant après "C'est vrai au départ".
On a toujours 0 < b < a :
C'est vrai au départ ; puis 0 < min(b;a-b) max(b,a-b) ; l'inégalité entre le min et le max est une égalité que si b = a-b équivalent à a = 2b ; dans ce cas b divise a et le "tant que" s'arrête. L'inégalité est donc stricte quand on passe à l'étape suivante et 0 < nouvelle valeur de b < nouvelle valeur de a .
A chaque étape, la nouvelle valeur de a est max(b,a-b) qui est strictement inférieur à a .
La nouvelle valeur de a est donc inférieure ou égale à a-1.
Il y a donc moins de a étapes.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :