{"cells":[{"metadata":{},"cell_type":"markdown","source":"![En tête general](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/En_tete_general.png)\n\n\n© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
\nLes activités partagées sur Capytale sont sous licence Creative Commons.\n\n Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.\n"},{"metadata":{},"cell_type":"markdown","source":"# PGCD par l'algorithme d'Euclide et coefficients de Bézout (corrigé)"},{"metadata":{},"cell_type":"markdown","source":"### Sommaire\n\n1. Description et étude de l'algorithme d'Euclide
\n2. Implémentation Python de l'algorithme d'Euclide
\n3. Identité de Bézout
\n4. Implémentation Python de la recherche des coefficients de Bézout
\n"},{"metadata":{},"cell_type":"markdown","source":"## 1. Description et étude de l'algorithme d'Euclide"},{"metadata":{},"cell_type":"markdown","source":"__1.1. On considère deux entiers naturels $a$ et $b$ non nuls. On note $q$ et $r$ respectivement le quotient et le reste de la division euclidienne de $a$ par $b$.__
\n__On a donc $a=bq+r$ avec $0 \\leqslant r\n__On note $D(a;b)$ (respectivement $D(b;r)$) l'ensemble des diviseurs communs de $a$ et $b$ (respectivement de $b$ et $r$).__
\n__Démontrer que $D(a;b)=D(b;r)$.__
\nAide :
\nOn pourra démontrer que tout diviseur commun de $a$ et de $b$ est aussi un diviseur commun de $b$ et de $r$, puis réciproquement que tout diviseur commun de $b$ et de $r$ est aussi un diviseur commun de $a$ et de $b$.\n\n\nSoit $d \\in D(a;b)$ un diviseur commun à $a$ et $b$. $d$ divise donc toute combinaison linéaire de $a$ et $b$, et il divise en particulier $a-bq=r$. Donc d divise b et r, c'est à dire $d \\in D(b;r)$. On a démontré que $D(a;b) \\subset D(b;r)$.
\nSoit $d \\in D(b;r)$ un diviseur commun à $b$ et $r$. $d$ divise donc toute combinaison linéaire de $b$ et $r$, et il divise en particulier $bq+r=a$. Donc d divise a et b, c'est à dire $d \\in D(a;b)$. On a démontré que $D(b;r) \\subset D(a;b)$.
\nFinalement, on a bien démontré que $D(a;b)=D(b;r)$.\n \n\n"},{"metadata":{},"cell_type":"markdown","source":"
\nIl résulte du résultat précédent que la recherche du PGCD (plus grand commun diviseur) de deux nombres entiers naturels $a$ et $b$ non nuls peut se ramener à la recherche du PGCD de $b$ et $r$, où $r$ est le reste de la division euclidienne de $a$ par $b$.
\nNous allons décrire une méthode de calcul qui permet de déterminer en un nombre fini d'opérations le PGCD de $a$ et $b$.
\nNous l'appelerons algorithme d'Euclide.\n
\nOn considère deux entiers naturels $a$ et $b$ non nuls.
\nOn pose $\\color{red}{a_0=a}$ et $\\color{blue}{b_0=b}$ puis on considère la succession des divisions euclidiennes suivantes, réitérées tant que le reste $r_n$ n'est pas nul.
\n\\begin{array}{} \n\\color{red}{a_0} &=& \\color{blue}{b_0} \\; q_0 & + & \\color{green}{r_0} \\\\ \n\\; & \\color{blue}\\swarrow & \\; & \\color{green}\\swarrow \\\\ \n\\color{blue}{a_1} &=& \\color{green}{b_1} \\; q_1 & + & \\color{magenta}{r_1} \\\\ \n\\; & \\color{green}\\swarrow & \\; & \\color{magenta}\\swarrow \\\\ \n\\color{green}{a_2} &=& \\color{magenta}{b_2} \\; q_2 & + & \\color{brown}{r_2} \\\\ \n\\; & \\color{magenta}\\swarrow & \\; & \\color{brown}\\swarrow \\\\\n... & \\; & \\;... & & ... \\\\ \n... & \\; & \\;... & & ... \\\\\n\\color{lightblue}{a_{n-2}} &=& \\color{pink}{b_{n-2}} \\; q_{n-2} & + & \\color{orange}{r_{n-2}} \\\\ \n\\; & \\color{pink}\\swarrow & \\; & \\color{orange}\\swarrow \\\\ \n\\color{pink}{a_{n-1}} &=& \\color{orange}{b_{n-1}} \\; q_{n-1} & + & \\color{olive}{r_{n-1}} \\\\ \n\\; & \\color{orange}\\swarrow & \\; & \\color{olive}\\swarrow \\\\ \n\\color{orange}{a_n} &=& \\color{olive}{b_n} \\; q_n & + & \\color{purple}{r_n} \\\\ \n... & \\; & \\;... & & ... \\\\ \n... & \\; & \\;... & & ... \\\\ \n\\end{array}\n
\n$\\bullet$ Pour $n \\geqslant 0$ ; S'ils existent, $q_n$ et $r_n$ sont respectivement le quotient et le reste de la division euclidienne de $a_n$ par $b_n$, et on a donc $0 \\leqslant r_n
\n$\\bullet$ Pour $n \\geqslant 1$ ; S'ils existent, $a_n=b_{n-1}$ et $b_n=r_{n-1}$.\n
\nOn reprend les notations précédemment introduites pour la mise en oeuvre de l'algorithme d'Euclide, où $a$ et $b$ sont des entiers naturels non nuls :
\n\\begin{array}{} \n\\color{red}{a_0} &=& \\color{blue}{b_0} q_0 & + & \\color{green}{r_0} \\\\ \n\\; & \\color{blue}\\swarrow & \\; & \\color{green}\\swarrow \\\\ \n\\color{blue}{a_1} &=& \\color{green}{b_1} q_1 & + & \\color{magenta}{r_1} \\\\ \n\\; & \\color{green}\\swarrow & \\; & \\color{magenta}\\swarrow \\\\ \n\\color{green}{a_2} &=& \\color{magenta}{b_2} q_1 & + & \\color{brown}{r_2} \\\\ \n\\; & \\color{magenta}\\swarrow & \\; & \\color{brown}\\swarrow \\\\\n... & \\; & \\;... & & ... \\\\ \n... & \\; & \\;... & & ... \\\\\n\\color{lightblue}{a_{n-2}} &=& \\color{pink}{b_{n-2}} q_{n-2} & + & \\color{orange}{r_{n-2}} \\\\ \n\\; & \\color{pink}\\swarrow & \\; & \\color{orange}\\swarrow \\\\ \n\\color{pink}{a_{n-1}} &=& \\color{orange}{b_{n-1}} q_{n-1} & + & \\color{olive}{r_{n-1}} \\\\ \n\\; & \\color{orange}\\swarrow & \\; & \\color{olive}\\swarrow \\\\ \n\\color{orange}{a_n} &=& \\color{olive}{b_n} q_n & + & \\color{purple}{r_n} \\\\ \n... & \\; & \\;... & & ... \\\\ \n... & \\; & \\;... & & ... \\\\ \n\\; & \\color{blue}\\swarrow & \\; & \\color{green}\\swarrow \\\\ \n\\color{blue}{a_{N-1}} &=& \\color{green}{b_{N-1}} q_{N-1} & + & \\color{magenta}{r_{N-1}} \\\\ \n\\; & \\color{green}\\swarrow & \\; & \\color{magenta}\\swarrow \\\\ \n\\color{green}{a_N} &=& \\color{magenta}{b_N} q_N & + & \\color{red}0 \\\\\n\\end{array}\n
\nPour $0 \\leqslant n \\leqslant N $, nous allons déterminer des coefficients entiers relatifs $u_n$ et $v_n$ tels que $au_n+bv_n=r_n$ .\n
\n Identité de Bézout :
\n Pour $a$ et $b$ entiers relatifs non nuls dont le PGCD est $d$, il existe deux coefficients entiers relatifs $u$ et $v$ tels que $au+bv=d$.\n