Autor Tema: Diofánticas ax+by=c ó ax+by+cxy=d

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

18 Marzo, 2009, 11:13 am
Leído 2884 veces

JaimeLG

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • Karma: +0/-0
  • Sexo: Masculino
Buenos días,

tengo un par de preguntas:

La primera es que no entiendo cómo se solucionan las ecusciones diofánticas lineales, como por ejemplo x + y = 12.

Se que lo primero que se hace es comprobar que el término a la derecha de la igualdad sea divisible por el mcd de los términos que acompañan a x e y. Como en este caso ese mcd es 1, 1|12. El mcd se buscaría a través del algoritmo de Euclides extendido. A partir de ahí no tengo muy claro cómo seguir. Se que se tiene que aplicar la identidad de Bezout, pero no cómo se hace para llegar a una solución o conjunto de soluciones.

La segunda pregunta y el motivo por el que la pongo aquí es esta:

Tengo varias ecuaciones de la forma Ax + By + 100xy = d, aparentemente diofánticas y tengo menos idea aún sobre cómo resolverlas, si es que se puede hacer de alguna manera que no sea por fuerza bruta, que las de la primera pregunta  :( por razones abvias.

Un ejemplo es este: 10x + 10y + 100xy = 120, que tiene solución única para x = y = 1, ya que todas las soluciones de estas ecuaciones deben ser enteras positivas y x e y > 0.

En primer lugar, divido toda la ecuación por 10, que además es el m.c.d, quedando:
x + y + 10xy = 12

A partir de aquí, me han comentado varias posibilidades. Una idea podría ser poner 10xy = z y así tener
x + y + z = 12, resolviendo como ecuación diofántica de 3 incógnitas. Otra posibilidad sería despejar x o y, pero eso no se si ayuda en algo.

Gracias de antemano por cualquier ayuda que me podáis prestar.

18 Marzo, 2009, 11:45 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 En cuanto a las ecuaciones diofánticas lineales en dos variables:

\(  ax+by=c \)

 lee en detalle el reciente hilo:

http://rinconmatematico.com/foros/index.php?topic=20148.msg81401;topicseen#msg81401

 Si sigues teniendo dudas vuelve a preguntar indicando exactamente en que paso te pierdes.

 En cuanto a las ecuaciones diofánticas del tipo:

\(  ax+by+cxy=d \)

 Puedes proceder así:

 - Multiplicas por \( c \):

\(  acx+bcy+c^2xy=dc \)

 - Ahora puedes escribirla así:

\(  (cx+b)(cy+a)=dc+ab \)

 - Finalmente para cada divisor \( n \) de \( dc+ab \), resuelve:

\(  cx+b=n\quad \Leftrightarrow{}\quad x=\dfrac{n-b}{c} \)

 Comprobando si las soluciones son enteras.

 Por ejemplo para:

\(  x+y+10xy=12 \)

 Tendríamos:

 1) \( 10x+10y+100xy=120 \)

 2) \( (10x+1)(10y+1)=121 \)

 3) Como \( 121=11^2 \), las posibilidades son:

i) \(  10x+1=1 \)

ii) \(  10x+1=-1 \)

iii) \(  10x+1=11 \)

iv) \(  10x+1=-11 \)

v) \(  10x+1=121 \)

vi) \(  10x+1=120 \)

 Termina...

Saludos.

26 Marzo, 2009, 11:23 am
Respuesta #2

JaimeLG

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • Karma: +0/-0
  • Sexo: Masculino
Hola de nuevo,

el link que me indicas no me aclara demasiado sobre la operativa posterior a la aplicación del algoritmo de Euclides. En cualquier caso, creo que mi problema está a la hora de encontrar una solución particular a partir de la que construir el conjunto de todas las soluciones.

En el ejemplo que puse, me quedo en el punto 3, cuando desglosas las posibles soluciones porque en este caso, 121, se obtiene facilmente, ya que es un número muy bajo y además cuadrado perfecto pero digamos que en vez de esa ecuación propongo:

10x + 10y + 100xy = 170

Siguiendo el proceso que me indicaste, tendríamos:

1)  x + y + 10xy = 17, comprobación de que existen soluciones dividiendo por el m.c.d = 10, aunque ahora lo deshagamos.

2) 10x + 10 y + 100xy = 170 => (10x + 1)(10y + 1) = 171

3) En este caso he puesto x = -1 e y = -2 para obtener el 170 pero si x,y deben ser naturales mayores que 0, ¿Cómo sigo hasta encontrar que no existe solución con esas condiciones?

Saludos y gracias.

26 Marzo, 2009, 11:53 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 1) Para la ecuación \( ax+by=c \):

 Si sabes hacer el algortimo de euclides habrás obtenido dos enteros \( n,m \) tales que:

\(  an+bm=m.c.d(a,b) \)

 Como \( c \) debe de ser múltiplo de \( m.c.d(a,b) \) (en otro caso la ecuación no tiene solución) multiplicando por \( c/m.c.d(a,b) \) obtienes:

\(  anc/m.c.d(a,b)+bmc/m.c.d(a,b)=c \)

 de manera que tu solución particular es:

\(  x=\dfrac{nc}{m.c.d(a,b)},\qquad  y=\dfrac{mc}{m.c.d(a,b)} \)

 2) Da igual que \( 121 \) sea cuadrado perfecto. Cuando has llegado a la ecuación de la forma:

\(  (cx+b)(cy+a)=dc+ab \)

 tienes que descomponer \( dc+ab \) en factores primos para hallar todos sus divisores \( n \). ¿Sabes descomponer un número en factores primos?.

 Por ejemplo cuando llegaste a:

\(  (10x+1)(10y+1)=171 \)

 Tendríamos:

\(  171=3^2\cdot 19 \)

 Por tanto los posibles valores de \( 10x+1 \) que debes de estudiar son:

\(  3^0\cdot 19^0=1 \)
\(  3^1\cdot 19^0=3 \)
\(  3^2\cdot 19^0=9 \)
\(  3^0\cdot 19^1=19 \)
\(  3^1\cdot 19^1=57 \)
\(  3^2\cdot 19^1=171 \)

 y los mismos con signo negativo.

Saludos.

06 Abril, 2009, 03:34 pm
Respuesta #4

JaimeLG

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 7
  • Karma: +0/-0
  • Sexo: Masculino
Hola de nuevo,

al final parece que algo en claro he sacado gracias a tu ayuda.

El problema es que se me ocurrió este posible camino para una teoría que intento optimizar y reducir el coste de computación para números de cualquier tamaño. Ahora bien, como podrás imaginar,  si para resolver una ecuación diofántica necesito previamente descomponer en factores primos, no sólo no mejoraría el tiempo de computación sino que intuyo que lo empeoraría bastante porque sólo para esa factorización, utilizando el único método de factorización determinista que conozco, que es el de la criba de erastóstenes o General number field sieve (GNFS) en su versión más moderna, creo que estamos en un orden \( n^\displaystyle\frac{1}{2} \)

Si se te ocurre alguna alternativa, estoy abierto a cualquier idea. Si no, gracias nuevamente porque al menos ya se algo más de matemáticas   ;D

07 Abril, 2009, 08:50 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 mmm.... hasta lo que yo sé ese es el método para resolver la ecuación general que proponías.

 Desconozco cual es el procedimiento computacionalmente más óptimo.

Saludos.