Bonjour à tous,
Dans le cadre d'un TP sur l'algorithme d'Euclide, je dois faire une démonstration par récurrence. J'aimerais bien que vous me donniez votre avis, pour savoir si ce que j'ai écrit est correct ou si je dois changer quelques trucs.
Données du TP
On considère l'espace $\mathbb Z_n = \mathbb Z/n\mathbb Z$. C'est donc l'ensemble des classes d'équivalences $\overline{0}, \overline{1}... \overline{n-1}$. On dit que $b \in \mathbb Z_n$ est inversible si, et seulement si : $pgcd(b, n) = 1\space mod\space n$ (avec $n \in \mathbb N^*$).
L'algorithme d'Euclide permet de savoir s'il est possible d'effectuer cette inversibilité dans $\mathbb Z_n$. L'algo d'Euclide étendu, lui, permet de calculer cet inverse dans $\mathbb Z_n$.
D'après l'algorithme d'Euclide : "si a et b sont deux entiers avec par exemple a>=b, si r est le reste de a par b, alors le pgcd de a et b vaut le pgcd de b et r". Il consiste donc à faire ces divisions :
$r_0 = a$
$r_1 = b$
$r_0 = q_1r_1 + r_2$
$r_1 = q_2r_2 + r_3$
$ etc. $
$r_{m-2} = q_{m-1}r_{m-1} + r_m$
$r_{m-1} = q_mr_m$
$r_m$, dernier élément non-nul, est alors le PGCD de $r_0$ et $r_1$.
Définissons maintenant la suite récurrente $t_0, t_1, ..., t_n$, utilisée pour l'algorithme d'Euclide étendu, et pour laquelle la suite $q_j$ est définie par l'algorithme d'Euclide précédemment écrit :
$t_0 = 0$
$t_1 = 1$
$t_j = t_{j-2} - q_{j-1}t_{j-1} \space mod \space r_0$ (si $j \ge 2$)
Démonstration à faire
Montrez par récurrence : Pour $0 \le j \le m$, on a : $r_j \equiv t_jr_1 \space (mod \space r_0)$.
Ce que j'ai écrit (est-ce correct ?)
Montrons par récurrence que :
$\forall j \in [0;m], r_j \equiv t_jr_1 \space (mod \space r_0)$
Vérifions que la propriété est vraie aux rangs $j = 0$ et $j = 1$.
Au rang $j = 0$ :
$r_0 \equiv t_0r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_0 = t_0r_1 + kr_0$
$r_0 \equiv t_0r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_0 = kr_0$ (car $t_0 = 0$)
$r_0 \equiv t_0r_1 \space (mod \space r_0) \leftrightarrow k = 1$
Donc k existe bien pour $j = 0$.
Donc la propriété est vraie au rang $j = 0$.
Au rang $j = 1$ :
$r_1 \equiv t_1r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_1 = t_1r_1 + kr_0$
$r_1 \equiv t_1r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_1 = r_1 + kr_0$ (car $t_1 = 1$)
$r_1 \equiv t_1r_1 \space (mod \space r_0) \leftrightarrow k = 0$
Donc k existe bien pour $j = 1$.
Donc la propriété est vraie au rang $j = 1$.
On considère que la propriété est vraie aux rangs $j-1$ et $j$. Montrons qu'elle est vraie au rang $j+1$.
$\forall j \in [0;m], r_j \equiv t_jr_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_j = t_jr_1 + kr_0$
$r_{j+1} \equiv t_{j+1}r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_{j+1} = t_{j+1}r_1 + kr_0$
$r_{j+1} \equiv t_{j+1}r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_{j+1} = r_1(t_{j-1} - q_jt_j) + kr_0$
$r_{j+1} \equiv t_{j+1}r_1 \space (mod \space r_0) \leftrightarrow \exists k \in \mathbb{Z} \space / \space r_{j+1} = $
!), tu as compris à quoi servent toutes ces variables, je veux bien que tu m'expliques s'il te plaît 