11. Números naturales y enteros. Divisibilidad

Ejercicios resueltos

Ejercicio 1.

Utilizando la función Divisors[], escribir un programa que haga lo mismo que PrimeQ[]. Comprobarlo para el 0, 1, 20 y el 71.

Solución:

n = NÚMERO;
If[Length[Divisors[n]] == 2, Print[n,   " es primo"], 
      Print[n,   " no es primo"]]

n = 0;
If[Length[Divisors[n]] == 2, Print[n,   " es primo"], 
      Print[n,   " no es primo"]]

n = 1;
If[Length[Divisors[n]] == 2, Print[n,   " es primo"], 
      Print[n,   " no es primo"]]

n = 20;
If[Length[Divisors[n]] == 2, Print[n,   " es primo"], 
      Print[n,   " no es primo"]]

n = 71;
If[Length[Divisors[n]] == 2, Print[n,   " es primo"], 
      Print[n,   " no es primo"]]

Ejercicio 2.

Definir funciones que calculen el cociente y resto de la división de dos números enteros, corrigiendo así el fallo detectado en el ejemplo 11.2. Comprobar que funciona para 7 y 4, 7 y -4, -7 y 4, -7 y -4.

Solución:

COCIENTE[a_, b_] := 
        If[Sign[b] == -1,  -Quotient[a, -b], 
          Quotient[a, b]];
RESTO[a_, b_] := 
        If[Sign[b] == -1,  Mod[a, -b], 
          Mod[a, b]];

COCIENTE[7, 4]
RESTO[7, 4]

COCIENTE[7, -4]
RESTO[7, -4]

COCIENTE[-7, 4]
RESTO[-7, 4]

COCIENTE[-7, -4]
RESTO[-7, -4]

Ejercicio 3.

Calcular, usando el algoritmo de Euclides, el máximo común divisor y el mínimo común múltiplo de:
	a) 1001 y 452
	b) 1001 y -4004
	c) 1001 y 1
	d) -1001 y -452
Interpretar los resultados obtenidos.

Solución:

a) 1001 y 45

n1 = 1001;
n2 = 45;
a = Abs[n1];
b = Abs[n2];
If[a < b, a = b; b = Abs[n1];];
m = 1;
While[m > 0, 
        m = Mod[a, b]; 
a = b; 
b = 
          m;
];
Print["m.c.d.(", n1, ",", n2, ")=", a]
Print["m.c.m.(", n1, ",", n2, ")=", 
      Abs[(n1*n2)/a]]

Como vemos son primos relativos y el mínimo común múltiplo es el producto de los dos.

b) 1001 y -4004

n1 = 1001;
n2 = -4004;
a = Abs[n1];
b = Abs[n2];
If[a < b, a = b; b = Abs[n1];];
m = 1;
While[m > 0, 
        m = Mod[a, b]; 
a = b; 
b = 
          m;
];
Print["m.c.d.(", n1, ",", n2, ")=", a]
Print["m.c.m.(", n1, ",", n2, ")=", 
      Abs[(n1*n2)/a]]

Observamos que -4004 es múltiplo de 1001.

c) 1001 y 1

n1 = 1001;
n2 = 1;
a = Abs[n1];
b = Abs[n2];
If[a < b, a = b; b = Abs[n1];];
m = 1;
While[m > 0, 
        m = Mod[a, b]; 
a = b; 
b = 
          m;
];
Print["m.c.d.(", n1, ",", n2, ")=", a]
Print["m.c.m.(", n1, ",", n2, ")=", 
      Abs[(n1*n2)/a]]

El 1 es divisor de todos los números enteros.

d) -1001 y 452

n1 = -1001;
n2 = 452;
a = Abs[n1];
b = Abs[n2];
If[a < b, a = b; b = Abs[n1];];
m = 1;
While[m > 0, 
        m = Mod[a, b]; 
a = b; 
b = 
          m;
];
Print["m.c.d.(", n1, ",", n2, ")=", a]
Print["m.c.m.(", n1, ",", n2, ")=", 
      Abs[(n1*n2)/a]]

Como en el primer caso también son primos relativos.

Ejercicio 4.

Calcular la Identidad de Bezout en todos los casos del ejercicio anterior.

Solución:

a) 1001 y 45

Clear[valor1,valor2];
n1=1001;
n2=45;
If[Abs[n1]>Abs[n2], temp=n1; n1=n2; n2=temp];
Signo1=n1/Abs[n1];
Signo2=n2/Abs[n2];
a=Abs[n1];
b=Abs[n2];
If [a<b,a=b;
	b=Abs[n1];
	n3=a;
	n4=b;
];
If[Mod[n2,n1]==0,Valoru=0;Valordev=Signo1;a=b;,
r=1;
cocientes={};
s=0;
While[r>0,
	q=Quotient[a,b];
	r=Mod[a,b];
	a=b;
	b=r;
	s=s+1;
	AppendTo[cocientes,q];
];
listam=Table[0,{i,s}];
listam[[1]]=valor1;
listam[[2]]=valor2;
For [f=3,f<s+1,f++,
listam[[f]]=listam[[f-2]]-(listam[[f-1]]*cocientes[[f-2]])
];
Bezout:=Simplify[listam[[s-1]]-(listam[[s]]*cocientes[[s-1]])];
valor1=1;
valor2=0;
Valoru=Bezout;
valor1=0;
valor2=1;

Valordev=Bezout;
Valoru=Valoru*Signo2;
Valordev=Valordev*Signo1;
]
Print["m.c.d.{",n1,",",n2,"}=",a]
Print["m.c.m.{",n1,",",n2,"}=",(n3*n4)/a]
Print["Identidad de Bezout: ",a," = ",n2,"·(",Valoru,") + ",n1,"·(",Valordev,")."]

b) 1001 y -4004

Clear[valor1,valor2];
n1=1001;
n2=-4004;
If[Abs[n1]>Abs[n2], temp=n1; n1=n2; n2=temp];
Signo1=n1/Abs[n1];
Signo2=n2/Abs[n2];
a=Abs[n1];
b=Abs[n2];
If [a<b,a=b;
	b=Abs[n1];
	n3=a;
	n4=b;
];
If[Mod[n2,n1]==0,Valoru=0;Valordev=Signo1;a=b;,
r=1;
cocientes={};
s=0;
While[r>0,
	q=Quotient[a,b];
	r=Mod[a,b];
	a=b;
	b=r;
	s=s+1;
	AppendTo[cocientes,q];
];
listam=Table[0,{i,s}];
listam[[1]]=valor1;
listam[[2]]=valor2;
For [f=3,f<s+1,f++,
listam[[f]]=listam[[f-2]]-(listam[[f-1]]*cocientes[[f-2]])
];
Bezout:=Simplify[listam[[s-1]]-(listam[[s]]*cocientes[[s-1]])];
valor1=1;
valor2=0;
Valoru=Bezout;
valor1=0;
valor2=1;
Valordev=Bezout;
Valoru=Valoru*Signo2;
Valordev=Valordev*Signo1;
]
Print["m.c.d.{",n1,",",n2,"}=",a]
Print["m.c.m.{",n1,",",n2,"}=",(n3*n4)/a]
Print["Identidad de Bezout: ",a," = ",n2,"·(",Valoru,") + ",n1,"·(",Valordev,")."]

c) 1001 y 1

Clear[valor1,valor2];
n1=1001;
n2=1;
If[Abs[n1]>Abs[n2], temp=n1; n1=n2; n2=temp];
Signo1=n1/Abs[n1];
Signo2=n2/Abs[n2];
a=Abs[n1];
b=Abs[n2];
If [a<b,a=b;
	b=Abs[n1];
	n3=a;
	n4=b;
];
If[Mod[n2,n1]==0,Valoru=0;Valordev=Signo1;a=b;,
r=1;
cocientes={};
s=0;
While[r>0,
	q=Quotient[a,b];
	r=Mod[a,b];
	a=b;
	b=r;
	s=s+1;
	AppendTo[cocientes,q];
];
listam=Table[0,{i,s}];
listam[[1]]=valor1;
listam[[2]]=valor2;
For [f=3,f<s+1,f++,
listam[[f]]=listam[[f-2]]-(listam[[f-1]]*cocientes[[f-2]])
];
Bezout:=Simplify[listam[[s-1]]-(listam[[s]]*cocientes[[s-1]])];
valor1=1;
valor2=0;
Valoru=Bezout;
valor1=0;
valor2=1;
Valordev=Bezout;
Valoru=Valoru*Signo2;
Valordev=Valordev*Signo1;
]
Print["m.c.d.{",n1,",",n2,"}=",a]
Print["m.c.m.{",n1,",",n2,"}=",(n3*n4)/a]
Print["Identidad de Bezout: ",a," = ",n2,"·(",Valoru,") + ",n1,"·(",Valordev,")."]

d) -1001 y 452

Clear[valor1,valor2];
n1=-1001;
n2=452;
If[Abs[n1]>Abs[n2], temp=n1; n1=n2; n2=temp];
Signo1=n1/Abs[n1];
Signo2=n2/Abs[n2];
a=Abs[n1];
b=Abs[n2];
If [a<b,a=b;
	b=Abs[n1];
	n3=a;
	n4=b;
];
If[Mod[n2,n1]==0,Valoru=0;Valordev=Signo1;a=b;,
r=1;
cocientes={};
s=0;
While[r>0,
	q=Quotient[a,b];
	r=Mod[a,b];
	a=b;
	b=r;
	s=s+1;
	AppendTo[cocientes,q];
];
listam=Table[0,{i,s}];
listam[[1]]=valor1;
listam[[2]]=valor2;
For [f=3,f<s+1,f++,
listam[[f]]=listam[[f-2]]-(listam[[f-1]]*cocientes[[f-2]])
];
Bezout:=Simplify[listam[[s-1]]-(listam[[s]]*cocientes[[s-1]])];
valor1=1;
valor2=0;
Valoru=Bezout;
valor1=0;
valor2=1;
Valordev=Bezout;
Valoru=Valoru*Signo2;
Valordev=Valordev*Signo1;
]
Print["m.c.d.{",n1,",",n2,"}=",a]
Print["m.c.m.{",n1,",",n2,"}=",(n3*n4)/a]
Print["Identidad de Bezout: ",a," = ",n2,"·(",Valoru,") + ",n1,"·(",Valordev,")."]

Ejercicio 5.

Resolver las ecuaciones diofánticas ax + by = c en los siguientes casos:
	I. a = 34, b = 238 y c = -68
	II. a = 34, b = -238 y c = 25
	III. a = -1968, b = -25992 y c = 68

Solución:

I. a = 34, b = 238 y c = -68

Paso 1: Aplicamos el programa 11.2.

Clear[valor1,valor2];
n1=34;
n2=238;
If[Abs[n1]>Abs[n2], temp=n1; n1=n2; n2=temp];
Signo1=n1/Abs[n1];
Signo2=n2/Abs[n2];
a=Abs[n1];
b=Abs[n2];
If [a<b,a=b;
	b=Abs[n1];
	n3=a;
	n4=b;
];
If[Mod[n2,n1]==0,Valoru=0;Valordev=Signo1;a=b;,
r=1;
cocientes={};
s=0;
While[r>0,
	q=Quotient[a,b];
	r=Mod[a,b];
	a=b;
	b=r;
	s=s+1;
	AppendTo[cocientes,q];
];
listam=Table[0,{i,s}];
listam[[1]]=valor1;
listam[[2]]=valor2;
For [f=3,f<s+1,f++,
listam[[f]]=listam[[f-2]]-(listam[[f-1]]*cocientes[[f-2]])
];
Bezout:=Simplify[listam[[s-1]]-(listam[[s]]*cocientes[[s-1]])];
valor1=1;
valor2=0;
Valoru=Bezout;
valor1=0;
valor2=1;
Valordev=Bezout;
Valoru=Valoru*Signo2;
Valordev=Valordev*Signo1;
]
Print["m.c.d.{",n1,",",n2,"}=",a]
Print["m.c.m.{",n1,",",n2,"}=",(n3*n4)/a]
Print["Identidad de Bezout: ",a," = ",n2,"·(",Valoru,") + ",n1,"·(",Valordev,")."]

Paso 2: Calculamos k = (c/d) y vemos si es entero.

k = -68/34

Paso 3: Multiplicamos la Identidad de Bezout por el k obtenido en el paso anterior obtenemos una solución de la ecuación diofántica:

x = (1)*k
y = (0)*k

Paso 4: Todas la soluciones enteras para la ecuación serán, para cada t ∈ ℤ:

x = -2 + t  (238/34)

y =  0  - t  (34/34)

II. a = 34, b = -238 y c = 25

Paso 1: Aplicamos el programa 11.2.

Clear[valor1,valor2];
n1=34;
n2=-238;
If[Abs[n1]>Abs[n2], temp=n1; n1=n2; n2=temp];
Signo1=n1/Abs[n1];
Signo2=n2/Abs[n2];
a=Abs[n1];
b=Abs[n2];
If [a<b,a=b;
	b=Abs[n1];
	n3=a;
	n4=b;
];
If[Mod[n2,n1]==0,Valoru=0;Valordev=Signo1;a=b;,
r=1;
cocientes={};
s=0;
While[r>0,
	q=Quotient[a,b];
	r=Mod[a,b];
	a=b;
	b=r;
	s=s+1;
	AppendTo[cocientes,q];
];
listam=Table[0,{i,s}];
listam[[1]]=valor1;
listam[[2]]=valor2;
For [f=3,f<s+1,f++,
listam[[f]]=listam[[f-2]]-(listam[[f-1]]*cocientes[[f-2]])
];
Bezout:=Simplify[listam[[s-1]]-(listam[[s]]*cocientes[[s-1]])];
valor1=1;
valor2=0;
Valoru=Bezout;
valor1=0;
valor2=1;
Valordev=Bezout;
Valoru=Valoru*Signo2;
Valordev=Valordev*Signo1;
]
Print["m.c.d.{",n1,",",n2,"}=",a]
Print["m.c.m.{",n1,",",n2,"}=",(n3*n4)/a]
Print["Identidad de Bezout: ",a," = ",n2,"·(",Valoru,") + ",n1,"·(",Valordev,")."]

Paso 2: Calculamos k=(c/d) y vemos si es entero.

k = 25/34

No es un número entero, por tanto no existe solución entera para la ecuación.

III. a = -1968, b = -25992 y c = 168

Paso 1: Aplicamos el programa 11.2.

Clear[valor1,valor2];
n1=-1968;
n2=-25992;
If[Abs[n1]>Abs[n2], temp=n1; n1=n2; n2=temp];
Signo1=n1/Abs[n1];
Signo2=n2/Abs[n2];
a=Abs[n1];
b=Abs[n2];
If [a<b,a=b;
	b=Abs[n1];
	n3=a;
	n4=b;
];
If[Mod[n2,n1]==0,Valoru=0;Valordev=Signo1;a=b;,
r=1;
cocientes={};
s=0;
While[r>0,
	q=Quotient[a,b];
	r=Mod[a,b];
	a=b;
	b=r;
	s=s+1;
	AppendTo[cocientes,q];
];
listam=Table[0,{i,s}];
listam[[1]]=valor1;
listam[[2]]=valor2;
For [f=3,f<s+1,f++,
listam[[f]]=listam[[f-2]]-(listam[[f-1]]*cocientes[[f-2]])
];
Bezout:=Simplify[listam[[s-1]]-(listam[[s]]*cocientes[[s-1]])];
valor1=1;
valor2=0;
Valoru=Bezout;
valor1=0;
valor2=1;
Valordev=Bezout;
Valoru=Valoru*Signo2;
Valordev=Valordev*Signo1;
]
Print["m.c.d.{",n1,",",n2,"}=",a]
Print["m.c.m.{",n1,",",n2,"}=",(n3*n4)/a]
Print["Identidad de Bezout: ",a," = ",n2,"·(",Valoru,") + ",n1,"·(",Valordev,")."]

Paso 2: Calculamos k=(c/d) y veremos si es entero.

k = 168/24

Paso 3: Multiplicamos la Identidad de Bezout por el k obtenido en el paso anterior

x = (383)*k
y = (-29)*k

Paso 4: Todas la soluciones enteras para la ecuación serán, para cada t ∈ ℤ:

x = 2681 + t ((-25992)/24)

y =  -203 - 
        t ((-1968)/24)

Ejercicio 6.

Si disponesmos de una cubeta con capacidad de 15 litros y otra con capacidad de 24 litros. ¿Es posible obtener exactamente 10 litros combinándolas de alguna manera? ¿y 12 litros? En caso afirmativo explicar cómo lo harías.

Solución:

a) Para responder a la primera pregunta buscamos soluciones enteras de la ecuación 15x + 24y = 10, de forma que seguiremos los pasos de resolución

Paso 1: Aplicamos el programa 11.2. y obtenemos

Clear[valor1, valor2];
n1 = 15;
n2 = 
        24;
If[Abs[n1] > Abs[n2], temp = n1; n1 = n2; 
        n2 = temp];
Signo1 = n1/Abs[n1];
Signo2 = 
        n2/Abs[n2];
a = Abs[n1];
b = 
        Abs[n2];
If[a < b, 
        a = b; 
b = Abs[n1]; 
n3 = 
          a; 
n4 = b;];
If[
      Mod[n2, n1] == 0, Valoru = 0; Valordev = Signo1; a = b;, 
      r = 1; 
cocientes = {}; 
s = 
        0; 
While[r > 0, 
        q = Quotient[a, b]; 
r = 
          Mod[a, b]; 
a = b; 
b = 
          r; 
s = s + 1; 
AppendTo[
          cocientes, q];]; 
listam = 
        Table[0, {i, s}]; 
listam[[1]] = 
        valor1; 
listam[[2]] = 
        valor2; 
For[f = 3, f < s + 1, f++, 
        listam[[f]] = 
          listam[[f - 2]] - (listam[[f - 1]]*
                cocientes[[f - 2]])]; 
Bezout := 
        Simplify[
          listam[[s - 1]] - (listam[[s]]*
                cocientes[[s - 1]])]; 
valor1 = 
        1; 
valor2 = 0; 
Valoru = 
        Bezout; 
valor1 = 0; 
valor2 = 
        1; 
Valordev = Bezout; 
Valoru = 
        Valoru*Signo2; 
Valordev = 
        Valordev*Signo1;]
Print["m.c.d.{", n1, ",", 
      n2, "}=", a]
Print["m.c.m.{", n1, ",", 
      n2, "}=", (n3*n4)/
        a]
Print["Identidad de Bezout: ", a, " = ", 
      n2, "·(", Valoru, ") + ", n1, "·(", 
      Valordev, ")."]
"m.c.d.{"270",\
"-3120"}="30
"m.c.m.{"270",\
"-3120"}="28080
\("Identidad de Bezout: "30" = "\(-3120\)"·("\(-2\)") + "270"·("\(-23\)")."\)

Paso 2: Calculamos k=(c/d) y vemos si es entero.

k = 10/3

como k =(c/d) no es entero, la ecuación no admite solución entera y no es posible obtener 10 litros combinándolas entre las dos.

b) Para responder ahora a la segunda pregunta buscamos soluciones enteras de la ecuación 15x + 24y = 12, de forma que seguiremos los pasos para resolver dicha ecuación:

Paso 1: Aplicamos el programa 11.2. y obtenemos

Clear[valor1, valor2];
n1 = 15;
n2 = 
        24;
If[Abs[n1] > Abs[n2], temp = n1; n1 = n2; 
        n2 = temp];
Signo1 = n1/Abs[n1];
Signo2 = 
        n2/Abs[n2];
a = Abs[n1];
b = 
        Abs[n2];
If[a < b, 
        a = b; 
b = Abs[n1]; 
n3 = 
          a; 
n4 = b;];
If[
      Mod[n2, n1] == 0, Valoru = 0; Valordev = Signo1; a = b;, 
      r = 1; 
cocientes = {}; 
s = 
        0; 
While[r > 0, 
        q = Quotient[a, b]; 
r = 
          Mod[a, b]; 
a = b; 
b = 
          r; 
s = s + 1; 
AppendTo[
          cocientes, q];]; 
listam = 
        Table[0, {i, s}]; 
listam[[1]] = 
        valor1; 
listam[[2]] = 
        valor2; 
For[f = 3, f < s + 1, f++, 
        listam[[f]] = 
          listam[[f - 2]] - (listam[[f - 1]]*
                cocientes[[f - 2]])]; 
Bezout := 
        Simplify[
          listam[[s - 1]] - (listam[[s]]*
                cocientes[[s - 1]])]; 
valor1 = 
        1; 
valor2 = 0; 
Valoru = 
        Bezout; 
valor1 = 0; 
valor2 = 
        1; 
Valordev = Bezout; 
Valoru = 
        Valoru*Signo2; 
Valordev = 
        Valordev*Signo1;]
Print["m.c.d.{", n1, ",", 
      n2, "}=", a]
Print["m.c.m.{", n1, ",", 
      n2, "}=", (n3*n4)/
        a]
Print["Identidad de Bezout: ", a, " = ", 
      n2, "·(", Valoru, ") + ", n1, "·(", 
      Valordev, ")."]
"m.c.d.{"270",\
"-3120"}="30
"m.c.m.{"270",\
"-3120"}="28080
\("Identidad de Bezout: "30" = "\(-3120\)"·("\(-2\)") + "270"·("\(-23\)")."\)

Paso 2: Calculamos k=(c/d) y vemos si es entero.

k = 12/3

Como es entero la ecuacion admite solución, para ello

Paso 3: Multiplicamos la Identidad de Bezout por el k obtenido en el paso anterior

x = (-3)*k
y = (2)*k

Así para obtener los 12 litros, lo hemos conseguido de la forma  12 = 15(-12) + 24(8); es decir, echaremos en primer lugar 8 cubetas de 24 litros y luego quitaremos 12 cubetas de 15 litros.