(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
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$.
On a donc $a=bq+r$ avec $0 \leqslant r<b$.
On note $D(a;b)$ (respectivement $D(b;r)$) l'ensemble des diviseurs communs de $a$ et $b$ (respectivement de $b$ et $r$).
Démontrer que $D(a;b)=D(b;r)$.
Aide :
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$.
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$.
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$.
Nous l'appelerons algorithme d'Euclide.
1.2. Dans cette question uniquement, on considère les nombres $a=525$ et $b=237$ dont on souhaite déterminer le PGCD.
Suivre la vidéo ci-dessous, qui traite ce cas particulier.
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.
On considère deux entiers naturels $a$ et $b$ non nuls.
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.
\begin{array}{}
\color{red}{a_0} &=& \color{blue}{b_0} \; q_0 & + & \color{green}{r_0} \\
\; & \color{blue}\swarrow & \; & \color{green}\swarrow \\
\color{blue}{a_1} &=& \color{green}{b_1} \; q_1 & + & \color{magenta}{r_1} \\
\; & \color{green}\swarrow & \; & \color{magenta}\swarrow \\
\color{green}{a_2} &=& \color{magenta}{b_2} \; q_2 & + & \color{brown}{r_2} \\
\; & \color{magenta}\swarrow & \; & \color{brown}\swarrow \\
... & \; & \;... & & ... \\
... & \; & \;... & & ... \\
\color{lightblue}{a_{n-2}} &=& \color{pink}{b_{n-2}} \; q_{n-2} & + & \color{orange}{r_{n-2}} \\
\; & \color{pink}\swarrow & \; & \color{orange}\swarrow \\
\color{pink}{a_{n-1}} &=& \color{orange}{b_{n-1}} \; q_{n-1} & + & \color{olive}{r_{n-1}} \\
\; & \color{orange}\swarrow & \; & \color{olive}\swarrow \\
\color{orange}{a_n} &=& \color{olive}{b_n} \; q_n & + & \color{purple}{r_n} \\
... & \; & \;... & & ... \\
... & \; & \;... & & ... \\
\end{array}
$\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
$\bullet$ Pour $n \geqslant 1$ ; S'ils existent, $a_n=b_{n-1}$ et $b_n=r_{n-1}$.
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.
$\;\;\;$En déduire qu'il existe un rang $N$ tel que $r_N=0$.
b. On reprend ici les notations de la question 1.
$\;\;\;$Démontrer que $D(a;b)=D(b_N;0)$.
c. En déduire que $b_N$ est le PGCD de $a$ et $b$.
$\;\;\;$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$.
2.1. Exécuter chacune des cellules ci-dessous. Décrire brièvement ce que permettent de réaliser les syntaxes proposées.
# Exécuter cette cellule
a,b = 525,237
a%b
# Exécuter cette cellule
a,b = 525,237
a,b = b,a%b
a,b
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.
Aide :
On utilisera une boucle, dans laquelle on modifiera pas à pas les valeurs des variables a et b.
Par exemple, pour les valeurs initiales $525$ et $237$, les valeurs successives des variables seront :
a | b | a%b |
---|---|---|
525 | 237 | 51 |
237 | 51 | ... |
... | ... | ... |
... | ... | 0 |
# Ecrire la fonction PGCD
# Exécuter cette cellule pour vérifier
PGCD(525,237)
3.1 Suivre la vidéo ci-dessous, qui reprend le cas particulier où $a=525$ et $b=237$.
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 :
\begin{array}{}
\color{red}{a_0} &=& \color{blue}{b_0} q_0 & + & \color{green}{r_0} \\
\; & \color{blue}\swarrow & \; & \color{green}\swarrow \\
\color{blue}{a_1} &=& \color{green}{b_1} q_1 & + & \color{magenta}{r_1} \\
\; & \color{green}\swarrow & \; & \color{magenta}\swarrow \\
\color{green}{a_2} &=& \color{magenta}{b_2} q_1 & + & \color{brown}{r_2} \\
\; & \color{magenta}\swarrow & \; & \color{brown}\swarrow \\
... & \; & \;... & & ... \\
... & \; & \;... & & ... \\
\color{lightblue}{a_{n-2}} &=& \color{pink}{b_{n-2}} q_{n-2} & + & \color{orange}{r_{n-2}} \\
\; & \color{pink}\swarrow & \; & \color{orange}\swarrow \\
\color{pink}{a_{n-1}} &=& \color{orange}{b_{n-1}} q_{n-1} & + & \color{olive}{r_{n-1}} \\
\; & \color{orange}\swarrow & \; & \color{olive}\swarrow \\
\color{orange}{a_n} &=& \color{olive}{b_n} q_n & + & \color{purple}{r_n} \\
... & \; & \;... & & ... \\
... & \; & \;... & & ... \\
\; & \color{blue}\swarrow & \; & \color{green}\swarrow \\
\color{blue}{a_{N-1}} &=& \color{green}{b_{N-1}} q_{N-1} & + & \color{magenta}{r_{N-1}} \\
\; & \color{green}\swarrow & \; & \color{magenta}\swarrow \\
\color{green}{a_N} &=& \color{magenta}{b_N} q_N & + & \color{red}0 \\
\end{array}
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$ .
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$.
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$.
3.4. Pour $2 \leqslant n \leqslant N$, on pose :
$\;\;\;\;\;$$u_n=u_{n-2}-u_{n-1}q_n$
3.5. Démontrer que:
Identité de Bézout :
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$.
Avertissement : Cette implémentation Python utilise le calcul matriciel (au programme de Math-Expertes).
On reprend le cas de deux entiers naturels non nuls $a$ et $b$, et les notations utilisées dans les parties précédentes.
On considère les matrices $P_n$ définies par :
$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)$
et pour $1 \leqslant n \leqslant N$ :
$P_n=\left (\begin{matrix} 0&1\\ 1&-q_{n} \end{matrix}\right) \times P_{n-1}$
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)$.
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$.
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.
a = 525
b = 237
# Syntaxe pour obtenir le quotient d'une division euclidienne
q = a//b
q
import numpy as np
# Syntaxes pour définir une matrice
# Chacune des listes intérieures correspond à une ligne de la matrice
P = np.array([ [ 0 , 1 ] , [ 1 , -q ] ])
P # Cette matrice correspond à P_0
s,t = P[0]
s,t # Ces valeurs correspondent à la première ligne de la matrice P_0
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.
a,b = b,a%b
q = a//b
# Syntaxe pour multiplier deux matrices
P = np.dot( np.array([ [ 0 , 1 ] , [ 1 , -q ] ]) , P )
P
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$.
Aide:
On pourra reprendre et modifier la fonction Python de la question 2.2.
# Ecrire la fonction Bezout
import numpy as np
# Exécuter cette cellule pour tester la fonction
Bezout(-525,-237)
(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/