\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"
]
},
{
"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"
]
},
{
"cell_type": "markdown",
"metadata": {},
"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",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__1.3. Dans cette question, on souhaite démontrer que la méthode détaillée ci-dessous permet de déterminer le PGCD de $a$ et $b$ en un nombre fini d'opérations.__\n",
"\n",
"\n",
"\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",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__a. Justifier que les restes $r_n$ calculés successivement sont rangés dans un ordre strictement décroissant et sont minorés par 0.__
\n",
"$\\;\\;\\;$__En déduire qu'il existe un rang $N$ tel que $r_N=0$.__
\n",
"\n",
"\n",
"__b. On reprend ici les notations de la question 1.__
\n",
"$\\;\\;\\;$__Démontrer que $D(a;b)=D(b_N;0)$.__ \n",
"\n",
"\n",
"__c. En déduire que $b_N$ est le PGCD de $a$ et $b$.__
\n",
"$\\;\\;\\;$__En particulier, justifier que si $b$ ne divise pas $a$, alors $r_{N-1}$, dernier reste non nul obtenu, est le PGCD de $a$ et $b$.__\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Implémentation Python de l'algorithme d'Euclide"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__2.1. Exécuter chacune des cellules ci-dessous. Décrire brièvement ce que permettent de réaliser les syntaxes proposées.__"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Exécuter cette cellule\n",
"\n",
"a,b = 525,237\n",
"\n",
"a%b"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Exécuter cette cellule\n",
"\n",
"a,b = 525,237\n",
"\n",
"a,b = b,a%b\n",
"\n",
"a,b "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__2.2. Ecrire une fonction PGCD qui reçoit deux entiers naturels non nuls a et b en arguments, et renvoie leur PGCD déterminé à l'aide de l'algorithme d'Euclide.__
\n",
"Aide :
\n",
"On utilisera une boucle, dans laquelle on modifiera pas à pas les valeurs des variables a et b.\n",
"Par exemple, pour les valeurs initiales $525$ et $237$, les valeurs successives des variables seront :\n",
"\n",
"| a | b | a%b | \n",
"|:-----|:-----|:-----|\n",
"| 525 | 237 | 51 |\n",
"| 237 | 51 | ... |\n",
"| ... | ... | ... |\n",
"| ... | ... | 0 |\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Ecrire la fonction PGCD\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Exécuter cette cellule pour vérifier\n",
"\n",
"PGCD(525,237)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Étude de l'identité de Bézout"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__3.1 Suivre la vidéo ci-dessous, qui reprend le cas particulier où $a=525$ et $b=237$.__
\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\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",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__3.2. Vérifier que $u_0=1$ et $v_0=-q_0$ conviennent, c'est à dire qu'on a bien $au_0+bv_0=r_0$.__\n",
"\n",
"\n",
"__3.3. Vérifier que $u_1=-q_1$ et $v_1=1+q_0q_1$ conviennent, c'est à dire qu'on a bien $au_1+bv_1=r_1$.__\n",
"\n",
"\n",
"__3.4. Pour $2 \\leqslant n \\leqslant N$, on pose :__\n",
"
\n",
"$\\;\\;\\;\\;\\;$__$u_n=u_{n-2}-u_{n-1}q_n$__ \n",
"
\n",
"$\\;\\;\\;\\;\\;$__$v_n=v_{n-2}-v_{n-1}q_n$.__ \n",
"
\n",
"$\\;\\;\\;\\;\\;$__Démontrer par récurrence que pour tout entier $n$ tel que $2 \\leqslant n \\leqslant N$, $u_n$ et $v_n$ vérifient $au_n+bv_n=r_n$__\n",
"\n",
"\n",
"__3.5. Démontrer que:__\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",
"
\n",
"Aide :
\n",
"Pour le cas où $a$ et $b$ sont tous deux positifs, utiliser la question précédente et le fait que $d=r_{N-1}$.
\n",
"Traiter ensuite le cas où $a$ et $b$ ne sont pas tous deux positifs.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Implémentation Python de la recherche des coefficients de Bézout"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avertissement : Cette implémentation Python utilise le calcul matriciel (au programme de Math-Expertes)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On reprend le cas de deux entiers naturels non nuls $a$ et $b$, et les notations utilisées dans les parties précédentes.\n",
"\n",
"On considère les matrices $P_n$ définies par : \n",
"\n",
"\n",
"$P_0=\\left (\\begin{matrix} 0&1\\\\ u_0&v_0 \\end{matrix}\\right)=\\left (\\begin{matrix} 0&1\\\\ 1&-q_0 \\end{matrix}\\right)$\n",
"
et pour $1 \\leqslant n \\leqslant N$ :
\n",
"$P_n=\\left (\\begin{matrix} 0&1\\\\ 1&-q_{n} \\end{matrix}\\right) \\times P_{n-1}$ \n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__4.1 Démontrer par récurrence que pour $1 \\leqslant n \\leqslant N$, on a $P_n=\\left (\\begin{matrix} u_{n-1}&v_{n-1}\\\\ u_n&v_n \\end{matrix}\\right)$.__\n",
"\n",
"Ainsi, les coefficients $u=u_{N-1}$ et $v=v_{N-1}$ de l'égalité de Bézout sont les coefficients de la première ligne de la matrice $P_N$.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__4.2 Exécuter les cellules suivantes, qui donnent des syntaxes permettant d'obtenir le quotient d'une division euclidienne, de définir une matrice et d'en extraire des valeurs.__"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 525\n",
"b = 237\n",
"\n",
"# Syntaxe pour obtenir le quotient d'une division euclidienne\n",
"q = a//b\n",
"\n",
"q"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"# Syntaxes pour définir une matrice\n",
"# Chacune des listes intérieures correspond à une ligne de la matrice\n",
"P = np.array([ [ 0 , 1 ] , [ 1 , -q ] ]) \n",
"\n",
"P # Cette matrice correspond à P_0"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s,t = P[0]\n",
"\n",
"s,t # Ces valeurs correspondent à la première ligne de la matrice P_0\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__4.3 Exécuter la cellule ci-dessous, qui permet de calculer P_1 à partir de P_0. Exécuter ensuite plusieurs fois d'affilée cette cellule. Quelles sont les matrices obtenues, stockées successivement dans P? Justifier.__\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a,b = b,a%b\n",
"q = a//b\n",
"\n",
"# Syntaxe pour multiplier deux matrices\n",
"P = np.dot( np.array([ [ 0 , 1 ] , [ 1 , -q ] ]) , P )\n",
"\n",
"P "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__4.4 Ecrire une fonction Bezout qui reçoit en argument deux entiers naturels non nuls $a$ et $b$, et qui renvoie leur PGCD et les coefficients de Bézout associés $u$ et $v$.__
\n",
"Aide:
\n",
"On pourra reprendre et modifier la fonction Python de la question 2.2."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Ecrire la fonction Bezout\n",
"import numpy as np\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Exécuter cette cellule pour tester la fonction\n",
"\n",
"Bezout(-525,-237)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"Euclide (IVème-IIIème siècle av JC) et Étienne Bézout (1730-1783)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*\n"
]
}
],
"metadata": {
"celltoolbar": "Raw Cell Format",
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 2
}