Programa Ecuaciones Diofanticas Y Cambio De Base. Matemáticas Discretas

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)

...