Ecuaciones diofanticas y cambio de base

INSTITUTO POLITECNICO NACIONAL

Matemáticas Discretas

Practica 2: Ecuaciones Diofanticas y Cambio de Base

Martínez Huitron Gabriel
Pascacio Ruiz Cuauhtémoc
Pérez Pérez José Ricardo

1CV16

24 de mayo de 2012

Ecuaciones Diofánticas

Los problemas a resolver serán definidos por el usuario , el programa decidirá si alguna ecuación de la forma ax+by = c , donde a, b, c ∈ Z, tienesoluciones en los enteros o no.

El usuario ingresara el valor de ax y by asi como el termino independiente, se evaluara si la ecuación tiene o no solución en los enteros a partir de una solución particular.

Sean a, b y c tres números enteros. La ecuación lineal ax + by = c tiene solución entera si, y sólo si el máximo común divisor de a y b divide a c.

Supongamos que los enteros x0 e y0son solución de la ecuación ax + by = c, es decir, ax0 + by0 = c. Pues bien, si d = m.c.d.(a, b), entonces d = m.c.d.(a, b) ⇒ d|a y d|b ⇒ d|ax0 + by0 ⇒ d|c .

Los problemas a resolver seran enteros, y se basara a partir de

supongamos que d = m.c.d.(a, b) es divisor de c. Entonces,

m.c.d.(a, b) = d ⇒ m.c.d. (a/d, b/d) = 1

⇐⇒ ∃p, q ∈ Z : (a/d) p + (b/d)q = 1

⇒ a (cp/d) + b (cq/d) =c

siendo c/d entero ya que, por hipótesis, d es divisor de c. Ahora bastaría tomar

x0 = (cp/d) e y0= (cq/d)

tendremos que

ax0 + by0 = c

los enteros ax0 e by0 son solución de la ecuación.

Pseudocodigo.

Algoritmo ecuaciones Diofánticas.

Variables
entero a,b,c //Enteros de nuestros coeficientes ax,by,c//
entero r = 1,inst,x,y,z //Enteros auxiliares//

inicioescribir (''Introduzca el valor de A'')
leer (a)
escribir (''Introduzca el valor de B'')
leer (b)
escribir (''Introduzca el valor de C'')
leer (c)
escribir (''ax + by + c'')
y ⇐ a
z ⇐ b

Si, a es menor que b Entonces
x ⇐ a
a ⇐ b
b ⇐ x

Mientras (r es distinto de cero)
inst ⇐ a/b
r ⇐ a%b

Si, r es menor que cero entonces
Si, inst es menor que cero entoncesinst ⇐ inst – 1
Si, inst es mayor o igual que cero entonces
inst ⇐ inst +1
r ⇐ a – (b * inst)

a ⇐ b
b ⇐ r

Si, a es menor que cero
a ⇐ a– a
escribir (''MCD de(y,z)= a")
Si, c=a*(c/a)
escribir ("La solución es posible en los enteros, puesto que (y,z)= a y a / c ")
de otro caso
escribir ("La solución no es posible en los enteros, puesto que (y,z)= a y a -/ c ")Código en lenguaje de programación C.

#include<stdio.h>
#include<stdlib.h>
int main(){
int a,b,c;
int r=1;
int inst;
int x,y,z;
printf("Introducir valor de A:\n");
scanf("%d",&a);
printf("Introducir valor de B\n");
scanf("%d",&b);
printf ("Introducir termino independiente:\n");
scanf("%d",&c);
printf("%dx + %dy = %d\n",a,b,c);
y=a;
z=b;if(a<b){
x=a;
a=b;
b=x;
}
while(r!=0){
inst=a/b;
r=a%b;
if(r<0) {
if(inst<0)
inst-=1;
if(inst>=0)
inst+=1;
r=a-(b*inst);
}
a=b;
b=r;
}
if(a<0)
a=-a;
printf("MCD de(%d,%d)= %d\n",y,z,a);
if (c==a*(c/a))
printf("La solucion es posible en los enteros, puesto que (%d,%d)= %d y %d / %d \n",y,z,a,a,c);
else
printf("La solucion no esposible en los enteros, puesto que (%d,%d)= %d y %d -/ %d \n",y,z,a,a,c);
system ("pause");
return 0;
}
Ecuaciones Diofánticas
En este programa el objetivo es verificar si dada la ecuación tiene soluciones en los enteros o no.
Para verificar si existen soluciones posibles en los enteros, se tiene que tomar en cuenta el máximo común divisor de los coeficientes de las variables. Existen doscasos, el primero es que dado el máximo común divisor, este pueda dividir al coeficiente de c, si este es el caso el programa muestra “La solución es posible en los enteros”; de lo contrario “La solución no es posible en los enteros”
En la siguiente ecuación el programa nos indicas que la solución es posible

En el caso de esta ecuación no tiene una solución posible en los enteros

Cambio...