Cómo resolver sistema de equivalencia modular con parámetro
Sistema dado de equivalencias modulares. Encuentra el parámetro natural más pequeño$a$ ese sistema tiene soluciones
$$\begin{cases} x \equiv a \mod 140\\ x \equiv 3 \mod 91\\ x \equiv 2a \mod 39 \end{cases}$$
Por supuesto, la solución será apreciada, pero si no quiere resolver esto, por favor, déme una pista, ni siquiera sé cómo abordar este problema.
Respuestas
No se necesita factorización prima de módulos, solo gcds rápidos. Según el criterio de solubilidad de CRT, un sistema se puede resolver si se puede resolver por pares si cada par es consistente en sus módulos mcd. Comprobemos todas las consistencias de los pares. Para el primer par$\,1,2\,$ el módulo gcd es $\,(140,91) = 7\,$ entonces
$\qquad\qquad\begin{align} x&\equiv a\!\!\!\pmod{\!140}\\ x&\equiv 3\!\!\!\pmod{\!91}\end{align}\,$ $\Rightarrow\, \begin{align} x&\equiv a\!\!\!\pmod{\!7}\\ x&\equiv 3\!\!\!\pmod{\!7}\end{align}\,$ $\Rightarrow\, \color{#c00}{a\equiv 3}\pmod{\!\color{#c00}{7}}$
Por pareja $\,1,3\,$ el módulo gcd $= (140,39)\!=\!1\,$por lo que siempre tiene solución. Por pareja$\,2,3,\,$ exactamente como arriba obtenemos $\bmod \color{#0a0}{13}\!=\!(91,39)\!:\,\ 2a\equiv 3\!\!\underset{\times 7\!\!}\iff \color{#0a0}a\equiv 21\equiv \color{#0a0}8.\,$ Por lo tanto, el sistema se puede resolver si
$$\begin{align} \color{#c00}{a\equiv 3}&\!\!\pmod{\!\color{#c00}7}\\ \color{#0a0}{a\equiv 8}&\!\!\pmod{\color{#0a0}{\!13}}\end{align}\qquad\qquad$$
Con Easy CRT la solución es$\ a\equiv \color{#0a0}8+13\underbrace{\left[\dfrac{\color{#c00}3-\color{#0a0}8}{13}\bmod 7\right]}_{\!\!\!\large \color{#90f}{-5/(-1)}\ \bmod 7}\equiv 8+13[\color{#90f}5]\equiv 73\pmod{\!7\cdot 13}$
Observación $ $Debido a que este método usa solo gcds (frente a factorizaciones primas), se puede hacer de manera eficiente (a máquina o manual) para módulos enormes , lo que no sería posible usando factorizaciones primas, ya que actualmente no se conoce un algoritmo eficiente para calcular las factorizaciones primas, pero hay uno para gcds: el algoritmo euclidiano.
$$x\equiv a\pmod{4,7,5}$$
$$x\equiv3\pmod{7,13}$$
$$x\equiv2a\pmod{3,13}$$
Entonces, $a\equiv3\pmod7\ \ (1)$
$$2a\equiv3\pmod{13}\equiv13+3$$
$\iff a\equiv8\pmod{13} \ \ (2)$
Aplicar el teorema del resto chino en $(1),(2)$
Eche un vistazo al teorema del resto chino
Para tu caso, x = 3 mod 91 = 3para que puedas ver:
3 = a mod 140
3 = 2a mod 39
De donde se obtiene:
a = 3 + 140 * k1
a = (3 + 39 * k2 ) / 2
Ahora el problema parece más simple, ya que solo necesita encontrar el par más pequeño (k1, k2) para el cual:
3 + 140 * k1 = (3 + 39 * k2 ) / 2
Al resolver puedes obtener:
k1 = 33
k2 = 237
a = 4623
PD: perdón por el formato, sigo aprendiendo a mi manera
Si el sistema es consistente, entonces tiene soluciones.
Ya que $140=4\cdot 5\cdot 7$ entonces el primer sistema es equivalente a $$x \equiv a \pmod {4, 5, 7}$$
y de manera similar para las otras congruencias tenemos $x \equiv 3 \pmod{7, 13}$ y $x\equiv 2a \pmod{3,13}$.
Desde el primero tenemos $x\equiv a \pmod{7}$ y desde el segundo $x\equiv 3 \pmod{7}$. Entonces, para que el sistema sea consistente, debemos tener$a\equiv 3 \pmod{7}$.
De manera similar de la segunda y tercera congruencias vemos que $a$ también debe satisfacer $2a\equiv 3\pmod {13}.$ Entonces desde $2^{-1} \equiv 7 \pmod{7}$, multiplicamos la congruencia por $7$ y obtener eso $$14a\equiv a \equiv21\equiv8 \pmod{13}$$
Por tanto, para que el sistema sea coherente, debe satisfacer $$a\equiv 3 \pmod{7}\space(1)$$ $$a \equiv8 \pmod{13}\space(2)$$
Ya que $7$ y $13$ son coprimidos, existen soluciones modulo $7\times13=91$por el CRT .
Desde $(2)$ lo sabemos $a=8+13k_1$ para $k_1\in\mathbb Z$ y sustituyendo en el primero da $$8+13k_1\equiv 3 \pmod{7}$$ $$13k_1\equiv 2 \pmod{7}$$
Entonces $$13\times 6 k_1\equiv k_1\equiv 12\equiv 5 \pmod{7}$$
Así $k_1=5+7k_2$ para $k_2\in\mathbb Z$ y por eso tenemos $a=8+13k_1=8+13(5+7k_2)=73+91k_{2}.$
Por lo tanto $a\equiv 73 \pmod {91}$ y el parámetro natural más pequeño de $a$ es $73$.