¿Cómo resuelvo estas preguntas usando ecuaciones diofánticas?

Question

Me han dicho que es más fácil resolver las siguientes 2 preguntas usando ecuaciones diofánticas en lugar de simplemente la prueba y error.

1) Encuentra el entero positivo más pequeño que, al dividirlo por 6, da un residuo de 1 y al dividirlo por 11, da un residuo de 6.

2) ¿Cuál es el entero positivo más pequeño que tiene residuos de 1, 1 y 5 al dividirlo por 3, 5 y 7 respectivamente?

En cuanto a mi progreso, he intentado generalizar estas preguntas como por ejemplo la primera pregunta:

Dado que el entero tiene un residuo de 1 al dividirlo por 6, debe ser de la forma 6m + 1

Por cierto, no tengo conocimiento previo sobre ecuaciones diofánticas y agradecería tanto una breve introducción como una explicación de cómo aplicar este conocimiento a las preguntas anteriores.

¡Gracias! :)

Answer 1

Quizás podríamos decir que utilizando este enfoque se reemplaza la suposición por un poco de modelado y aplicando un algoritmo de solución, por lo que es más sistemático.

Problema 1): De las ecuaciones para las divisiones $$u = 6x+1 =11y+6$$ obtenemos una ecuación lineal diofántica $$6x-11y=5$$ que es el nombre de una ecuación lineal con coeficientes enteros $$ax + by = c$$ donde se buscan soluciones enteras $x$, $y$. Puede no tener solución o tener infinitas soluciones, dependiendo de si $$\gcd(a,b) \,\rvert\, c$$ donde $\gcd(a,b)$ es el máximo común divisor de $a$ y $b.

Aquí $\gcd(6,-11)=1$ y $1$ divide a $5$, por lo que tenemos soluciones.

Una solución particular se puede obtener aplicando el algoritmo de Euclides extendido.

$$\begin{array}{|c|c|c|c|c|} \hline i & q_{i-1} & r_i & s_i & t_i \\ \hline 0 & & 6 & 1 & 0 \\ \hline 1 & & -11 & 0 & 1 \\ \hline 2 & 6:-11 = 0 & 6- 0\cdot (-11) = 6 & 1-0\cdot 0=1 & 0-0\cdot 1=0 \\ \hline 3 & -11:6=-1 & -11 - (-1)\cdot 6 = -5 & 0 -(-1)\cdot 1=1 & 1-(-1)\cdot 0=1\\ \hline 4 & 6:-5=-1 & 6 - (-1) \cdot (-5) = 1 & 1-(-1)\cdot 1=2 & 0-(-1)\cdot 1=1\\ \hline 5 & -5:1=-5 & -5 - 1 \cdot (-5) = 0 & 1-(-5)\cdot 2=11 & 1-(-5)\cdot 1=6\\ \hline \end{array}$$

La fila para $i=4$ da $\gcd(6,-11) = 1$, $s = 2$, $t = 1$. Comprobando: $6\cdot 2 + (-11) \cdot 1 = 1$, OK.

Esto resuelve $$a s + bt = \gcd(a,b) = 1 \Rightarrow a (5s) + b (5t) = 5$$

Así que $(x,y)=(5\cdot 2, 5\cdot 1) = (10,5)$ es una solución particular.

La solución general son todas las soluciones de la ecuación homogénea $$a x + by = 0 = a x - tab + tab + b y = a(x-tb) + b (y + at)$$ para $t \in \mathbb{Z}$ más una solución particular.

Aquí esto da $(10+11t,5+6t)$ para $t \in \mathbb{Z}$ y

$u = 6(10+11t)+1=61-66t$, el más pequeño positivo es $61$.

Problema 2): El segundo ejemplo da $$u = 3x+1 = 5 y + 1 = 7 z + 5$$ Entonces podríamos intentar $$3x-5y=0 \wedge 3x+1=7z+5$$ lo cual da $$y=(3/5)x \wedge 3x-7z=4$$ Esto conduce a $(x,z)=(6+7t,2+3t)$ y $y = (3/5)(6+7t) = (18+21t)/5$ que es un entero para t=2, dando $(x,y,z)=(20,12,8)$ y $u=61$ nuevamente.

WA parece pensar lo mismo (enlace).