#!/usr/bin/env python
# coding: utf-8

# ![En tête general](img/En_tete_general.png)
# 
# 
# *(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*
# 
# <span style="color: #9317B4"> Pour exécuter une saisie Python, sélectionner la cellule et valider avec </span><span style="color: #B317B4"><strong>SHIFT+Entrée</strong></span>.
# 

# # <span style="color:#6C3483">PGCD par l'algorithme d'Euclide et coefficients de Bézout</span>

# ### <span style="color:#8E44AD">Sommaire</span>
# 
# <span style="color:#8E44AD">1.</span> <a href="#1">Description et étude de l'algorithme d'Euclide</a><br>
# <span style="color:#8E44AD">2.</span> <a href="#2">Implémentation Python de l'algorithme d'Euclide</a><br>
# <span style="color:#8E44AD">3.</span> <a href="#3">Identité de Bézout</a><br>
# <span style="color:#8E44AD">4.</span> <a href="#4">Implémentation Python de la recherche des coefficients de Bézout</a><br>
# 

# ## <span style="color:#8E44AD" id="1">1. Description et étude de l'algorithme d'Euclide</span>

# __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$.__<br> 
# __On a donc $a=bq+r$ avec $0 \leqslant r<b$.__<br>
# __On note $D(a;b)$ (respectivement $D(b;r)$) l'ensemble des diviseurs communs de $a$ et $b$ (respectivement de $b$ et $r$).__<br>
# __Démontrer que $D(a;b)=D(b;r)$.__<br>
# Aide :<br>
# 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$.
# 
# 

# <p style='background-color:#F5EEF8;' >
# 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$.<br>
# 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$.<br>
# Nous l'appelerons <strong>algorithme d'Euclide</strong>.
# </p>
# 

# __1.2. Dans cette question uniquement, on considère les nombres $a=525$ et $b=237$ dont on souhaite déterminer le PGCD.__<br>
# __Suivre la vidéo ci-dessous, qui traite ce cas particulier.__<br><br>
# 
# <video controls src="video/Euclide_Bezout_1.mp4" width="960" height="540" />
# 

# __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.__
# 
# 
# 
# <p style='background-color:#F5EEF8;' >
# On considère deux entiers naturels $a$ et $b$ non nuls.<br> 
# 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.<br><br>
# \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}
# <br>
# $\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<b_n$.<br><br>
# $\bullet$ Pour $n \geqslant 1$ ; S'ils existent, $a_n=b_{n-1}$ et $b_n=r_{n-1}$.
# </p>
# 
# 
# 
# 

# __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.__<br>
# $\;\;\;$__En déduire qu'il existe un rang $N$ tel que $r_N=0$.__<br>
# 
# 
# __b. On reprend ici les notations de la question 1.__ <br>
# $\;\;\;$__Démontrer que $D(a;b)=D(b_N;0)$.__ 
# 
# 
# __c. En déduire que $b_N$ est le PGCD de $a$ et $b$.__<br>
# $\;\;\;$__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$.__
# 
# 

# ## <span style="color:#8E44AD" id="2">2. Implémentation Python de l'algorithme d'Euclide</span>

# __2.1. Exécuter chacune des cellules ci-dessous. Décrire brièvement ce que permettent de réaliser les syntaxes proposées.__

# In[ ]:


# Exécuter cette cellule

a,b = 525,237

a%b


# In[ ]:


# Exécuter cette cellule

a,b = 525,237

a,b = b,a%b

a,b 


# __2.2. Ecrire une fonction <mark>PGCD</mark> qui reçoit deux entiers naturels non nuls <mark>a</mark> et <mark>b</mark> en arguments, et renvoie leur PGCD déterminé à l'aide de l'algorithme d'Euclide.__ <br>
# Aide : <br>
# On utilisera une boucle, dans laquelle on modifiera pas à pas les valeurs des variables <mark>a</mark> et <mark>b</mark>.
# Par exemple, pour les valeurs initiales $525$ et $237$, les valeurs successives des variables seront :
# 
# |  <mark>a</mark>   |  <mark>b</mark>   | <mark><span style="color:#7F8C8D">a%b</span></mark> | 
# |:-----|:-----|:-----|
# | 525  | 237  |  <span style="color:#7F8C8D">51</span>   |
# | 237  |  51  |  <span style="color:#7F8C8D">...</span>  |
# | ...  | ...  |  <span style="color:#7F8C8D">...</span>  |
# | ...  | ...  |  <span style="color:#7F8C8D">0</span>    |
# 
# 

# In[ ]:


# Ecrire la fonction PGCD




# In[ ]:


# Exécuter cette cellule pour vérifier

PGCD(525,237)


# ## <span style="color:#8E44AD" id="3">3. Étude de l'identité de Bézout</span>

# __3.1 Suivre la vidéo ci-dessous, qui reprend le cas particulier où $a=525$ et $b=237$.__<br><br>
# 
# <video controls src="video/Euclide_Bezout_2.mp4" width="960" height="540" />
# 
# 

# <p style='background-color:#F5EEF8;' >
# 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 :<br><br>
# \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}
# <br>
# Pour $0 \leqslant n \leqslant N $, nous allons déterminer des coefficients entiers relatifs $u_n$ et $v_n$ tels que  <span style='background-color:#D7BDE2;'>  $au_n+bv_n=r_n$ </span>.
# </p>

# __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 :__
# <br><br>
# $\;\;\;\;\;$__$u_n=u_{n-2}-u_{n-1}q_n$__ 
# <br>
# $\;\;\;\;\;$__$v_n=v_{n-2}-v_{n-1}q_n$.__ 
# <br><br>
# $\;\;\;\;\;$__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$__
# 
# 
# __3.5. Démontrer que:__
# 
# <p style='background-color:#D7BDE2;'>
#     <strong> Identité de Bézout :</strong><br>
#     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$.
# </p><br>
# Aide :<br>
# 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}$.<br>
# Traiter ensuite le cas où $a$ et $b$ ne sont pas tous deux positifs.
# 

# ## <span style="color:#8E44AD" id="4">4. Implémentation Python de la recherche des coefficients de Bézout</span>

# <span style="color:#FF2222">Avertissement : Cette implémentation Python utilise le calcul matriciel (au programme de Math-Expertes).</span>

# 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)$
# <br><br>et pour $1 \leqslant n \leqslant N$ :<br><br>
# $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.__

# In[ ]:


a = 525
b = 237

# Syntaxe pour obtenir le quotient d'une division euclidienne
q = a//b

q


# In[ ]:


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


# In[ ]:


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.__
# 
# 

# In[ ]:


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 <mark>Bezout</mark> 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$.__<br>
# Aide:<br>
# On pourra reprendre et modifier la fonction Python de la question 2.2.

# In[ ]:


# Ecrire la fonction Bezout
import numpy as np




# In[ ]:


# Exécuter cette cellule pour tester la fonction

Bezout(-525,-237)


# ![Euclide_et_Bézout](img/Euclide_Bezout.png)
# 
# <center><a href="https://fr.wikipedia.org/wiki/Euclide">Euclide</a> (IVème-IIIème siècle av JC) et <a href="https://fr.wikipedia.org/wiki/%C3%89tienne_B%C3%A9zout">Étienne Bézout</a> (1730-1783)</center>

# *(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*
#