Como resolver sistema de equivalência modular com parâmetro

Question

Sistema dado de equivalências modulares. Encontre o menor parâmetro natural$a$ aquele sistema tem soluções

$$\begin{cases} x \equiv a \mod 140\\ x \equiv 3 \mod 91\\ x \equiv 2a \mod 39 \end{cases}$$

Claro, a solução será apreciada, mas se você não quiser resolver isso, por favor, me dê alguma dica, eu nem sei como abordar esse problema

Answer 1

Nenhuma fatoração primária de módulos é necessária - apenas gcds rápidos. Pelo critério de solvabilidade do CRT, um sistema é solucionável se for resolvível aos pares se cada par for consistente com seu módulo. Vamos verificar a consistência de todos os pares. Para o primeiro par$\,1,2\,$ o módulo gcd é $\,(140,91) = 7\,$ então

$\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}}$

Para par $\,1,3\,$ o módulo gcd $= (140,39)\!=\!1\,$então é sempre solucionável. Para par$\,2,3,\,$ exatamente como acima nós temos $\bmod \color{#0a0}{13}\!=\!(91,39)\!:\,\ 2a\equiv 3\!\!\underset{\times 7\!\!}\iff \color{#0a0}a\equiv 21\equiv \color{#0a0}8.\,$ Assim, o sistema é solucionável se

$$\begin{align} \color{#c00}{a\equiv 3}&\!\!\pmod{\!\color{#c00}7}\\ \color{#0a0}{a\equiv 8}&\!\!\pmod{\color{#0a0}{\!13}}\end{align}\qquad\qquad$$

Por Easy CRT a solução é$\ 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}$

Observação $ $Como este método usa apenas gcds (vs. fatorações primárias), ele pode ser feito de forma eficiente (por máquina ou mão) para módulos enormes - o que não seria possível usando fatorações primárias, uma vez que atualmente não há algoritmo eficiente conhecido para calcular fatorações primárias, mas existe um para gcds - o algoritmo euclidiano.

Answer 2

$$x\equiv a\pmod{4,7,5}$$

$$x\equiv3\pmod{7,13}$$

$$x\equiv2a\pmod{3,13}$$

Então, $a\equiv3\pmod7\ \ (1)$

$$2a\equiv3\pmod{13}\equiv13+3$$

$\iff a\equiv8\pmod{13} \ \ (2)$

Aplicar o teorema do resto chinês em $(1),(2)$

Answer 3

Dê uma olhada no Teorema do Remanescente Chinês

Para o seu caso, x = 3 mod 91 = 3você pode ver:

3 = a mod 140
3 = 2a mod 39

De onde você obtém:

a = 3 + 140 * k1
a = (3 + 39 * k2 ) / 2

Agora o problema parece mais simples, pois você só precisa encontrar o par menor (k1, k2) para o qual:

3 + 140 * k1 = (3 + 39 * k2 ) / 2

Ao resolver, você pode obter:

k1 = 33
k2 = 237
a = 4623

PD: desculpe pela formatação, ainda estou aprendendo do meu jeito

Answer 4

Se o sistema for consistente, então ele terá soluções.

Desde a $140=4\cdot 5\cdot 7$ então o primeiro sistema é equivalente a $$x \equiv a \pmod {4, 5, 7}$$

e da mesma forma para as outras congruências que temos $x \equiv 3 \pmod{7, 13}$ e $x\equiv 2a \pmod{3,13}$.

Desde o primeiro temos $x\equiv a \pmod{7}$ e do segundo $x\equiv 3 \pmod{7}$. Portanto, para que o sistema seja consistente, devemos ter$a\equiv 3 \pmod{7}$.

Da mesma forma, a partir da segunda e terceira congruências, vemos que $a$ também deve satisfazer $2a\equiv 3\pmod {13}.$ Então desde $2^{-1} \equiv 7 \pmod{7}$, nós multiplicamos a congruência por $7$ e obter isso $$14a\equiv a \equiv21\equiv8 \pmod{13}$$

Assim, para o sistema ser consistente, ele deve satisfazer $$a\equiv 3 \pmod{7}\space(1)$$ $$a \equiv8 \pmod{13}\space(2)$$

Desde a $7$ e $13$ são co-prime, existe soluções modulo $7\times13=91$pelo CRT .

De $(2)$ nós sabemos isso $a=8+13k_1$ para $k_1\in\mathbb Z$ e substituindo no primeiro dá $$8+13k_1\equiv 3 \pmod{7}$$ $$13k_1\equiv 2 \pmod{7}$$

então $$13\times 6 k_1\equiv k_1\equiv 12\equiv 5 \pmod{7}$$

portanto $k_1=5+7k_2$ para $k_2\in\mathbb Z$ e, portanto, temos $a=8+13k_1=8+13(5+7k_2)=73+91k_{2}.$

Conseqüentemente $a\equiv 73 \pmod {91}$ e o menor parâmetro natural de $a$ é $73$.