{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![En tête general](img/En_tete_general.png)\n",
"\n",
"\n",
"*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\n",
"\n",
" Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# PGCD par l'algorithme d'Euclide et coefficients de Bézout (corrigé)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Sommaire\n",
"\n",
"1. Description et étude de l'algorithme d'Euclide
\n",
"2. Implémentation Python de l'algorithme d'Euclide
\n",
"3. Identité de Bézout
\n",
"4. Implémentation Python de la recherche des coefficients de Bézout
\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Description et étude de l'algorithme d'Euclide"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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)$.__
\n",
"Aide :
\n",
"On 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",
"\n",
"Soit $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)$.
\n",
"Soit $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)$.
\n",
"Finalement, on a bien démontré que $D(a;b)=D(b;r)$.\n",
" \n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"
\n",
"Il 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$.
\n",
"Nous 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$.
\n",
"Nous l'appelerons algorithme d'Euclide.\n",
"
\n",
"On considère deux entiers naturels $a$ et $b$ non nuls.
\n",
"On 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",
"
\n",
"On 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",
"
\n",
"Pour $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",
"