Type de calculatrice
TI
Prérequis
L’algorithme d’Euclide, partant de deux entiers et avec , détermine d’abord un reste , puis, partant de et de , un autre reste et ainsi de suite, jusqu’au dernier reste non nul qui est le PGCD de et .
Remonter à l’envers l’algorithme d’Euclide permet de construire les coefficients et dits de Bézout, tels que .
Description
Programme
Le programme prend deux entiers et et calcule les restes successifs , …, .
À chaque reste il considère des coefficients et tels que .
Comme , on a et .
De même, vu que , on a et .
Ensuite, si l’on connaît et on peut en déduire .
Posons le quotient de par alors :
- (principe de la division euclidienne de par ) ;
- (on a isolé ) ;
- donc
Variables
deux entiers entrés par l’utilisateur
un entier calculé par le programme
et les coefficients correspondant à dans l’explication ci-dessus
et les coefficients correspondant à dans l’explication ci-dessus
et les coefficients correspondant à dans l’explication ci-dessus
le rapport correspondant à ci-dessus
Algorithme
|demander et
| le reste de la division euclidienne de par
| et
|tant que
| prend la valeur du quotient euclidien de
| prend la valeur de
| prend la valeur de
| prend la valeur de
| prend la valeur de , prend la valeur de
| prend la valeur de , prend la valeur de
| prend la valeur de , prend la valeur de
|fin du tant que
|afficher (le PGCD)
|afficher
Programme TI
- « Prompt » « A » « : »
« Prompt » « B » - « A »
« NUM » « ent( »
« A » « B »
« B » « ➔ » « R » - « ➔ » « C » « : »
« ➔ » « D » « : »
« ➔ » « E » « : »
« ➔ » « F » - « While » « R »
« ≠ » - « NUM » « ent( »
« A » « B »
« ➔ » « M » - « A » « M » « B »
« ➔ » « R »
« C » « M » « E »
« ➔ » « G »
« D » « M » « F »
« ➔ » « H » - « B » « ➔ » « A » « : »
« R » « ➔ » « B »
« E » « ➔ » « C » « : »
« F » « ➔ » « D »
« G » « ➔ » « E » « : »
« H » « ➔ » « F » - « End »
- « Disp » « A »
« Disp » « C »
« Disp » « D »