Aller dans Outils >Lycée > Informatique >Python>IDLE ou utiliser wing 101
Faire new File pour ouvrir l'éditeur de texte pour pouvoir écrire un programme
A chaque fois qu'un programme est écrit le sauvegarder en faisant CTRL S. La première fois donner un nom significatif au programme, avec un suffixe .py
Ensuite pour exécuter le programme faire F5
Données : $a$ un entier naturel non nul, $b$ un entier naturel non nul
Sortie : un entier relatif $d$ le pgcd de $a$ et $b$ en faisant des divisions successives
Exemples : $a = 70$ et $b = 42$ donc $d = 14$
Comment trouver une combinaison linéaire de $a$ et $b$ donnant le pgcd de $a$ et $b$?
Réécrire $(r_{n-1},r_n) -> (r_{n},r_{n+1})$Puisque nous savons que pgcd($a$,$b$) est le dernier reste non nul des divisions successives dans l'algorithme d'Euclide, pour trouver cette combinaison linéaire on procède ainsi:
En posant $r_{-1} = a$ et $r_{0 } = b < a$ avec $ r_{n-2}= r_{n-1}q_{n} + r_{n}$ on peut calculer les termes de la suite $(r_n)$. Nous avons ici une récurrence double, pour déterminer $r_n$ nous avons besoin des deux termes précédents et l'initialisation se fait avec les deux termes initiaux $r_{-1} = a$ et $r_{0 } = b < a$
Un tour de boucle fait passer de $(r_{n-1},r_n)$ à $(r_{n},r_{n+1})$
De plus l'invariant de boucle est que chaque reste $r_k$ soit une combinaison linéaire de $a$ et $b$
En partant de $r_{-1} = a = 1\times a + 0 \times b = u_{-1}a+v_{-1}b$ et $r_{0} = b = 0\times a + 1 \times b = u_0a+v_0b$, on veut construire par récurrence deux suites $(u_n)$ et $(v_n)$ telles que : $r_n = u_na+v_nb$ et $u_{-1} = 1$, $u_0 = 0$ et $v_{-1} = 0$, $v_0 = 1$, il nous reste à trouver une relation de récurrence reliant $w_n=(u_n,v_n)$ à $w_{n-1}=(u_{n-1},v_{n-1})$ et $w_{n-2}=(u_{n-2},v_{n-2})$ Vérifier que cette relation est $w_n = w_{n-2} - \lfloor\dfrac{r_{n-2}}{r_{n-1}}\rfloor w_{n-1}$
Ecrire l'algorithme d'Euclide étendu où un tour de boucle met à jour deux couples de variables $(r_{n-1},r_n) -> (r_{n},r_{n+1})$ et $(w_{n-1},w_n) -> (w_{n},w_{n+1})$
Le traduire en Python