Exercice A25 : Énoncé & Corrigé Détaillé

$\textbf{Représentation matricielle de la division euclidienne:}$
Soit (a,b) deux entiers naturels premiers entre eux. dzns cet exercice on se propose de trouver un couple d'entiers relatifs (x,y) tel que: $ax+by=1$. On a: $a=q_1b+r_1$ Ecrivons sous forme matricielle: $$\begin{pmatrix} a\\b \end{pmatrix} =\begin{pmatrix} q_1&1\\ 1&0 \end{pmatrix} \begin{pmatrix} b\\ r_1 \end{pmatrix}$$

Montrer que: $$\begin{pmatrix} q_1&1\\ 1&0 \end{pmatrix}^{-1}=\begin{pmatrix} 0&1\\ 1&-q_1 \end{pmatrix}$$
En prenant $(a,b)=(49,18),~$ effectuer les divisions euclidiennes successives.
Montrer alors que l'on: $$\begin{pmatrix} 49\\ 18 \end{pmatrix}=\begin{pmatrix} 2&1\\ 1&0 \end{pmatrix} \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}\begin{pmatrix} 2&1\\ 1&0 \end{pmatrix} \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} \begin{pmatrix} 2&1\\ 1&0 \end{pmatrix} \begin{pmatrix} 1\\ 0 \end{pmatrix}$$
Montrer alors que: $$\begin{pmatrix} 1\\ 0 \end{pmatrix}= \begin{pmatrix} 0&1\\ 1&-2 \end{pmatrix} \begin{pmatrix} 0&1\\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1\\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1\\ 1&-2 \end{pmatrix} \begin{pmatrix} 0&1\\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1\\ 1&-2 \end{pmatrix} \begin{pmatrix} 49\\ 18 \end{pmatrix}$$
En déduire que: $$\begin{pmatrix} 1\\ 0 \end{pmatrix}=\begin{pmatrix} 7&-19\\ -12&33 \end{pmatrix}\begin{pmatrix} 49\\ 18 \end{pmatrix}$$
En déduire que $(u,v)=(7,19)$

Remarque:
- On peut démontrer rapidement cette question en vérifiant que : $$\begin{pmatrix} 0&1\\1&-q_1 \end{pmatrix}\times\begin{pmatrix} q_1&1\\1&0 \end{pmatrix}=\begin{pmatrix} 1&0\\0&1 \end{pmatrix}$$
- La notion de déterminant n'est pas au programme.
- Dans ce qui suit on va utiliser une methode simple et intuitive.
Posons: $$\quad Q=\begin{pmatrix} q_1&1\\1&0\end{pmatrix}~~$$ Pour calculer $~~Q^{-1}~~$ on va utiliser ce qui suit:
$$\begin{pmatrix} x'\\\\y'\end{pmatrix}= Q\begin{pmatrix} x\\\\y\end{pmatrix}\Longleftrightarrow \begin{pmatrix} x\\\\y\end{pmatrix}=Q^{-1}\begin{pmatrix} x'\\\\y'\end{pmatrix}$$ $$\begin{cases} x'=q_1x+y\\\\y'=x \\ \end{cases}\Longleftrightarrow \begin{cases} x=0x'+y' \\\\y=x'-q_1y'\end{cases}$$ Ce qui veut dire que: $$Q^{-1}=\begin{pmatrix} 0&1\\1&-q_1 \end{pmatrix}$$
Les divisions euclidienne successives pour $~~(a,b)=(49,18)~~$ donnent: $$\begin{array}{rlllrlr} {\color{magenta}49}&=&2&\times&{\color{magenta}18}&+&{\color{magenta}13}\\ {\color{magenta}18}&=&1&\times& {\color{magenta}13}& +& {\color{magenta} 5}\\ {\color{magenta}13 }&=&2&\times& {\color{magenta}5 } &+& {\color{magenta} 3} \\ {\color{magenta}5 }&=&1&\times&{\color{magenta}3}& +&{\color{magenta}2}\\ {\color{magenta}3}&=&1&\times& {\color{magenta}2}& + &{\color{magenta} 1}\\ {\color{magenta}2}&=&2&\times&{\color{magenta}1}&+&{\color{magenta}0} \end{array}$$
On obtient les matrices $Q_i$ suivantes: $$Q_1=\begin{pmatrix} 2&1\\1&0\end{pmatrix};~Q_2=\begin{pmatrix} 1&1\\1&0\end{pmatrix};~Q_3=\begin{pmatrix} 2 &1\\1&0\end{pmatrix};~Q_4=\begin{pmatrix} 1&1\\1&0\end{pmatrix};~Q_5=\begin{pmatrix} 1&1\\1&0\end{pmatrix}; ~Q_6=\begin{pmatrix}2&1\\1&0\end{pmatrix}$$ Et on a: $$\begin{pmatrix} 49\\18\end{pmatrix}=Q_1 Q_2 Q_3Q_4Q_5 Q_6\begin{pmatrix} 1\\0\end{pmatrix}$$
On obtient à partir de la question précédente: $$\begin{pmatrix} 1\\0\end{pmatrix}=Q_6^{-1}Q_5^{-1}Q_4^{-1}Q_3^{-1}Q_2^{-1}Q_1^{-1}\begin{pmatrix} 49\\18\end{pmatrix}$$
La question 1 ci dessus donne les inverse des des matrices $~~Q_i~~$ ce qui permet d'écrire: $$\begin{pmatrix} 1\\0\end{pmatrix}=\begin{pmatrix} 0&1\\1&-2\end{pmatrix}\begin{pmatrix} 0&1\\1&-1\end{pmatrix}\begin{pmatrix} 0&1\\1&-1\end{pmatrix}\begin{pmatrix} 0 &1\\1&-2\end{pmatrix}\begin{pmatrix} 0&1\\1&-1\end{pmatrix}\begin{pmatrix} 0&1\\1&-2\end{pmatrix}\begin{pmatrix} 49\\18\end{pmatrix}$$ $$\begin{pmatrix} 1\\0\end{pmatrix}=\begin{pmatrix} 7&-19\\-12&33\end{pmatrix}\begin{pmatrix} 49\\8\end{pmatrix}\qquad (Eq.1)$$
La première ligne du calcul matriciel $(~(Eq.1~)$ donne: $${\color{magenta}1}=7\times {\color{magenta}49}-19\times {\color{magenta}18}$$ L'avantage de cette méthode c'est qu'elle donne directement un couple (u,v) solution de l'equation: $$49u-18v=1$$ Et on a: $~(u,v)=(7,19)~$

Énoncé de l'exercice :

Exercices similaires dans Arithmétique