{"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

\n"},{"metadata":{},"cell_type":"markdown","source":"__1.2. Dans cette question uniquement, on considère les nombres $a=525$ et $b=237$ dont on souhaite déterminer le PGCD.__
\n__Suivre la vidéo ci-dessous, qui traite ce cas particulier.__

\n\n