Autor Tema: Ecuación diofántica lineal: ax+by=c

0 Usuarios y 1 Visitante están viendo este tema.

05 Noviembre, 2009, 04:55 pm
Leído 20251 veces

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,042
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Dada la ecuación:

 \( ax+by=c \)

con \( a,b,c \) enteros se trata de calcular todos los pares de enteros \( (x,y) \) que verifican la ecuación.

Teorema:

 La ecuación \( ax+by=c \) anterior tiene solución si y sólo si \( m.c.d.(a,b) \) divide a \( c. \)

Método sistemático para hallar la solución:

Spoiler
1) Calcular numeros enteros \( x',y' \) tales que \( ax'+by'=m.c.d(a,b) \). Para ello podemos usar el algoritmo extendido de euclides que nos da al mismo tiempo el \( m.c.d(a,b) \) y los números \( x',y' \).

2) Si \( c \) no es múltiplo de \( m.c.d.(a,b) \) no tiene solución.

3) Si \( c \) es múltiplo de \( m.c.d(a,b) \) una solución particular de la ecuación es:

\(  (x_0,y_0)=\left(\dfrac{cx'}{m.c.d(a,b)},\dfrac{cy'}{m.c.d(a,b)}\right) \)

4) La solución general es:

\(  (x,y)=(x_0,y_0)+k\left(\dfrac{b}{m.c.d(a,b)},\dfrac{-a}{m.c.d(a,b)}\right) \)
[cerrar]

Ejemplo I:

Hallar todas las soluciones de la ecuación diofántica \( 12x+10y=6 \).

Spoiler
1) Calculamos el \( m.c.d \) por el algoritmo de euclides:

\( 12=10\cdot 1+2 \)
\( 10=2\cdot 5+0 \)

 de donde \( m.c.d(12,10)=2 \) y \( 12\cdot 1-10\cdot 1=2 \).

2) El término indpendiente \( 6 \) es múltiplo del \( m.c.d=2 \). Por tanto existe solución.

3) Una solución particular de la ecuación es:

\(  (x_0,y_0)=\left(\dfrac{1\cdot 6}{2},-\dfrac{1\cdot 6}{2}\right)=(3,-3) \)

4) La solución general es:

\(  (x,y)=(3,-3)+k\left(\dfrac{10}{2},\dfrac{-12}{2}\right)=(3,-3)+k(5,-6) \) con \( k\in Z \)
[cerrar]

31 Mayo, 2010, 07:56 pm
Respuesta #1

Click

  • Novato
  • Mensajes: 160
  • Karma: +0/-0
  • Sexo: Masculino
Muy interesante, estoy buscando soluciones para este tipo de ecuaciones pero en n variables.
Pude hallar soluciones particulares. Pero no he podido hallar las generales
Quiciera saber si existe una expresión que represente la solución general para ecuaciones diofánticas de n variables?

Saludos

30 Julio, 2011, 04:38 pm
Respuesta #2

Virgi7

  • Nuevo Usuario
  • Mensajes: 4
  • Karma: +0/-0
  • Sexo: Femenino
Al igual que Click me interesa conocer cómo resuelvo una ecuación diofántica con más de dos incógnitas. En realidad algo he leído pero no logro poner en común todas las fuentes. Es decir, por un método hallo cierta solución general pero por otro, una que es diferente. ¿Puede ser que haya distintas maneras de expresar la solución general (como sucede con las ecuaciones dofánticas de dos variables)? ¿Esto depende de con qué solución particular partimos? Me parece que todo depende de eso.

Por ejemplo: al resolver la ecuación x+2y+5z=29 tengo que las soluciones son:
y=5n+2x+2,
z=-2n-x+5; con n entero.

Utilizando otro método obtuve:
x=29-2t+5s,
y=t,
z=s;

Y otro:
x=12+15t+2s,
y=-4-5t-s.

07 Agosto, 2012, 04:54 pm
Respuesta #3

teeteto

  • Lathi
  • Mensajes: 2,616
  • Karma: +0/-0
  • Sexo: Masculino
  • Dormirás por una eternidad ¡Despierta!
Para \( n \) variables la cosa funciona del mismo modo porque la Identidad de Bézout se puede generalizar.
Para encontrar la solución particular se puede recurrir también al Algoritmo de Euclides sin más que darse cuenta de que \( $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$ \) y así sucesivamente.

No sé si se habrá aclarado algo el asunto.

Saludos.
Debemos saber...sabremos (David Hilbert)

16 Marzo, 2013, 08:37 pm
Respuesta #4

Hernan_ER

  • Héroe
  • Mensajes: 1,452
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias el_manco. Me sirvió mucho. Estaba leyendo en un libro sobre las ecuaciones diofánticas donde tuve que leer toda la parte de congruencia modulo n anteriormente para que luego sólo mostrara que algunas (no solo lineales) no tenían solución.  Necesitaba saber como hallar las soluciones de las lineales solamente.

Edición: ¿Hay alguna demostración o justificación de por qué sirve el método?

05 Abril, 2013, 12:11 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,097
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Edición: ¿Hay alguna demostración o justificación de por qué sirve el método?

En el punto 1) no hay nada que justificar.

El punto 2) es fácil: si se cumple \( ax+by=c \), es obvio que todo divisor común de a y b divide a c.

El punto 3) lo puedes comprobar sin más que sustituir en la ecuación.

Para el punto 4), si tienes otra solución \( (x,y) \), entonces restando las ecuaciones \( ax+by=c \) y \( ax_0+by_0=c \) obtienes que \( (x-x_0, y-y_0) \) es solución de la ecuación \( ax+by=0 \), luego se trata de resolver esta ecuación. Observa que es equivalente a dividir entre el mcd de a y b, por lo que puedes suponer que a y b son primos entre sí y luego sustituir a y b en la solución por a/mcd(a) y b/mcd(b).

Así pues, se trata de ver que si a y b son primos entre sí, las soluciones de  \( ax+by=0 \) son las de la forma \( k(b,-a) \). Se comprueba sustituyendo que todos los pares de esta forma son solución. Si \( (x,y) \) es una solución arbitraria, llama k = mcd(x,y), y entonces \( (x,y)=k(x_0, y_0) \), donde \( (x_0, y_0) \) es solución con componentes primas entre sí. Ahora, si \( ax_0=-by_0 \), con a y b primos entre sí y \( x_0, y_0 \) también, necesariamente \( x_0\mid b \) y \( b\mid x_0 \), luego \( x_0=\pm b \), e igualmente \( y_0=\pm a \), para que se cumpla la ecuación los signos deben ser opuestos.

06 Abril, 2013, 10:14 pm
Respuesta #6

Hernan_ER

  • Héroe
  • Mensajes: 1,452
  • Karma: +0/-0
  • Sexo: Masculino

29 Julio, 2013, 04:02 am
Respuesta #7

BernardRiemann

  • Nuevo Usuario
  • Mensajes: 8
  • Karma: +0/-0
  • Sexo: Masculino
Acabo de realizar un programa desarrollado en Java que resuelve ecuaciones diofanticas, aquel que este interesado en tenerla, que me escriba. Saludos

17 Septiembre, 2013, 09:06 am
Respuesta #8

kiragoras

  • Nuevo Usuario
  • Mensajes: 5
  • Karma: +0/-0
  • Sexo: Femenino
Las soluciones son enteras, ¿cierto?

Porque respecto a la pregunta de un usuario, para ecuaciones con \( n \) variables, se puede encontrar un caso particular de combinatoria ... pero se discriminan casos,  uno es para soluciones enteras positivas y el otro es para soluciones enteras no negativas...

Saludos.

22 Noviembre, 2014, 02:38 pm
Respuesta #9

numerosprimos

  • Nuevo Usuario
  • Mensajes: 11
  • Karma: +0/-0
  • Sexo: Femenino
Buenas, lo que no entiendo es cómo calcular los números x' y y' que dices. Por ejemplo, en la ecuación 7x-5a=1.
El primer paso es hallar el mcd (7,5) que es igual a 1; y como 1 es múltiplo de 1 pues la ecuación tiene soluciones enteras.
Ahora bien, para calcular la solución particular ¿cómo lo hago?
Me lo he leído todo pero no logro entender cómo hallar esta solución particular.

Muchas gracias.

P.S. Si no recuerdo mal, había un método para calcularla que se basa en realizar una caja pero el problema es que tampoco me acuerdo de cómo se hacía :-\

22 Noviembre, 2014, 06:50 pm
Respuesta #10

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,042
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Buenas, lo que no entiendo es cómo calcular los números x' y y' que dices. Por ejemplo, en la ecuación 7x-5a=1.
El primer paso es hallar el mcd (7,5) que es igual a 1; y como 1 es múltiplo de 1 pues la ecuación tiene soluciones enteras.
Ahora bien, para calcular la solución particular ¿cómo lo hago?
Me lo he leído todo pero no logro entender cómo hallar esta solución particular.

Muchas gracias.

P.S. Si no recuerdo mal, había un método para calcularla que se basa en realizar una caja pero el problema es que tampoco me acuerdo de cómo se hacía :-\

Tienes que usar el algortimo extendido de Eculides. Lo tienes (con ejemplos) descrito aquí:

http://rinconmatematico.com/foros/index.php/topic,26742.0.html

Saludos.

22 Noviembre, 2014, 08:31 pm
Respuesta #11

numerosprimos

  • Nuevo Usuario
  • Mensajes: 11
  • Karma: +0/-0
  • Sexo: Femenino
Muchas gracias, ya lo he entendido.
Saludos.

05 Enero, 2015, 12:34 pm
Respuesta #12

minette

  • Experto
  • Mensajes: 973
  • Karma: +0/-5
  • Sexo: Femenino
Hola

Según el_manco la ecuación \( ax+by=c \) tiene la solución particular siguiente cuando
\( a \) , \( b \) son coprimos:

\( x_0=cx' \) ; \( y_0=cy' \)

sustituyendo

\( acx'+bcy'=c \)

\( ax'+by'=1 \)

esto es imposible salvo que \( x' \) o \( y' \) sean uno positivo y otro negativo.

Y también es necesario que \( a \), \( b \) no sean ambos pares. Lo cual se cumple al ser coprimos.

¿Estáis de acuerdo?

Saludos.

05 Enero, 2015, 12:58 pm
Respuesta #13

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,042
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Según el_manco la ecuación \( ax+by=c \) tiene la solución particular siguiente cuando
\( a \) , \( b \) son coprimos:

\( x_0=cx' \) ; \( y_0=cy' \)

sustituyendo

\( acx'+bcy'=c \)

\( ax'+by'=1 \)

esto es imposible salvo que \( x' \) o \( y' \) sean uno positivo y otro negativo.

Y también es necesario que \( a \), \( b \) no sean ambos pares. Lo cual se cumple al ser coprimos.

¿Estáis de acuerdo?

Si. Aunque no sé si quieres llegar a algún sitio con esa observación.

Saludos.

P.D. Pones "según el_manco"; aclaro que aunque el post es mío, lo que he escrito es la teoría sobre ecuaciones diofánticas lineales que viene en todos los libros que tratan el tema.

05 Enero, 2015, 05:34 pm
Respuesta #14

minette

  • Experto
  • Mensajes: 973
  • Karma: +0/-5
  • Sexo: Femenino
Hola

Gracias el_manco.

Esta puntualización mía la puedo poner en Rincón Matemático y no en cualquier libro sobre las ecuaciones diofánticas.

Rincón Matemático, y para sus foristas, lo considero mejor a cualquier libro sobre el asunto. Además hace posible el diálogo.

Pienso que mi observación no es inútil. Y me ayuda a formarme en el tema.

Ahora otra observación.

La solución general que incluyes es

\( x=x_0+Kb \) ; \( x=cx'+Kb \)
\( y=y_0-Ka \) ; \( y=cy'-Ka \)

También para \( a \), \( b \) coprimos.

Mi pregunta ahora es si la solución general también se puede expresar así:

\( x=cx'-Kb \)
\( y=cy'+Ka \)

Y es equivalente a la anterior.

Saludos.

07 Enero, 2015, 10:08 am
Respuesta #15

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,042
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

La solución general que incluyes es

\( x=x_0+Kb \) ; \( x=cx'+Kb \)
\( y=y_0-Ka \) ; \( y=cy'-Ka \)

También para \( a \), \( b \) coprimos.

Mi pregunta ahora es si la solución general también se puede expresar así:

\( x=cx'-Kb \)
\( y=cy'+Ka \)

Y es equivalente a la anterior.

Si.

Saludos.