Bonjour, j'aimerais votre aide pour un exercice de base sur le PGCD mais que je n'arrive malheureusement pas:
a et b designent deux entiers naturels tels que PGCD(a,b)=7
La dernière division de reste nul étant écrite les quotients sucessifs de l'algorithme d'Euclide sont respectivement 3;11;3
Quelles sont les valeurs de a et b?
Merci beaucoup à ceux qui m'aideront.
Déjà, quand tu as le pgcd de deux nombres, tu peux dire qu'il les divise tous deux.
a = 7a'
b = 7b'
et a' et b' sont premiers entre eux.
Ensuite, il faut que tu saches "retranscrire" l'hypothèse concernant l'algorithme d'Euclide. Celui-ci consiste à faire la division euclidienne des deux premiers nombres. Puis, du deuxième nombre (celui que tu trouveras multiplié au premier quotient) avec le reste de la première division euclidienne, et ainsi de suite...
Pour faire plus clair :
Première division euclidienne :
Deuxième division euclidienne :
Troisième division euclidienne (qui sera la dernière, car tu l'auras compris, on ne te donne que 3 quotients) ;
On t'a dit qu'on atteignait la division avec un reste nul. Donc
On t'a donné les valeurs de,
Wait a moment pour la suite, c'est déjà pas mal ça ^^
on a donc bien :
a = 7a'
b = 7b'
et a' et b' sont premiers entre eux.
Puis cela fera
Première division euclidienne : a=b* q1 + r1 soit a= 3b +r1
Deuxième division euclidienne :b=r1 * q2 +r2 soit b= r1 +r2
Troisième division euclidienne :r1 = r2* q3 +r3 soit r1=r2+r3
quatrième divison euclidienne :r2 = r3*q4+ r4 avec r4=0 d'ou r2=3*r4
• or on sait que pgcd(a,b)= 7= r3 soit r3=7
et r1=r3+r2 soit r1= r2+7
or b=r1+r2 donc b=r2+7+r2 soit b= 2 r2 +7
et a = 3b +r1 donc a=3( 2 r2 +7) +r2 +7 soit a=7 r2 + 28
de plus a=7a'
d'ou 7 r2+28=7a'
soit r2+4=a'
et b=7b'
d'ou 2 r2 +7 = b'
soit 2/7 r2 +1 =b'
et PGCD (r2+4 ; 2/7 r2 +1 ) =1
je pense que ce que je viens de faire ne sert pas à grand chose ^^
je ne vois toujours pa comment faire.
s'il vous plait vous n'auriez pas juste une petite piste pour me dire si c'est que j'ai ajouté cela peut me mener quelque part?
Je viens de me rendre compte que j'avais fait une erreur dans l'enoncé les quotients sont 3;1;1;3 d'ou les 4 divisions euclidiennes dans mon premier post!
as tu reussi à resoudre cet exercice?
