[pierrot]

En este hilo, el_manco expone el método tradicional para resolver una ecuación diofántica lineal de dos variables de la forma \( ax+by=c \).

¿Cómo se puede generalizar ese algoritmo para el caso de \( n \) variables? ¿Hay alguna forma estándar de proceder en todos los casos? Sé que se ha preguntado ésto muchas veces (sin ir más lejos, en ese mismo hilo que cito), pero aún así agradecería que alguien me lo aclarara. Si es de la forma \( a_1x_1+a_2x_2+\cdots +a_nx_n=b \) lo primero que habría que hacer es chequear que se cumple \( m.c.d.(a_1,a_2,\dots,a_n)|b \). De no pasar ésto, es fácil ver que no puede haber soluciones.

¿Cómo encontrar ahora una solución particular? Sería el algoritmo de Euclides extendido pero para \( n \) enteros. En estas notas, se presenta una interpretación matricial del algoritmo de Euclides y hay un ejercicio que consiste en adaptar el mismo algoritmo para el caso general.

Muchas gracias.

[pierrot]

¿Alguna idea?

Pensando de manera análoga al caso \( n=2 \), habría que construir \( n \) sucesiones \( \{x_1^{(j)}\},\{x_2^{(j)}\},\dots, \{x_n^{(j)}\} \) tal que:

\( R_0=\left(\begin{array}{cccc}
x_1^{(0)}& x_1^{(1)} &\cdots & x_1^{(n)}\\
x_2^{(0)}& x_2^{(1)}  & \cdots & x_2^{(n)} \\
\vdots & \vdots & \ddots & \vdots \\
x_n^{(0)}& x_n^{(1)} & \cdots & x_n^{(n)}\\
\end{array}\right)=I_{n\times n} \)

Luego, hay que determinar los demás términos para que en cada iteración se cumpla \( a_1x_1^{(i)}+a_2x_2^{(i)}+\cdots+a_nx_n^{(i)}=r_i \), ¿pero cuál sería ese \( r_i \)? El último \( r_i \), pongamos en el paso \( k \), nos tiene que dar \( r_k=m.c.d.(a_1,a_2,\cdots, a_n) \) y por cómo están construidas las sucesiones la n-upla \( (x_1^{(k)},x_2^{(k)},\dots ,x_n^{(k)}) \) debiera satisfacer la ecuación diofántica original.

¿Alguna ayuda? Independientemente del ejercicio, ¿qué manera simple hay de resolver ecuaciones diofánticas lineales de muchas variables?

[Luis Fuentes]

Hola

 Para ser sincero no conozco la interpretación matricial del algorimo de Euclides. Pero una posible idea para extenderlo a varias variables, es muy sencilla. Te lo cuento para tres números, pero se adapta fácilmente por inducción al caso general.

 En realidad basta tener en cuenta que:

\(  mcd(a_1,a_2,a_3)=mcd((a_1,a_2),a_3) \)

 Entonces por el algortimo clásico encontramos:

\(  b_1a_1+b_2a_2=d_2=mcd(a_1,a_2) \)

\(  c_2d_2+c_3a_3=mcd(d_2,a_3) \)

 Combinando ambas cosas:

\(  b_1c_2a_1+b_2c_2a_2+c_3a_3=mcd(a_1,a_2,a_3) \)

 ¡Y listo!. Ahora no tengo tiempo de mirar la versión en lenguaje matricial, pero esta idea, de fundamento inductivo, debería de ser fácilmente expresable en tal lenguaje.

Saludos.

[pierrot]

En realidad basta tener en cuenta que:

\(  mcd(a_1,a_2,a_3)=mcd((a_1,a_2),a_3) \)

 Entonces por el algortimo clásico encontramos:

\(  b_1a_1+b_2a_2=d_2=mcd(a_1,a_2) \)

\(  c_2d_2+c_3a_3=mcd(d_2,a_3) \)

 Combinando ambas cosas:

\(  b_1c_2a_1+b_2c_2a_2+c_3a_3=mcd(a_1,a_2,a_3) \)

¡Muchas gracias el_manco! No me había dado cuenta de que se podía proceder así. En caso de resolver una ecuación a mano, eso sería lo más práctico ¿no? ¿Y para hallar todas las soluciones de la ecuación general cómo haría? ¿En cada paso voy hallándolas todas? ¿O cómo? En la versión matricial, quedan unos "residuos" que sirven para ese propósito pero todavía no entiendo bien el algoritmo como para implementarlo en el caso general.

Tal vez más adelante trate de explicarlo aquí para el caso \( n=2 \) con algún ejemplo, así puedes ver en qué consiste sin perder tanto tiempo. Seguro que para ti no es difícil hacer la generalización .

Saludos, y muchas gracias.

[DavidDeSantisB]

Hola pierrot, pudiste generalizar el algoritmo de Euclides extendido para encontrar una solución general de una ecuación general de varias variables?