Algorithme d'Euclide étendu — Les-mathematiques.net The most powerful custom community solution in the world

Algorithme d'Euclide étendu

Bonjour !

Je me demandais s'il existait une "méthode" de rédiger l'algorithme d'Euclide étendu, de manière à ne pas se tromper ! Je veux dire que quand l'algorithme s'étant sur 5 ou 6 ligne, on commence à pouvoir s'y perdre facilement ! Surtout quand les entiers sont grands...

Merci.

Réponses

  • Bonjour Jona.

    La seule méthode humaine est de faire soigneusement les calculs (bien présenter, laisser de la place entre les étapes, etc.). La meilleure méthode est de le faire faire par un ordinateur (ou une calculette) qui travaille sans se tromper.
    Mais il n'y a pas d'algorithme général de remplacement plus simple (sinon on aurait laissé tomber l'algorithme d'Euclide).

    Sur des nombres, même relativement grands, on y arrive assez facilement. Pour des polynômes de grands degrés, ça devient vite très difficile (entre autres parce que les coefficients peuvent devenir extrêmement grands).

    Cordialement
  • Oui. Sous forme de tableau. Je te livre la méthode tirée du cours d'algèbre que j'avais fait lorsque j'étais en Angleterre. Désolé, j'ai la flemme de traduire.


    Set

    $$r_{-1}=a,r_0=b,r_{i+1}=r_{i-1}-q_i.r_i,$$
    $$u_{-1}=1,u_{0}=0,u_{i+1}=u_{i-1}-q_i .u_i,$$
    $$v_{-1}=0,v_{0}=1,v_{i+1}=v_{i-1}-q_i .v_i.$$

    We then construct an array with 4 columns corresponding to the values $-q_i,r_i,u_i,v_i$, and with rows indexed by integers $i\geq -1$ starting like this:

    $$\begin{array}{cccc} -q_i & r_i & u_i & v_i \cr & a & 1 & 0 \cr & b & 0 & 1\end{array}$$

    We will workout a concrete example to illustrate the procedure at the same time:

    Assume that $a=32, b=7$.

    So we have

    $$\begin{array}{cccc} -q_i & r_i & u_i & v_i \cr & 32 & 1 & 0 \cr & 7 & 0 & 1\end{array}$$

    Notice that the value $q_{-1}$ is not defined.
    The next step is to compute $q_0$. It can be not totally immediate, but it is easy for $R=\zz$ or $K[X]$, and there are some recipes for other rings that we will give later.

    In our example, $32=4\times 7 + 4$, so $q_0=4$.

    Hence the next step gives

    $$\begin{array}{cccc} -q_i & r_i & u_i & v_i \cr & 32 & 1 & 0 \cr -4 & 7 & 0 & 1\end{array}$$

    Now to compute the values $r_1,u_1,v_1$, we multiply all the elements of the last line by the first one, and we add the corresponding elements lying above them.

    For example, the next value of $r_i$ is $-4\times 7+32$, the next value of $u_i$ is $-4\times 0+1$, and the next value of $v_i$ is $-4\times 1+0$. So we get

    $$\begin{array}{cccc} -q_i & r_i & u_i & v_i \cr & 32 & 1 & 0 \cr -4 & 7 & 0 & 1\cr & 4& 1 & -4\end{array}$$

    Now we need to compute the values for the next line. For this we consider, only the two last lines, and we compute the new quotient, that is we divide the two last values of $r_i$.

    In this example, we have to divide $7$ by $4$. So $7=1\times 4 +3$, and the new quotient is $1$.

    Then we get


    $$\begin{array}{cccc} -q_i & r_i & u_i & v_i \cr & 32 & 1 & 0 \cr -4 & 7 & 0 & 1\cr -1 & 4& 1 & -4\end{array}$$

    Now we repeat the previous procedure to compute the new values for the next line.
    The new value for $r_i$ is $-1\times 4 +7$, the new value for $u_i$ is $-1\times 1+0$, and the new value for $v_i$ is $-1\times (-4)+1$.

    Hence we get

    $$\begin{array}{cccc} -q_i & r_i & u_i & v_i \cr & 32 & 1 & 0 \cr -4 & 7 & 0 & 1\cr -1 & 4& 1 & -4\cr & 3 & -1 & 5\end{array}$$

    To find the new quotient, we have to divide $4$ by $3$: $4=1\times 3+1$, so the new quotient is $1$.

    Then we have

    $$\begin{array}{cccc} -q_i & r_i & u_i & v_i \cr & 32 & 1 & 0 \cr -4 & 7 & 0 & 1\cr -1 & 4& 1 & -4\cr -1 & 3 & -1 & 5\end{array}$$

    The new value for $r_i$ is $-1\times 3 +4$, the new value for $u_i$ is $-1\times(-1)+1$, and the new value for $v_i$ is $-1\times 5+(-4)$.

    Then we get


    $$\begin{array}{cccc} -q_i & r_i & u_i & v_i \cr & 32 & 1 & 0 \cr -4 & 7 & 0 & 1\cr -1 & 4& 1 & -4\cr -1 & 3 & -1 & 5\cr & 1 & 2 & -9\end{array}$$

    To find the new quotient, we need to divide $3$ by $1$. But $3=3\times 1+0$, so the new remainder is $0$ and we stop here.

    Hence a h.c.f of $32$ and $7$ is $1$ (the last $r_i$) and we have $u=2$ (the last $u_i$) and $v=-9$ (the last $v_i$).

    Let us check: $32\times 2-7\times(-9)=64-63=1$ !!!
  • Merci pour cet extrait de ton cours !
  • Jolie méthode Greg !

    Et si j'ai bien lu, c'est tout simplement les valeurs des mémoires d'un algorithme de calcul sur ordinateur. Je n'y avais pas pensé (Et pourtant j'ai parfois "fait faire l'ordinateur" à mes étudiants !)

    Cordialement
  • Ca marche aussi pour les polynômes.

    En fait l'idée pratique est toute simple. Pour passer d'une ligne à l'autre. Tu te places dans la colonne "r" et tu regardes les les deux dernières valeurs, puis tu calcules l'opposé du quotient que tu places dans la dernière ligne.

    Ensuite pour calculer les entrées r, u et v de la nouvelle ligne, tu fais toujours le même mouvement dans le tableau. On part de -q, puis on part à droite, on multiplie, on va au-dessus et on additionne.
  • J'ai essayé pour 1243 et 1067.

    On trouve $r_{-1}=1243$ , $r_{0}=1067$

    Ainsi que : $u_{-1}=1$ , $u_0=0$

    Et : $v_{-1}=0$ , $v_0=1$

    Je commence les choses et je trouve $q_0=176$ donc $-q_0=-176$

    Mais après je n'arrive pas à trouver $r_1$ ... Ou du moins je trouve un truc énorme ... (-186549 ...)

    Que trouves-tu ? Est-ce normal ?
  • M'enfin! tu crois vraiment que le quotient de 1243 par 1067 est 176 ????

    Tu as confondu quotient et reste...
  • Cette méthode, c'est l'algorithme de Blankinship sans le dire.
    Elle revient à faire des opérations élémentaires (échange de 2 lignes, multiplication d'une ligne par un entier non nul,
    remplacement d'une ligne par la somme des deux autres) sur les lignes d'une matrice particulière.

    On part de la matrice $\begin{pmatrix} a & 1 & 0 \\ b & 0 & 1 \end{pmatrix}$ et après un nombre fini d'étapes
    on arrive à $\begin{pmatrix} PGCD(a,b) &u &v \\ 0 & *& * \end{pmatrix}$, les nombres $u$ et $v$ vérifiant
    $au+bv = PGCD(a,b)$.

    On peut limiter les calculs en partant de la matrice tronquée $\begin{pmatrix} a & 1 \\ b & 0 \end{pmatrix}$.
    Après un nombre fini d'étapes, on arrivera à $\begin{pmatrix} PGCD(a,b) & u \\ 0 & * \end{pmatrix}$.
    On vérifie que le nombre $v=\frac{PGCD(a,b) - au}{b}$ est entier et on retrouve la relation $au+bv = PGCD(a,b)$.
  • Dans la pratique, on peut remarquer que remplacer une ligne par elle-même plus (ou moins) un multiple
    entier d'une autre ligne, est une succession d'opérations élémentaires (ce qui revient à faire des divisions euclidiennes). On peut alors arriver rapidement au résultat.


    Un exemple pour le calcul de $PGCD(1243,1067)$ et l'existence de deux nombres $u$ et $v$ entiers vérifiant
    $PGCD(1243,1067) = 1243u+1067v$.


    $\begin{pmatrix} 1243 & 1 \\ 1067 & 0 \end{pmatrix}$, puis on fait $L_1-L_2 \rightarrow L_1$ :\\
    $\begin{pmatrix} 176& 1 \\ 1067 & 0 \end{pmatrix} $, puis on fait $L_2 - 6L_1 \rightarrow L_2$ ($6$ est le quotient
    de la division euclidienne $1067$ par $176$) :\\
    $\begin{pmatrix} 176& 1 \\ 11 & -6 \end{pmatrix} $, puis on fait $L_1 - 16L_2 \rightarrow L_1$ :\\
    $\begin{pmatrix} 0& 97\\ 11 & -6 \end{pmatrix} $, puis on échange les deux lignes (pour le plaisir...) :\\
    $\begin{pmatrix}11 & -6 \\ 0& * \end{pmatrix} $. L'algorithme s'arrête et le $PGCD$ se lit comme étant le seul
    coefficient non nul de la première colonne.

    On a $PGCD(1243,1067)=11$. De plus, $u=-6$. On calcule rapidement $v$ en faisant
    $v = \frac{11-1243(-6)}{1067} = \frac{7469}{1067} = 7$.
  • Greg a écrit:
    Tu as confondu quotient et reste...

    Hmm... Oui, en effet... Le quotient $q_0=1$ ...

    Sinon j'aimerais bien comprendre aussi comment ça marche cette méthode avec la matrice... Je vais essayer de chercher : "algorithme de Blankinship" sur le net, je devrais trouver non ?

    Edit : je n'avais pas vu ton dernier message Titou.
  • Un extrait de "Clark", moi aussi j'ai la flemme de traduire ;-)

    In an article in the August-September 1963 issue of the {\em American
    Mathematical Monthly}, W.A. Blankinship\footnote{Thanks to Chris Miller for
    bringing this method to my attention.} gave a simple method to produce the
    integers $s$ and $t$ in Bezout's Lemma and at the same time produce $\gcd(a,b)$:

    Given $a>b>0$ we start with the array
    $$
    \begin{bmatrix} a & 1 & 0 \\ b & 0 & 1
    \end{bmatrix}
    $$ Then we continue to add multiples of one row to another row, alternating
    choice of rows until we reach an array of the form
    $$
    \begin{bmatrix} 0 & x_1 & x_2 \\ d & y_1 & y_2
    \end{bmatrix}
    $$ or
    $$
    \begin{bmatrix} d & y_1 & y_2 \\ 0 & x_1 & x_2
    \end{bmatrix}
    $$ Then $d=\gcd(a,b)=y_1a+y_2b$. [The goal is to get a $0$ in the first column.]

    \begin{Examples} First take $a=35$, $b=15$.
    $$
    \begin{bmatrix} 35 & 1 & 0 \\ 15 & 0 & 1
    \end{bmatrix}
    $$ Note $35=15\cdot 2+5$, hence
    $$ 35+15(-2)=5.
    $$ So we multiply row $2$ by $-2$ and add it to row $1$, getting
    $$
    \begin{bmatrix} 5 & 1 & -2 \\ 15 & 0 & 1
    \end{bmatrix}
    $$ Now $3\cdot 5=15$ or $15+(-3)5=0$, so we multiply row $1$ by $-3$ and add it
    to row $2$, getting
    $$
    \begin{bmatrix} 5 & 1 & -2 \\ 0 & -3 & 7
    \end{bmatrix}.
    $$ Now we can say that
    $$
    \boxed{\gcd(35,15)=5}
    $$ and
    $$
    \boxed{5=1\cdot 35+(-2)\cdot 15.}
    $$

    Let's now consider a more complicated example: Take $a=1876$, $b=365$.
    $$
    \begin{bmatrix} 1876 & 1 & 0 \\ 365 & 0 & 1
    \end{bmatrix}
    $$ Now $1876=365\cdot5+51$ so we add $-5$ times the second row to the first row,
    getting:
    $$
    \begin{bmatrix} 51 & 1 & -5 \\ 365 & 0 & 1
    \end{bmatrix}
    $$ Now $365=51\cdot7+8$, so we add $-7$ times row $1$ to row $2$, getting:
    $$
    \begin{bmatrix} 51 & 1 & -5 \\ 8 & -7 & 36
    \end{bmatrix}
    $$ Now $51=8\cdot 6+3$, so we add $-6$ times row $2$ to row $1$, getting:
    $$
    \begin{bmatrix} 3 & 43 & -221 \\ 8 & -7 & 36
    \end{bmatrix}
    $$ Now $8=3\cdot 2+2$, so we add $-2$ times row $1$ to row $2$, getting:
    $$
    \begin{bmatrix} 3 & 43 & -221 \\ 2 & -93 & 478
    \end{bmatrix}
    $$ Then $3=2\cdot 1+1$, so we add $-1$ times row $2$ to row $1$, getting:
    $$
    \begin{bmatrix} 1 & 136 & -699 \\ 2 & -93 & 478
    \end{bmatrix}
    $$ Finally, $2=1\cdot 2$ so if we add $-2$ times row $1$ to row $2$ we get:
    \begin{equation}
    \begin{bmatrix} 1 & 136 & -699 \\ 0 & -365 & 1876
    \end{bmatrix}. \tag{$\ast$}
    \end{equation} This tells us that
    $$
    \boxed{\gcd(1876,365)=1}
    $$ and
    \begin{equation}
    \boxed{1=136\cdot 1876+(-699)365.} \tag{$\ast\ast$}
    \end{equation} Note that it was not necessary to compute the last two entries
    $-365$ and $1876$ in $(\ast)$. It is a good idea however to check that equation
    $(\ast\ast)$ holds. In this case we have:
    \begin{align*} 136\cdot 1876 &=\ \ 255136 \\
    \underline{(-699)\cdot 365} &=\underline{-255135} \\ &\hspace*{.75in}1
    \end{align*} So it is correct.
    \end{Examples}

    \textbf{Why Blankinship's Method works:} Note that just looking at what happens
    in the first column you see that we are just doing the Euclidean Algorithm, so
    when one element in column $1$ is $0$, the other is, in fact, the $\gcd$. Note
    that at the start we have
    $$
    \begin{bmatrix} a & 1 & 0 \\ b & 0 & 1
    \end{bmatrix}
    $$ and
    \begin{align*} a &=1\cdot a+0\cdot b \\ b &=0\cdot a+1\cdot b.
    \end{align*} One can show that at {\em every} intermediate step
    $$
    \begin{bmatrix} a_1 & x_1 & x_2 \\ b_1 & y_1 & y_2
    \end{bmatrix}
    $$ we always have
    \begin{align*} a_1 &=x_1a+x_2b \\ b_1 &=y_1a+y_2b,
    \end{align*} and the result follows. I will omit the details.
  • Cool :)

    J'adore vraiment cette méthode, car on peut dire qu'elle est "2 en 1" !

    Vous pensez que je peux l'utiliser dans un examen, même si je ne l'ai pas vu dans mon cours ?
  • Je n'ai pas encore lu le cours que tu m'as mis, mais j'ai essayé la méthode pour $177$ et $108$ (j'ai pris au hasard)

    $\begin{pmatrix} 177 & 1 \\ 108 & 0 \end{pmatrix}$

    $\begin{pmatrix} 69 & 1 \\ 108 & 0 \end{pmatrix} \qquad L_1\to L_1-L_2$

    $\begin{pmatrix} 69 & 1 \\ 39 & -1 \end{pmatrix} \qquad L_2\to L_2-L_1$

    $\begin{pmatrix} 30 & 2 \\ 39 & -1 \end{pmatrix} \qquad L_1\to L_1-L_2$

    $\begin{pmatrix} 30 & 2 \\ 9 & -3 \end{pmatrix} \qquad L_2\to L_2-L_1$

    $\begin{pmatrix} 3 & 11 \\ 9 & -3 \end{pmatrix} \qquad L_1\to L_1-L_2$

    $\begin{pmatrix} 3 & 11 \\ 0 & -36 \end{pmatrix} \qquad L_2\to L_2-L_1$

    On a donc : $177\wedge 108=3$. De plus on a : $11\times 177-18\times 108=3$ !

    C'est vraiment très élégant comme méthode je trouve ...

    Mais n'est-ce pas encore plus simple de prendre la matrice $3\times 2$ pour ne pas devoir faire le calcul de $v$ "infaisable" sans calculatrice ? (Je vais essayer pour voir)

    En tout cas merci beaucoup !
  • Bonjour

    Sinon de façon simple j'appelle $a$ et $b$ les deux entiers de départ, et j'exprime chacun des restes de l'algorithme d'Euclide en fonction de $a$ et $b$... Sans remplacer $a$ et $b$ par leur valeur... Ce qui évite que je me perde dans les différents entiers... D'autre part, je procède dans le même sens que l'algorithme d'Euclide, ce qui évite les fastidieuses remontées que l'on voit parfois. Cette méthode se programme très facilement.
    Ainsi par exemple avec les entiers 2892 et 768, je pose $ a = 2892$ et $ b = 768$ et j'écris :
    $2892 = 768 \times 3 + 588$ donc $588 = 2892 - 768 \times 3 = a - 3b $
    $768 = 588 \times 1 + 180$ donc $180 = 768 - 588 \times 1 = b - (a - 3b)= -a + 4b$
    $588 = 180 \times 3 + 48$ donc $48 = 588 - 180 \times 3 = (a - 3b) - 3(-a + 4b) = 4a - 15b$
    $180 = 48 \times 3 + 36$ donc $180 - 48 \times 3 = ( - a + 4b) - 3 (4a - 15b)= - 13a + 49b$
    $48 = 36 \times 1 + 12$ donc $12= 48 - 36 = (4a - 15b) - ( - 13a + 49b) =17a - 64b $
    enfin $36 = 12 \times 3 + 0$
    Le pgcd est bien $12$ et il est exprimé, comme tous les restes intermédiaires en fonction de $a$ et $ b$.

    Je connais l'algorithme précédent utilisant les matrices comme celui de Blankinship.

    A bientôt,

    Christian
  • Salut, pourrais-tu éditer ton message, car il apparait mal ... Merci :)
  • Le même que précédemment, sans latex... car je deviens chèvre... :?

    Bonjour

    Sinon de façon simple j'appelle a et b les deux entiers de départ, et j'exprime chacun des restes de l'algorithme d'Euclide en fonction de a et b... sans remplacer a et b par leur valeur... ce qui évite que je me perde dans les différents entiers... D'autre part, je procède dans le même sens que l'algorithme d'Euclide, ce qui évite les fastidieuses remontées que l'on voit parfois. Cette méthode se programme très facilement.
    Ainsi par exemple avec les entiers 2892 et 768, je pose a = 2892 et b = 768 et j'écris:
    2892 = 768 x 3 + 588 donc 588 = 2892 - 768 x 3 = a - 3b
    768 = 588 x 1 + 180 donc 180 = 768 - 588 x 1 = b - (a - 3b) = -a + 4b
    588 =180 x 3+48 donc 48 = 588 - 180 x 3 = (a - 3b) -3(-a + 4b) = 4a - 15b
    180 = 48 x 3 + 36 donc 180 - 48 x 3 = (-a + 4b) - 3(4a - 15b) = -13a + 49b
    48 = 36 x 1+12 donc 12 = 48 - 36 = (4a - 15b) - (-13a + 49b) =17a - 64b
    enfin 36=12 x 3+0...
    Le pgcd est bien 12 et il est exprimé, comme tous les restes intermédiaires en fonction de a et b. La conclusion est immédiate.

    D'autre part, je connais l'algorithme précédent utilisant les matrices comme celui de Blankinship.

    A bientôt,

    Christian

    PS: beaucoup de "merdouilles" sont apparues dans mes images latex... j'espère que ce n'est plus le cas!
  • Oui, cette méthode a l'avantage d'éviter les erreurs de calcul, de plus, on peut faire des soustractions si on n'a pas envie de faire des divisions euclidiennes, ça produit $u$ et $v$ naturellement... dans le message que je t'ai mis plus haut, tu peux calculer $u$ et $v$ ensemble avec une matrice non carrée.

    Je dirai même plus : cette méthode se généralise pour calculer le PGCD de trois entiers ou plus.

    Partant de 3 entiers $a$, $b$ et $c$, on veut calculer leur PGCD et les entiers $u$, $v$ et $w$ vérifiant
    $PGCD(a,b,c)=au+bv+cw$.


    On part de la matrice $$\begin{pmatrix} a & 1 & 0 & 0 \\ b & 0 & 1 & 0 \\c & 0 & 0 & 1 \end{pmatrix}$$.

    Au bout d'un nombre fini d'opérations élémentaires, il restera :
    $$\begin{pmatrix} PGCD(a,b,c) & u & v & w \\ 0 & * & * & * \\0 & * & * & * \end{pmatrix}$$.

    Bien plus puissant que la méthode dite "associative" qui utilise $PGCD(a,b,c) = PGCD(PGCD(a,b),c)$, les remontées
    etc.
  • Oui, je suis absolument séduit par cet algorithme, vraiment ...! (je n'avais pas pensé au cas où on cherche le pgcd de plus de deux entiers)

    Sinon Christian, ta méthode est sympa aussi. A vrai dire c'est un peu ce genre de rédaction que je souhaitais trouver quand j'ai posté mon message initial.

    Mais je reste définitivement sur l'algorithme de Blankinship ...! Je trouve ça plus clair, et en plus comme ça se généralise pour un pgcd à $n$ arguments ... J'ai une seule question : Pourquoi cet algorithme n'est-il pas expliqué dans mon cours ??! (Après c'est clair qu'on peut pas mettre tout les trucs intéressants existants dans un cours ...)
  • Bonsoir,

    Titou n'utilise que la première ligne de sa matrice. C'est dommage, il n'y a rien à jeter dans cette matrice (c'est comme le cochon, tout est bon).
    Les deux lignes à étoiles forment une base du module des relations entières entre a, b et c, c'est à dire que tout triplet (x,y,z) d'entiers vérifiant ax + by + cz = 0 s'écrit de manière unique comme combinaison linéaire à coefficients entiers des deux lignes étoilées.
    Ceci permet d'ailleurs d'avoir une description complète de l'ensemble des "coefficients de Bézout", autrement dit des triplets (x,y,z) d'entiers tels que ax + by + cz = d : on les obtient tous en ajoutant à la première ligne (u,v,w) une combinaison entière des deux lignes étoilées.
    D'ailleurs, titou devrait dire "... et des entiers (u,v,w) vérifiant..." car il n'y a bien sûr pas unicité.

    Tout ceci a un parfum de forme normale de Hermite.

    Cordialement
  • Voici pour le parfum de forme normale de Hermite (pub gratuite pour Maple)

    12260
  • Salut Zo! Pourrais-tu m'expliquer sur un exemple, car je ne suis pas sûr d'avoir parfaitement compris ce que tu as dit ...

    Par exemple, $57$ et $33$ :

    $\begin{pmatrix} 57 & 1 & 0\\33 & 0 & 1\end{pmatrix}$

    $\begin{pmatrix} 24 & 1 & -1\\33 & 0 & 1\end{pmatrix}\qquad L_1\to L_1-L_2$

    $\begin{pmatrix} 24 & 1 & -1\\9 & -1 & 2\end{pmatrix}\qquad L_2\to L_2-L_1$

    $\begin{pmatrix} 6 & 3 & -5\\9 & -1 & 2\end{pmatrix}\qquad L_1\to L_1-2L_2$

    $\begin{pmatrix} 6 & 3 & -5\\3 & -4 & 7\end{pmatrix}\qquad L_2\to L_2-L_1$

    $\begin{pmatrix} 0 & 11 & -19\\3 & -4 & 7\end{pmatrix}\qquad L_1\to L_1-2L_2$

    $\begin{pmatrix} 3 & -4 & 7\\0 & 11 & -19 \end{pmatrix}\qquad L_1\to L_1-2L_2$

    $\text{pgcd}(57,33)=3$

    et $-4\times 57+7\times 33=3$

    Que puis-je déduire de $0, 11, -19$ ?

    C'est quoi une base du module des relations ?
  • Tes flèches sont à l’envers.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Bonjour,
    Jona a écrit:
    C'est quoi une base du module des relations ?

    Il me semblait avoir expliqué :
    Zo! a écrit:
    Les deux lignes à étoiles forment une base du module des relations entières entre a, b et c, c'est à dire que tout triplet (x,y,z) d'entiers vérifiant ax + by + cz = 0 s'écrit de manière unique comme combinaison linéaire à coefficients entiers des deux lignes étoilées.

    J'essaie d'être plus compréhensible. Le "module des relations entières entre a, b et c" c'est un gros mot pour désigner l'ensemble des solutions entières de l'équation ax + by + cz = 0 à trois inconnues x,y,z. On cherche à trouver des solutions de cette équation qui engendrent toutes les autres, exactement comme on cherche en algèbre linéaire une base de l'espace vectoriel des solutions d'un système d'équations linéaires homogènes - sauf qu'ici on travaille exclusivement sur les entiers.
    On parle dans cette situation de module et pas d'espace vectoriel, mais ça recouvre des propriétés similaires : la somme de deux triplets solutions est un triplet solution, le produit d'un triplet solution par un entier est encore un triplet solution.

    Dans l'exemple que tu as calculé, c'est assez trivial : la deuxième ligne est (11,-19) (tu remarqueras que dans la situation de trois entiers, je ne considère que les "étoiles", sans prendre en compte le 0 du début). Or il est facile de voir que les couples d'entiers (x,y) qui vérifient 57x + 33y = 0 sont exactement les couples de la forme s (11,-19), pour s entier.

    Ca devient intéressant à partir de trois entiers, comme dans l'exemple traité avec Maple. La sortie du calcul dit que les triplets d'entiers (x,y,z) qui vérifient l'équation 221442 x + 1070745 y + 108290 z =0 sont exactement les triplets de la forme s (5, 2, -30) + t (160, -34, 9) avec s et t entiers (et en plus, cette écriture est unique).

    Un petit exercice : peux-tu trouver une base du module des solutions entières de 2x + 3y + 5z = 0 ?

    Cordialement.
  • $\begin{pmatrix} 2 & 1 & 0 &0 \\ 3 & 0 & 1 & 0 \\ 5 & 0 & 0 & 1\end{pmatrix}$
    $\begin{pmatrix} 2 & 1 & 0 &0 \\ 1 & -1 & 1 & 0 \\ 1 & -2 & 0 & 1\end{pmatrix}\qquad L_2-L_1 \to L2,~L3-2L1 \to L3$
    $\begin{pmatrix} 1 & 2 & -1 &0 \\ 0 & 1 & 1 & -1 \\ 1 & -2 & 0 & 1\end{pmatrix}\qquad L1-L2 \to L1,~L2-L3 \to L2$
    $\begin{pmatrix} 1 & 2 & -1 &0 \\ 0 & 1 & 1 & -1 \\ 0 & -4 & 1 & 1\end{pmatrix}\qquad L3-L1 \to L3$
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Ah, je vois, j'ai compris. En somme, ça permet de résoudre une sorte d'équation Diophantienne non ?

    Je vais essayer ton exercice :

    $\begin{pmatrix} 2 & 1 & 0 & 0 \\ 3 & 0 & 1 & 0 \\ 5 & 0 & 0 & 1\end{pmatrix}$

    $\begin{pmatrix} 2 & 1 & 0 & 0 \\ 1 & -1 & 1 & 0 \\ 0 & -1 & -1 & 1\end{pmatrix}\qquad L_3-L_2-L_1\to L_3 \quad \text{et} \quad L_2-L_1\to L_2$

    $\begin{pmatrix} 1 & 2 & -1 & 0 \\ 1 & -1 & 1 & 0 \\ 0 & -1 & -1 & 1\end{pmatrix}\qquad L_1-L_2\to L_1 $

    $\begin{pmatrix} 1 & 2 & -1 & 0 \\ 0 & -3 & 2 & 0 \\ 0 & -1 & -1 & 1\end{pmatrix}\qquad L_2-L_1\to L_2 $

    Donc on a bien évidement : pgcd(2,3,5)=1.

    De plus on a : $2\times 2-3+0\times 5=1$

    Et une base des solutions de : $2x+3y+5z=0$ serait $s(-3,2,0)$... Après si on veut "inclure" du $z$ on peut aussi prendre comme famille génératrice : $s(-4,2,1)$, mais est-ce encore une base ...? Non puisque la famille n'est pas libre n'est-ce pas ?

    Edit : Nicolas m'est passé devant ! En revanche on ne trouve pas la même matrice finale ... D'ailleurs je ne suis pas d'accord avec ta fin : L3 devient L3-L1 ... Tu as dû te tromper non ?
  • Tiens, on n’a pas la même base.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Oui car il me semble que ta dernière opération est fausse.
  • La dernière ou l’avant-dernière ?
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Ah non, j'ai rien dit. (C'est juste qu'on a pas la même façon de présenter l'énonciation d'une combinaison linéaire. Toi tu l'annonce avant de la faire, puis en dessous tu mets la matrice obtenue, moi je mets la matrice obtenue en fonction de la combinaison linéaire faite sur la même ligne Même pas en fait ! Qu'est-ce que je raconte... J'ai tout simplement mal vu...)

    Bref pourquoi on a une base différente ? C'est peut-être moi qui me suis trompé du coup ?
  • Pour moi, la flèche veut dire dans et pas devient.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Ouais.

    En fait si tu fais $L_2+L_3\to L2$ tu trouves la même chose que moi.
  • @Jona :
    1) tu t'es trompé dans ta première opération. La troisième ligne de ta matrice est fausse.
    2)
    Jona a écrit:
    Et une base des solutions de : 2x + 3y + 5z = 0 serait s (-3,2,0)... Après si on veut "inclure" du z on peut aussi prendre comme famille génératrice : s (-4,2,1), mais est-ce encore une base ...? Non puisque la famille n'est pas libre n'est-ce pas ?
    Oh la la! Bouhouhou, suis-je si peu clair que ça? Ou alors peut-être devrais-tu lire avec plus d'attention? Prend modèle sur la résolution d'un système linéaire normal (une base du module des solutions entières va aussi donner une base de l'espace des solutions réelles) Est-ce que tu penses que la phrase encadrée tiendrait debout dans ce contexte?

    Cordialement.
  • $ \begin{pmatrix}1 & 2 & -1 & 0 \\ 0 & -3 & 2 & 0 \\ 0 & -1 & -1 & 1\end{pmatrix}$

    Oui pardon en effet...

    Je ne comprends pas sinon pour la base ...
  • Je vois bien que tu ne comprends pas, mais je pense que tu ne te donnes pas vraiment les moyens de comprendre. Bon, je me mets en colère, excuse-moi.

    Reprenons calmement.

    1) Si je te demande une base de l'espace des solutions de 2x + 3y + 5z =0 dans R3, que réponds-tu?

    2) Dans l'exemple que j'ai traité avec Maple, quelle est la base du module des solutions entières? De combien de vecteurs se compose cette base?

    Après ça, on pourra peut-être repartir sur une bonne base ;)
  • 1) $s(-1,-1,1)$

    2) $s(5,2,-30)$ ...

    Mais dans les deux cas je ne comprends pas à quoi sert l'autre ligne ... Et comment décider quelle ligne on prend pour la base ? (Doit-on faire le calcul ??)
  • Restons calme, restons calme. Non, Jona ne fait pas exprès pour m'embêter.

    Les solutions (x,y,z) de 2x + 3y + 5z =0 dans R3 forment un sous-espace vectoriel de R3. D'accord?
    Quelle est la dimension de ce sous-espace vectoriel?
    De combien de vecteurs de R3 se compose une base de ce sous-espace vectoriel?
    Peux-tu donner une base de ce sous-espace vectoriel?
  • La dimension de ce sous-espace vectoriel est 2.

    Et deux vecteurs le compose...

    Une base serait : $\left(\begin{pmatrix} -3 \\ 2 \\ 0\end{pmatrix},\begin{pmatrix} -1 \\ -1 \\ 1 \end{pmatrix} \right)$
  • Ah, enfin! Est-ce parce que j'écris les vecteurs à 3 composantes en ligne alors que tu les préfères en colonne que tu étais complètement perdu?
    Je continue tout de même à les écrire en ligne, parce que ça consomme moins de LaTeX.
    Donc les vecteurs (-3,2,0) et (-1,-1,1) forment une base de l'espace des solutions réelles de 2x + 3y + 5z = 0. Les vecteurs (-3,2,0) et (-5,0,2) en forment aussi une base (d'accord?).
    Est ce que (-3,2,0) et (-5,0,2) forment une base du module des solutions entières de l'équation?
    Est ce que (-3,2,0) et (-1,-1,1) forment une base du module des solutions entières de l'équation?
  • Ben dites-moi, vous êtes allés bien loin dans tout ça !

    Je vais reprendre l'exercice posé : on cherche à résoudre l'équation $2x+3y+5z = 0$.

    On forme la matrice de Blankinship.

    $$B = \begin{pmatrix} 2 & 1 & 0 & 0 \\3 & 0 & 1 & 0 \\ 5 & 0 & 0 & 1\end{pmatrix}$$

    Faisant des calculs différents, j'ai trouvé :

    $$ L_2 -L_1 \to L_2 \qquad M_1 = \begin{pmatrix} 2 & 1 & 0 & 0 \\1 & -1 & 1 & 0 \\ 5 & 0 & 0 & 1\end{pmatrix}$$

    $$ L_1 \leftrightarrow L_2 \qquad M_2 = \begin{pmatrix} 1 & -1 & 1 & 0 \\ 2 & 1 & 0 & 0 \\ 5 & 0 & 0 & 1\end{pmatrix}$$

    $$ L_2-2L_1 \to L_2 \qquad M_3 = \begin{pmatrix} 1 & -1 & 1 & 0 \\ 0 & 3 & -2 & 0 \\ 5 & 0 & 0 & 1\end{pmatrix}$$

    $$ L_3-5L_1 \to L_3 \qquad M_4 = \begin{pmatrix} 1 & -1 & 1 & 0 \\ 0 & 3 & -2 & 0 \\ 0 & 5 & -5 & 1\end{pmatrix}$$


    La matrice $M_1$ s'obtient en multipliant la matrice $M$ à gauche par la matrice identité de taille $3\times 3$, qui a subi l'opération élémentaire $L_2 -L_1 \to L_2$. En posant $P_1 = \begin{pmatrix} 1 & 0 & 0 \\-1 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}$, on a $P_1 B = M_1$. Remarquer que la matrice $P_1$ est inversible et à coefficients entiers. On a même, explicitement : $P_1^{-1}=
    \begin{pmatrix} 1 & 0 & 0 \\1 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}$.

    De même, en posant $P_2 = \begin{pmatrix} 0 & 1 & 0 \\1 & 0 & 0 \\ 0 & 0 & 1\end{pmatrix}$, on constate
    que $P_2 = P_2^{-1}$ et que $P_2 M_1 = M_2$.

    En posant $P_3 = \begin{pmatrix} 1 & 0 & 0 \\-2 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}$, on constate
    que $P_3^{-1} = \begin{pmatrix} 1 & 0 & 0 \\2 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}$ et que $P_3 M_2 = M_3$.

    En posant $P_4 = \begin{pmatrix} 1 & 0 & 0 \\0 & 1 & 0 \\ -5 & 0 & 1\end{pmatrix}$, on constate
    que $P_4^{-1} = \begin{pmatrix} 1 & 0 & 0 \\0 & 1 & 0 \\ 5 & 0 & 1\end{pmatrix}$ et que $P_4 M_3 = M_4$.



    On a pu écrire que $M_4 = P_4P_3P_2P_1 B$. Cette écriture est très importante.

    Passons maintenant à la résolution proprement dite.



    Analyse. Soit $(x,y,z)\in\Z^3$ tel que $2x+3y+5z = 0$.

    Alors on a l'identité suivante, grâce au produit matriciel :
    $$ \begin{pmatrix} x & y & z \end{pmatrix} B = \begin{pmatrix} 0 & x & y & z \end{pmatrix}.$$

    Ce que l'on écrit :

    $$\begin{pmatrix} x & y & z \end{pmatrix} P_1^{-1}P_2^{-1}P_3^{-1}P_4^{-1}P_4P_3P_2P_1 B = \begin{pmatrix} 0 & x & y & z \end{pmatrix}. $$

    Nos matrices étant à coefficients entiers, il existe $(x',y',z')\in\Z^3$, tel que

    $$\begin{pmatrix} x' & y' & z' \end{pmatrix} = \begin{pmatrix} x & y & z \end{pmatrix} P_1^{-1}P_2^{-1}P_3^{-1}P_4^{-1}.$$

    On en déduit

    $$\begin{pmatrix} x' & y' & z' \end{pmatrix} M_4 = \begin{pmatrix} 0 & x & y & z \end{pmatrix}.$$

    En utilisant les lignes de $M_4$, on écrit :


    $$x' \begin{pmatrix} 1 & -1 & 1 & 0 \end{pmatrix} + y'
    \begin{pmatrix} 0 & 3 & -2 & 0 \end{pmatrix} + z' \begin{pmatrix} 0 & 5 & -5 & 1 \end{pmatrix} =
    \begin{pmatrix} 0 & x & y & z \end{pmatrix}.$$

    L'identification du premier coefficient montre que $x' = 0$ et on obtient

    $$\begin{pmatrix} x & y & z \end{pmatrix} = y'\begin{pmatrix} 3 & -2 & 0 \end{pmatrix}
    + z'\begin{pmatrix} 5 & -5 & 1 \end{pmatrix} .$$

    Synthèse. Soit $(y',z')\in\Z^2$.
    Posons $\begin{pmatrix} x & y & z \end{pmatrix} = y'\begin{pmatrix} 3 & -2 & 0 \end{pmatrix}
    + z'\begin{pmatrix} 5 & -5 & 1 \end{pmatrix} $.

    Alors $$2x+3y+5z = 2(3y'+5z') + 3(-2y'-5z') + 5z' = 10z'-15z'+5z'= 0.$$

    Conclusion. L'ensemble des triplets entiers solutions de l'équation $2x+3y+5z = 0$ est
    exactement $$\left\{ a ( 3 , -2 , 0) + b (5 , -5 , 1), (a,b)\in\Z^2 \right\}.$$






    Je passe aux questions suivantes.



    Est ce que $(-3,2,0)$ et $(-5,0,2)$ forment une base du module des solutions entières de l'équation ?


    NON. Si c'était le cas, la solution $(5,-5,1)$ pourrait s'écrire sous la forme $a(3,-2,0) + b(-5,0,2)$, avec $a$ et $b$
    entiers.

    Mais $(5,-5,1) = \frac{1}{2}(-5,0,2) + \frac{5}{2}(3,-2,0)$, ce qui conduit à

    $$\frac{1}{2}(-5,0,2) + \frac{5}{2}(3,-2,0) = a(3,-2,0) + b(-5,0,2). $$

    L'identification du second coefficient fournit $-5 = -2a$, d'où $a = 2,5$. $a$ n'est pas entier, contradiction.





    Est ce que $(-3,2,0)$ et $(-1,-1,1)$ forment une base du module des solutions entières de l'équation?


    OUI. On constate déjà que $(-3,2,0)$ et $(-1,-1,1)$ sont deux solutions triviales de l'équation $2x+3y+5z = 0$.
    Par conséquent, quels que soient $a$ et $b$ dans $\Z$, $a(-3,2,0) + b(-1,-1,1)$ seront des solutions.


    Avant d'étudier la réciproque, remarquons que

    $$(-3,2,0) = -1(3,-2,0) + 0(5,-5,1)$$

    $$(-1,-1,1) = -2(3,-2,0) + 1(5,-5,1) $$

    Matriciellement, cela s'écrit

    $$ \begin{pmatrix} -3 & 2 & 0 \\ -1 & -1 & 1 \end{pmatrix} = \begin{pmatrix} -1 & 0 \\ -2 & 1 \end{pmatrix}
    \begin{pmatrix} 3 & -2 & 0 \\ 5 & -5 & 1 \end{pmatrix}. $$

    Remarquons que la matrice $\begin{pmatrix} -1 & 0 \\ -2 & 1 \end{pmatrix}$ est inversible, et qu'elle est égale à son inverse ! On peut donc écrire que

    $$ \begin{pmatrix} 3 & -2 & 0 \\ 5 & -5 & 1 \end{pmatrix} = \begin{pmatrix} -1 & 0 \\ -2 & 1 \end{pmatrix} \begin{pmatrix} -3 & 2 & 0 \\ -1 & -1 & 1 \end{pmatrix}.
    $$


    On peut maintenant montrer la réciproque. Soit $(x,y,z)\in\Z^3$ une solution de $2x+3y+5z = 0$.
    D'après les calculs précédents, on a vu qu'il existe
    $(a,b)\in\Z^2$, $$ \begin{pmatrix} x & y & z \end{pmatrix} = \begin{pmatrix} a & b \end{pmatrix} \begin{pmatrix} 3 & -2 & 0 \\ 5 & -5 & 1 \end{pmatrix}$$

    d'où

    $$ \begin{pmatrix} x & y & z \end{pmatrix} = \begin{pmatrix} a & b \end{pmatrix} \begin{pmatrix} -1 & 0 \\ -2 & 1 \end{pmatrix} \begin{pmatrix} -3 & 2 & 0 \\ -1 & -1 & 1 \end{pmatrix} =
    \begin{pmatrix} -a-2b & b \end{pmatrix} \begin{pmatrix} -3 & 2 & 0 \\ -1 & -1 & 1 \end{pmatrix}.$$

    On en déduit
    $(x,y,z) = (-a-2b) (-3,2,0) + b(-1,-1,1)$. Comme $-a-2b\in\Z$,


    les solutions de l'équation sont donc incluses dans le $\Z$-module engendré par
    $(-3,2,0)$ et $(-1,-1,1)$


    Il reste à montrer que $((-3,2,0),(-1,-1,1))$ est $\Z$-libre. En effet :

    soit $(a,b)\in\Z^2$ tel que $$a(-3,2,0) + b(-1,-1,1) = (0,0,0).$$

    Par identification du dernier coefficient, $b=0$. Il reste $a(-3,2,0) = (0,0,0)$, d'où $a=0$.
  • Tout ça pour dire que, la théorie des modules, elle est largement plus difficile. Avec les modules, des règles sur les espaces vectoriels ne s'appliquent plus (si on prend deux modules de même rang, l'un étant inclus dans l'autre, ils ne sont pas forcément égaux !)
  • @titou : je trouve un peu bizarre d'appeler "algorithme de Blankinship" (je n'avais jamais entendu mentionner ce nom) quelquechose qui est un cas particulier de la réduction de Hermite. Précisément, le calcul de la forme normale de Hermite d'une matrice à une seule colonne.
    La source citée pour Blankinship est un article de 1963. Ca faisait belle lurette qu'on connaissait la réduction de Hermite (1822-1901).

    Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!