Programa Ecuaciones Diofanticas Y Cambio De Base. Matemáticas Discretas
Enviado por krauserman • 11 de Enero de 2013 • 1.533 Palabras (7 Páginas) • 829 Visitas
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, tiene soluciones 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 y0 son 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//
inicio
escribir (''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 entonces
inst ⇐ 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 es posible 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
...