MAD: Ecuaciones diofánticas y de congruencias con maxima

Ecuación de congruencias

Recordemos, para resolver la ecuación $aX\equiv b {\pmod {n}}$, $(aX \equiv b (n))$, cuando $\mathbf{mcd}(a,n)=1$, utilizamos bien solución de Bézout, bien la función $\varphi$ de Euler.

Ejemplo: Resolver la ecuación \[7X\equiv 3 {\pmod {103}}\]

(%i5)

ex:eucl_ext(7,103);
if ex[1]<0 then inv:mod(ex[1],103) else inv:ex[1]$
sol:mod(inv*3,103)$
print(«Solución X=»,sol,«(103)»)$

$\begin{matrix} (ex) & [- 44, 3, 1] \\ Solución X= 74 (103) \end{matrix}$

Verifiquémoslo:

(%i6)

mod(7*sol,103);

$\begin{matrix} (%o6) & 3 \end{matrix}$

Ejercicio: Resolver la ecuación de congruencias $3X\equiv 16 \pmod{22}$.

Hemos visto el uso de la función $\varphi$ de Euler. El cálculo de esta función también se puede realizar si sabemos la descomposición de un número entero en sus factores primos:

Si $n\in\mathbb{Z}$ es ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$, entonces \[\varphi (n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)\]

Ejemplo: Utilizar la fórmula anterior para construir un algoritmo que calcule $\varphi(87)$

Sistemas de congruencias

Ejercicio: Resolver el sistema \[\begin{align*}
3X &\equiv 2\pmod{8} \\ 2X&\equiv 1\pmod{5} \end{align*}\]

Tenemos las ecuaciones de congruencia 3X$\equiv$2(mod 8) y 2X$\equiv$1(mod 5):

(%i4)

eq:[[3,2,8],[2,1,5]]$

Resolvamos la ecuaciones de congruencia de forma individual

(%i6)

s:[]$
for i:1 thru 2 do(
   d:eucl_ext(eq[i][1],eq[i][3]),
   s:append(s,[mod(d[1]*eq[i][2],eq[i][3])]),
   print(eq[i][1],«X=»,eq[i][2],«(mod»,eq[i][3],«)-> X=»,s[i],«(mod»,eq[i][3],«)»)
)$

$\begin{matrix} 3 X= 2 (mod 8)\to X= 6 (mod 8) \\ 2 X= 1 (mod 5)\to X= 3 (mod 5) \end{matrix}$

Ahora calculamos los inversos de los respectivos módulos módulo el producto de ellos:

(%i10)

sv:[]$
p:product(eq[i][3],i,1,2)$
for i:1 thru 2 do(
d:eucl_ext(p/eq[i][3],eq[i][3]),
sv:append(sv,[d[1]*p/eq[i][3]])
)$
sv;

$\begin{matrix} (%o10) & [- 15, 16] \end{matrix}$

La solución del sistema será

(%i13)

sm:0$
for i:1 thru 2 do(
sm:sm+s[i]*sv[i]
)$
print(«X=»,mod(sm,p),«(mod»,p, «)»)$

$\begin{matrix} X= 38 (mod 40) \end{matrix}$

Ejercicio: Resolver el sistema \begin{align*}
5&\equiv 3 \pmod{17} \\
2&\equiv 7 \pmod{15} \\
12&\equiv 14\pmod{31} \\
22&\equiv 17\pmod{29} \\
\end{align*}

Tenemos la ecuaciones de congruencia 5X=3(mod 17),2X=7(mod 15), 12X=14(mod 31) y22X=17(mod 29):

(%i4)

eq:[[5,3,17],[2,7,15],[12,14,31],[22,17,29]]$

Resolvamos la ecuaciones de congruencia de forma individual

(%i6)

s:[]$
for i:1 thru length(eq) do(
   d:eucl_ext(eq[i][1],eq[i][3]),
   s:append(s,[mod(d[1]*eq[i][2],eq[i][3])]),
   print(eq[i][1],«X=»,eq[i][2],«(mod»,eq[i][3],«)-> X=»,s[i],«(mod»,eq[i][3],«)»)
)$

$\begin{matrix} 5 X= 3 (mod 17)\to X= 4 (mod 17) \\ 2 X= 7 (mod 15)\to X= 11 (mod 15) \\ 12 X= 14 (mod 31)\to X= 27 (mod 31) \\ 22 X= 17 (mod 29)\to X= 10 (mod 29) \end{matrix}$

Ahora calculamos los inversos de los respectivos módulos módulo el producto de ellos:

(%i10)

sv:[]$
p:product(eq[i][3],i,1,length(eq))$
for i:1 thru length(eq) do(
d:eucl_ext(p/eq[i][3],eq[i][3]),
sv:append(sv,[d[1]*p/eq[i][3]])
)$
sv;

$\begin{matrix} (%o10) & [- 53940, 106981, 81345, 94860] \end{matrix}$

La solución del sistema será

(%i14)

sm:0$
for i:1 thru length(eq) do(
sm:sm+s[i]*sv[i]
)$
sol:mod(sm,p)$
print(«X=»,sol,«(mod»,p, «)»)$

$\begin{matrix} X= 208781 (mod 229245) \end{matrix}$

Veamos que es cierto:

(%i15)

makelist(mod(eq[i][1]*sol–eq[i][2],eq[i][3]),i,1,length(eq));

$\begin{matrix} (%o15) & [0, 0, 0, 0] \end{matrix}$

Ecuación lineal diofántica

El pasado día trabajamos las ecuaciones lineales diofánticas. En particular, abordamos la solución de la ecuación \[ax+by=c.\]

Ejercicio: Sea $v$ la menor de las soluciones positivas de 4x+22y=46, ¿cuál es el valor de [3,-5].v?

Utilicemos el algoritmo extendido de Euclides para determinar el mcd y la solución de Bézout:

(%i2)

d:eucl_ext(4,22);

$\begin{matrix} (d) & [- 5, 1, 2] \end{matrix}$

Veamos si verifica las condiciones y, en su caso, sustiyamos en la fórmula:

(%i3)

if(mod(46,d[3])=0) then (
       print(«Hay solución:»),
       cprima:46/d[3],
       x:d[1]*cprima+22/d[3]*k,
       y:d[2]*cprima–4/d[3]*k,
       print(«x=»,x),
       print(«y=»,y)
   )$

$\begin{matrix} Hay solución: \\ x= 11 k - 115 \\ y= 23 - 2 k \end{matrix}$

Estimemos las soluciones positivas. Primero creamos la función que nos devuelve las soluciones:

(%i4)

sol(i):=[ev(x,k=i),ev(y,k=i)]$

Ahora, consideramos el valor más cercano de la x a cero:

(%i6)

id:floor(115/11)$
makelist(sol(i),i,id,id+2);

$\begin{matrix} (%o6) & [[- 5, 3], [6, 1], [17, - 1]] \end{matrix}$

Respondamos a la pregunta:

(%i7)

[6,1].[3,–5];

$\begin{matrix} (%o7) & 13 \end{matrix}$

Ejercicio: Sea $v$ la menor de las soluciones positivas de 7x-11y=5, ¿cuál es el valor de [3,4].v?

Como necesitamos el mcd y, si hay solución, una solución inicial dada por la solución de Bezout, apliquemos el algoritmo extendido de Euclides

(%i6)

a:7$b:–11$c:5$
d:eucl_ext(a,b);

$\begin{matrix} (d) & [- 3, - 2, 1] \end{matrix}$

El mcd es 1, con lo cual hay solución. Apliquemos la fórmula:

(%i8)

sol(k):=[d[1]*(c/d[3])+b/d[3]*k,d[2]*(c/d[3])–a/d[3]*k]$
sol(k);

$\begin{matrix} (%o8) & [- 11 k - 15, - 7 k - 10] \end{matrix}$

Buscamos una solución positiva, luego

(%i11)

solve(sol(k)[1],k);
p:floor(ev(k,%));
makelist(sol(i),i,p–2,p+2);

$\begin{matrix} (%o9) & [k = - \frac{15}{11}] \end{matrix}$ $\begin{matrix} (p) & - 2 \end{matrix}$ $\begin{matrix} (%o11) & [[29, 18], [18, 11], [7, 4], [- 4, - 3], [- 15, - 10]] \end{matrix}$

Como vemos, k=-2 es el número que marca el cambio de signo en la variable x, y en este caso tambien en la y. Por tanto, la solución que buscamos es

(%i12)

sol(–2).[3,4];

$\begin{matrix} (%o12) & 37 \end{matrix}$

Si la ecuación es de tres variables y tiene solución, el caso más sencillo es cuando tenemos dos coeficientes coprimos. En tal caso, la ecuación plantea una solución paramétrica cuyo parámetro es la variable del coeficiente no coprimo. Es decir, si $m.c.d(a,b)=1$, planteamos la ecuación \[ax+by=n-c\lambda,\] donde designamos $z=\lambda$, la resolvemos como ya conocemos.

Ejercicio: Resolver la ecuación $5x+12y+3z=11$

Ejercicio: Dada la ecuación 7x-2y+9z=10, dar la solución positiva con min{x>0} y min{y>0}

Ejercicio: Sea v$:[x_s,y_s,z_s]$ la solución de la ecuación 5x-15y+22z=32, que cumple min{0<$y_s$<5} y max{0<$z_s$<10}, ¿cuál es el producto de v.[-2,3,4]

Ejercicio: Resolver el sistema 3x+5y-z=12, 2x-3y+4z=3

Ejercicio: Resolver el sistema 7x+2y+3z=5,5x+3y-2z=3