Exercice

On considère l’algorithme suivant, où A et B sont des entiers naturels tels que A < B :

1 On entre A = 12 et B = 14.

En remplissant le tableau donné ci-après, déterminer la valeur affichée par l’algorithme.

2 Cet algorithme calcule la valeur du PGCD des nombres A et B.

En entrant A = 221 et B = 331, l’algorithme affiche la valeur 1.

a. Justifier qu’il existe des couples (x ; y) d’entiers relatifs solutions de l’équation :

(E) 221x – 331y = 1.

b. Vérifier que le couple (3 ; 2) est une solution de l’équation (E).

En déduire l’ensemble des couples (x ; y) d’entiers relatifs solutions de l’équation (E).

3 On considère les suites d’entiers naturels (u_n) et (v_n) définies pour tout entier naturel n par :

u n =2+221net{ v 0 =3 v n+1 = v n +331

a. Exprimer v_n en fonction de l’entier naturel n.

b. Déterminer tous les couples d’entiers naturels (p ; q) tels que :

u_p = v_q, 0 ≤ p ≤ 500 et 0 ≤ q ≤ 500.