Ecuaciones diofantinas... Un poco de menelao

<%=Texto%>Las ecuaciones diofánticas son ecuaciones algebraicas con coeficientes enteros en las que solo nos importan las soluciones enteras. Pero eso seguramente ya lo sabes.
Si la ecuación tiene una sola incógnita la búsqueda de raíces es como en cualquier ecuación, lo único que tenemos que hacer es verificar si por es o no un entero.
Las cosa se pone más movida cuando tenemos más de una incógnita. Así lo que en el campo de los reales nos de una indeterminación, dentro de los enteros da interesantes conjuntos de soluciones.
El caso más simple es la ecuación lineal con dos incógnitas:
a x + b y = n (1)
Lo primero que tenemos que notar aquí es que si a y b son ambos múltiplos de un mismo numero, por ejemplo de 5 cualquiera sea por el producto a por será múltiplo de cinco, y también el producto b.y será (con cualquier y) múltiplo de cinco y por supuesto la suma ax+by también será múltiplo de cinco, así que si n no es múltiplo de cinco no hay ninguna solución.
¿Que pasa si n=1?
a x + b y = 1 (2)
Como uno no es múltiplo de nadie es decir no tiene ningún factor, solamente puede haber solución si a con b no tienen ningún factor en común. Esto se expresa diciendo que a y b son coprimos o también podemos decir que el máximo común divisor de a, b es uno mcd(a, b)=1. Es decir que
mcd(a, b)>1 => (2) no tiene solución
¿Será cierta la reciproca?
mcd(a,b)=1 => (2) tiene solución
Si es cierta. El proceso de demostrarlo es el mismo que el del Algoritmo de Euclides. Ojo que evidentemente alguna de las incógnitas por e y tendrá que ser negativa, por lo que ax+by es en realidad una resta.
Lo que ocurre se pude ver mejor con un ejemplo:
Supongamos que tengo que colocar en un tanque un litro de agua y solo dispongo de dos baldes: uno de 5 litros y otro de 3 litros.
Agregando 5 litros y quitando tres puedo obtener dos (ojo puedo poner 2 tanto como quitar 2 ) Pero 3-2=1
Por lo tanto agrego tres. Luego agrego 3 y quito 5.
Es decir que la solución de 3x+5y=1 es x=2 y=1
Puedes probar con cualquier par de coprimos y siempre hay solución.
Partiendo de que :
mcd(a,b)=1 => ax+by=1 tiene solución
Multiplicando por n llegamos a
mcd(a,b)=n => ax+by=n tiene solución
O también
mcd(a,b)=k => ax+by=n tiene solución si n es múltiplo de k
Es decir que sumando o restando por veces a e y veces b puedo llegar a cualquier numero divisible por k= mcd(a, b).
------------------------------
Ejemplo
Si dispongo de baldes de 14 y 21 litros voy a poder medir cualquier cantidad de agua que sea múltiplo de 7 litros.
Hay por allí un problema que supone que solo existen billetes de 3 y 5 euros y se llega a que siempre se pude dar vuelto.
La ecuación homogénea:
ax+by=0 se llama la ecuación homogénea y siempre tiene infinitas soluciones.
La (1) también tiene infinitas soluciones porque si a una solución de la (1) le sumamos una solución de la homogénea obteneos otra solución. En los problemas estas infinitas soluciones suelen reducirse a unas pocas porque se desechan las negativas.
Ejemplo típico La entrada de cine vale 3 los menores y 8 los mayores . Se recaudaron 59.
¿Cuántos menores y cuantos mayores asistieron? No puedo tener asistencia negativa
------------------------------------------------
Espero que esto te sirva de envión para comenzar a investigar el tema. Ojo que no hay que descuidar la base conocimientos de aritmética de los enteros, congruencias, etc.
Te doy algunas direcciones
http://www.matematicas.net/paraiso/temas.php
http://perso.wanadoo.es/ebuitron/apuntes/discreta/md.pdf
---------------------------------------------------
Problemas que se resuelven con el t. de Menelao
No me pedís poco. Prefiero hallar el teorema para el problema que en buscar el problema para el teorema ya que menos que el sea de aplicación directa, no es nada fácil.
Bueno. En general es conveniente considerar el t. de Menelao cuando hay que probar la colinealidad de puntos (así como el t. de Ceva es útil para probar la concurrencia de rectas)
El teorema de Pascal para la circunferencia dice que los puntos de intersección de de los lados opuestos de un hexágono inscripto en una circunferencia son colineales.
Sea ABCDEF el hexágono inscripto y L, M y N los puntos de intersección de AB y DE, de BC y EF y de FA y DC respectivamente.
Se puede probar. De la siguiente manera. Prolongando tres lados no consecutivos del hexágono se determinan un triangulo. Por ejemplo podemos prologar AB CD y EF y se formara un triangulo PQR ( AB contenido en RP, CD contenido en PORQUE, EF contenido en QR ) Este triángulo es atravesado por las rectas que determinan los otros tres lados (rectas BC, CD y DE). En el triangulo PQR aplico el t. de Menelao de cuatro formas distintas :
a) Con los puntos DE, E, L alineados
b) con los puntos B, C, M alineados
c) con los puntos F, A, M alineados
d) con los puntos M, N, L ¿alineados?
Si se cumple
LR/LP*MQ/MR*NP/NQ=1 (3)
Lo estarán y el teorema queda probado.
De a b y c obtengo expresiones del tipo .../...=1
Multiplicando miembro a miembro y simplificando obtengo algo que todavía no es la (3)
pero aplicando el teorema de la potencia de P Q y R con respecto a la circunferencia es
PC PD =PB PA , QD QC=QD QF , RA RB=RD RF
Si con todo esto llego a la (3) el queda probada la colinealidad
Fíjate como el teorema va en los dos sentidos:
En a) b) y c) uso la colinelidad para probar la igualdad y en d) con la igualdad pruebo la colinealidad.
Los detalles te los dejo para que practiques Espero que te sirva, a pesar de que esto funciona sin ningún gráfico, a puro ASCII.