Practica 1: Los Naturales

3.1. El algoritmo de la división

Dado dos enteros, a y b,  a=bq+r con q,r en Z tal que b>0 y 0<=r<b. Veamos  como hacerlo con Mathematica.

division[x_,y_]:=Module[{aux,q,r},
	If[y==0, Print["el divisor debe ser distinto de 0"]];
	If[y<0,aux=-y,aux=y];
	q=Quotient[x,aux];
	r=Mod[x,aux];
	If[y>0,Print[x,"=",q,"*",y,"+",r],Print[x,"=",-q,"*",y,"+",r]]]

division[5,3]

division[-5,3]

division[-5,-3]

division[5,-3]

division[123,-7]

-17 *-7+4

3.2. Máximo Común Divisor.

Algoritmo de Euclides

mcd[a_,b_]:=Module[{x,y,r},
If[y==0,Return[x]];
x=a;y=b;r=Mod[x,y];
While[r!=0,
	x=y;
	y=r;
	r=Mod[x,y]];
Return[y]]

mcd[20,12]

mcd[12,20]

GCD[20,12]

Algoritmo de Euclides Extendido

gcdext[X_,Y_]:=Module[{x,y,q,r,a,b,c,d,a0,b0,lista={}},
If[Y==0,Return[{X,{1,0}}]];
x=X;y=Y;q=Quotient[x,y];r=Mod[x,y];
a=1; b=0;c=0;d=1;AppendTo[lista,{q,r,c,d}];
While[r!=0,
	x=y;y=r;
	a0=a;b0=b;
	a=c;b=d;
	c=a0-q c;d=b0-q d;
	q=Quotient[x,y];
	r=Mod[x,y];
	AppendTo[lista,{q,r,c,d}];
	];
	Return[{y,{c,d},lista}]]

pu=gcdext[28,42]

TableForm[Prepend[pu[[3]],{q,r,u,v}]]

14==-1 28+1 42

ExtendedGCD[28,42]

3.3 Ecuaciones Diofánticas

Definamos la función que me permita resolver ecuaciones de la forma  "ax+by=c" en Z

lineales[a_,b_,c_,variable_]:=Module[{lista,u,v,solup,solucion},
Clear[variable]; (* Para poder devolver una solucion en funcion de una variable*)
lista=ExtendedGCD[a,b];
If[Mod[c,lista[[1]]]!=0,Return["No tiene solución"]];
u=lista[[2,1]];
v=lista[[2,2]];
solup={u c/lista[[1]],v c/lista[[1]]};
solucion={solup[[1]]+b/lista[[1]] variable,solup[[2]]-a/lista[[1]] variable};
Return[solucion]]

Ejemplo: 3x+5y=7

lineales[3,5,7,"z"]

Expand[3 (14+5 z)+ 5 (-7-3 z)]==7

1.  Resuelva las siguientes ecuaciones lineales en Z.
	a)12x-10y=16
	b)12x+6y=5

3.4 Inverso en Zp

inversoZp[x_,p_]:=Module[{mcd},
mcd=ExtendedGCD[x,p];
If[mcd[[1]]!=1,Return["No tiene inverso"]];
Return[Mod[mcd[[2,1]],p]]]

Ejemplo: Inverso de 3 en Z5

inversoZp[3,5]

Mod[3 2,5]

2. Calcular los inversos de los siguientes enteros:
	a)123^-1 en Z257
	b)12^-1 en 140
	c)-3^-1 en Z11

Mathematica posee su propia función inverso en Zp. Para ello utilizamos la función PowerMod[x,exponente,módulo] que calcula x elevado a exponente en Zmodulo. Basta tomar entonces exponente=-1.

3.5. Ecuaciones en congruencias

Ejemplo: 3x ≡7 4

a=3;m=7;b=4;

GCD[a,m]

tienesolucion=(Mod[b,GCD[a,m]]==0)

Podemos calcular la solución de dos formas en este caso, ya que GCD(3,7) es igual a 1, con lo que existe el inverso de 3 en Z7. Asi pues, lo haremos utilizando la función que calcula dicho inverso, operando directamente en Z7 y posteriormente, transformando la ecuación en congruencias en una ecuación lineal como se vió en teoría.

inv=inversoZp[a,m];x=Mod[b inv,m]+m z

Comprobemos que 6 es una solución particular

Mod[6 a,m]

Así pues, la solución general en Z será 6+7 z, con z un número entero.

Recordemos que resolver la ecuación en congruencias ax ≡m b es equivalente a resolver la ecuación lineal ax - m y = b.

x= lineales[a,-m,b,"z"][[1]]

Notemos que -8 en Z7 es 6, con lo la solución anterior es la misma que la obtenida anteriormente.

Ejemplo: 4x ≡6 2

a=4;m=6;b=2;

GCD[a,m]

tienesolucion=(Mod[b,GCD[a,m]]==0)

Observese que como a y m no son coprimos, no existe el inverso de a en Zm, por lo que solo podemos obtar por la segunda solución.

x= lineales[a,-m,b,"z"][[1]]

Mod[-1 a,m]

Notemos que como el GCD(a,m) es 2, la ecuación en congruencias tiene 2 soluciones distintas en Zm. Estas soluciones son:

Mod[-1,m]

Mod[-4,m]

3. Resolver las siguientes ecuaciones en congruencias:
	a) 234 x≡251 15 
	b) 615 x ≡1285 25
	c) 65 x ≡70 7

La siguiente función, basándonos en lo anteriormente descrito, calcula la solución de una congruencia siempre que ésta tenga solución

congruencia[a_,m_,b_,variable_]:=Module[{},
If[Mod[b,GCD[a,m]]!=0,Return["No tiene solución"],
Return[Mod[lineales[a,-m,b,variable][[1,1]],m]+m variable]]]

Veamos algunos ejemplos

congruencia[3,7,4,"z"]

congruencia[234,251,15,"z"]

congruencia[4,6,2,"z"]

congruencia[615,1285,25,"z"]

congruencia[65,70,7,"z"]

3.6. Sistema de congruencias

\(CRA[lista_] := 
      Module[{i, j, n, ai, mi, Mi, Ui, wi, bi}, 
		n = 
          Length[lista]; 
		ai = 
          Table[lista[[i, 1]], {i, 1, 
              n}]; 
		mi = 
          Table[lista[[i, 2]], {i, 1, 
              n}]; 
		Mi = 
          Table[∏\+\(j = 1\)\%i\( Prepend[mi, 
                  1]\)[[j]], {i, 1, 
              n}]; 
		Ui = 
          Table[PowerMod[
              Mi[[i]], \(-1\), 
              mi[[i]]], {i, 1, 
              n}]; 
		wi = {{}}; 
        bi = {ai[[1]]}; 
		Do[
          AppendTo[wi, 
            Mod[\((ai[[i]] - 
                    bi[[i - 
                        1]])\)\ Ui[[
                  i]], 
              mi[[
                i]]]]; 
			AppendTo[bi, 
            bi[[i - 1]] + 
              wi[[
                  i]]\ Mi[[
                  i]]], {i, 2, n}]; 
		Clear[
          t]; 
		Return[{bi[[n]] + 
              mi[\([n]\)]\ Mi[\([n]\)]\ t, ai, mi, Mi, Ui, wi, 
            bi}];]\)

\(\(\(vertabla[
        lista_]\)\(:=\)\(Module[{i, 
          j}, 
		Print["i  ai  mi  Mi  Ui  wi bi"]; 
		Do[
			Print[i, "  ", 
            lista[[2, i]], "   ", 
            lista[[3, i]], "   ", 
            lista[[4, 
              i]], "   ", 
lista[[5, i]], "   ", 
            lista[[6, i]], "   ", 
            lista[[7, i]]], {i, 1, 
            Length[lista[[2]]]}];]\)\(
\)\)\)

Ejemplo: x ≡5 3, x≡4 1

Primero calculamos la solución general para la primera congruencia del sistema.

congruencia[1,5,3,"z"]

A continuación sustituimos dicha solución en la segunda congruencia obteniendo entonces
que 3 -5 z ≡4 1. De este modo tenemos que las ecuaciones en congruencias 
3 -5 z ≡4 1   y -5 z ≡4 2 son equivalentes. Así resolviendo esta segunda habremos resuelto el sistema.

congruencia[-5,4,2,"t"]

Clear[t,x];x=Expand[3 -5 (-2 -4 t)]

Notemos que la solución dada para la segunda congruencia es para la variable z, con lo que sustituyendo esta expresión en la solución de la primera congruencia obtenemos la solución general para x.

Comprobemos, en primer lugar, que podemos aplicar el algortimo del resto chino para solucionar este sistema, es decir, si el mcd de los módulos es 1.

GCD[5,4]==1

tabla=CRA[{{3,5},{1,4}}]

vertabla[tabla]

5. Resuelve los siguientes sistemas de congruencias:
	a) 7 x ≡3 1, 8 -12 x ≡5 -6, 9 x +1 ≡3 5
	b) x ≡2 1, x ≡3 6, x ≡5 7, x ≡11 1
	c) x ≡3 2, 4 x ≡9 5
	d) x ≡4 2, x ≡6 1

6.  Un inversor quiere comprar acciones por un montante total de 537'5 euros. Dicho inversor está interesado en dos compañías cuyas acciones cuestan 2'5 y 6'5 euros respectivamente. Determinar cuantas acciones de cada compañía pudo comprar si invirtió todo el dinero.

7. Tres niñós están jugando en un faro. El primero sube las escaleras de dos en dos, pero al final sólo tiene que subir un escalón. El segundo las sube todas de tres en tres. El tercero baja saltando los tramos que están compuestos por siete escalones cada uno, excepto el último que tiene sólo cinco. ¿Cuántos escalones tienen las escaleras del faro como mínimo?