Ouvrir EduPython pour utiliser les modules numpy et numpy.linalg (pour linear algebra) de Python, pour utiliser Python comme assistant de calcul matriciel
Ecrire une fonction python euclide(a,b) qui retourne le pgcd de a et b
Exemples : $a = 70$ et $b = 42$ donc $d = 14$
Comment trouver une combinaison linéaire de $a$ et $b$ donnant le pgcd de $a$ et $b$?
"A la main" on remonte dans la suite des divisions euclidiennes mais comment le faire faire par une machine ?
On écrit la suite des divisions euclidiennes jusqu'à obtenir le dernier reste nul
$r_{-1} = a = bq + r = r_0q+ r_1$
$r_0 = r_1q_2+ r_2$
..................
$ r_{n-2}= r_{n-1}q_{n} + r_{n}$
Nous avons ici une récurrence double, pour déterminer $r_n$ nous avons besoin des deux termes précédents et l'initialisation se fait avec les deux termes initiaux $r_{-1} = a$ et $r_{0 } = b $
Un tour de boucle fait passer de $(r_{n-1},r_n)$ à $(r_{n},r_{n+1})$
De plus l'invariant de boucle est que chaque reste $r_k$ soit une combinaison linéaire de $a$ et $b$
En partant de $r_{-1} = a = 1\times a + 0 \times b = u_{-1}a+v_{-1}b$ et $r_{0} = b = 0\times a + 1 \times b = u_0a+v_0b$, on veut construire par récurrence deux suites $(u_n)$ et $(v_n)$ telles que : $r_n = u_na+v_nb$ et $u_{-1} = 1$, $u_0 = 0$ et $v_{-1} = 0$, $v_0 = 1$, il nous reste à trouver une relation de récurrence reliant $w_n=(u_n,v_n)$ à $w_{n-1}=(u_{n-1},v_{n-1})$ et $w_{n-2}=(u_{n-2},v_{n-2})$
Vérifier que cette relation est $w_n = w_{n-2} - \lfloor\dfrac{r_{n-2}}{r_{n-1}}\rfloor w_{n-1}$
Ecrire l'algorithme d'Euclide étendu où un tour de boucle met à jour deux couples de variables $(r_{n-1},r_n) -> (r_{n},r_{n+1})$ et $(w_{n-1},w_n) -> (w_{n},w_{n+1})$
Le traduire en Python
La matrice $T = \begin{pmatrix} 1 & 1 &1\\ 0& 1 & 1\\ 0 & 0 &1 \end{pmatrix}$ est une liste de listes (ligne par ligne)
Recopier le code suivant et l'exécuter
import numpy as np
T = np.array([[1,1,1],[0,1,1],[0,0,1]])
#I est la matrice identité d'ordre 3
I = np.eye(3)
S = T - I
print(S)
Maintenant il s'agit de calculer $S^3$ et de vérifier que l'on obtient la matrice nulle. Une façon de faire est :
Recopier le code suivant et l'exécuter
import numpy as np
T = np.array([[1,1,1],[0,1,1],[0,0,1]])
#I est la matrice identité d'ordre 3
I = np.eye(3)
S = T - I
S2 = S.dot(S)
S3 = S2.dot(S)
#on peut faire aussi S3 = S.dot(S).dot(S)
print(S3)
Une autre façon est d'utiliser le module numpy.linalg
import numpy as np
import numpy.linalg as alg
T = np.array([[1,1,1],[0,1,1],[0,0,1]])
#I est la matrice identité d'ordre 3
I = np.eye(3)
S = T - I
S3 = alg.matrix_power(S,3)
print(S3)