spé maths ts algorithme d'Euclide

[CharlineCoco]

Bonjour
la question est la suivante:
"a et b désignent deux entiers naturels non nuls tels que PGCD (a,b) = 7 . La dernière division de reste nul étant écrite, les quotients successifs de l'algorithme d'Euclide sont respectivement 3; 1; 1; 3. quelles sont de a et b?"
Je ne sais pas comment commencer :/
Merci d'avance
-----

[mickan]

Bonjour,

a=3*b+r1
b=1*r1+r2
r1=1*r2+r3
r2=3*r3+0

ajouter le faite que a^b=7

[sylvainc2]

On considère la tableau suivant:



À chaque ligne i on fait:
a_i = b_i-1
b_i = r_i-1
q_i = quotient de a_i / b_i
r_i = reste de a_i / b_i

C'est juste l'algo d'Euclide mis sous forme de tableau.

A la dernière ligne le reste est toujours 0 (c'est comme ça que l'algo termine), et à l'avant-derniere ligne le reste est toujours le pgcd, ici c'est 7 selon l'énoncé.

Ensuite l'énoncé dit que les q_i sont 3,1,1,3 à partir de la dernière ligne (où la dernière division est faite), on les écrit dans le tableau dans cet ordre.

A chaque ligne on doit calculer a=qb+r. Il ne reste plus qu'à faire l'algo d'Euclide mais à l'envers.

A la ligne 4 on fait 3*7+0 = 21 = a₄.

Puis on reporte b₄ dans r₃ (c'est déjà fait), et a₄ dans b₃.

Puis on calcule a₃ = ...etc..., et on reporte b₃ dans r₂ et a₃ dans b₂, et on remonte ainsi jusqu'à la ligne 1.

Je te laisse compléter le tableau, tu devrais trouver a=175 et b=49.