Resolvendo uma congruência - não consigo entender uma etapa da solução [duplicado]
Novo em congruências e teoria dos números
Abaixo está o texto do livro Joseph H. Silverman: Uma introdução amigável à teoria dos números , 4ª edição, capítulo 8, página 56.
Resolver
$4x\equiv 3 \pmod{19}$
vamos multiplicar ambos os lados por $5$. Isto dá
$20x\equiv 15 \pmod{19}$ - Passo 1
Mas $20\equiv 1\pmod{19}$, tão $20x\equiv x\pmod{19}$ - Passo 2
Assim, a solução é
$x\equiv 15\pmod{19}$
Eu entendi até a etapa 2, não consigo entender como alguém chega à solução da Etapa 2.
Como faz
$20x\equiv x \pmod{19}$
leva a
$x\equiv 15 \pmod{19}$
Onde fez o $20$no LHS ir? Como fez$x$ no RHS seja substituído por $15$?
Respostas
Acho que a questão aqui diz respeito às propriedades básicas da congruência.
De muitas maneiras importantes, a congruência se comporta exatamente como a igualdade. Ou seja, ele satisfaz as três propriedades críticas:
$1)$ Reflexivo: $a\equiv a \pmod n$.
$2)$ Simétrico: $a\equiv b \pmod n\iff b\equiv a \pmod n$
$3)$ Transitivo: $a\equiv b\pmod n$ e $b\equiv c\pmod n$ implica $a\equiv c \pmod n$.
Cada um deles segue facilmente a definição central de congruência.
Essas três propriedades, juntas, tornam a congruência um https://en.wikipedia.org/wiki/Equivalence_relation. Essa é uma noção importante por si só ... de muitas maneiras, você pode trabalhar com Relações de Equivalência da mesma forma que trabalha com Igualdade. Isso é o que está acontecendo no cálculo dado.
Neste caso você tem $$20x\equiv x\pmod {19}\quad \&\quad 20x\equiv 15\pmod {19}$$ então combinar a propriedade simétrica e a propriedade transitiva nos leva $x\equiv {15}\pmod {19}$.
Como de costume, porém, o importante é o princípio geral. Essas três propriedades são o motivo pelo qual as congruências são tão úteis e importantes ... certifique-se de entender por que elas são válidas.
Vou enfatizar que $\gcd(5,19)=1$. Desde a$5$ é coprime ao módulo, multiplicando por $5$não muda as soluções, então essas duas congruências são equivalentes 1
$$4x\equiv3\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$$
Agora desde $x\equiv20x\pmod{19}$, o último é equivalente a $x\equiv15\pmod{19}$.
Como os comentários aqui (e as outras respostas) esclareceram que este é o problema principal, deixe-me explicar a última equivalência em detalhes. (Estarei usando livremente simetria e transitividade.)
- $x\equiv20x\pmod{19}$ e $20x\equiv15\pmod{19}$ implica $x\equiv15\pmod{19}$
- $20x\equiv x\pmod{19}$ $x\equiv15\pmod{19}$ implica $20x\equiv15\pmod{19}$
- Então nós temos ambos $$20x\equiv15\pmod{19} \Longrightarrow x\equiv15\pmod{19}$$ e $$x\equiv15\pmod{19} \Longrightarrow 20x\equiv15\pmod{19}$$ o que nos dá a equivalência $x\equiv15\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$.
1 Veja, por exemplo:
- https://math.stackexchange.com/q/1845718
- https://math.stackexchange.com/q/1752523
Como observação lateral, mencionarei que existem salas de bate-papo como https://chat.stackexchange.com/transcript/12070 e https://chat.stackexchange.com/transcript/77161. E também há ohttps://chat.stackexchange.com/transcript/36. Veja também:https://math.meta.stackexchange.com/q/26814#26817. (Estou mencionando isso principalmente porque vi que você teve várias trocas de comentários. Se houver muitos comentários, isso pode ser um sinal de que a discussão no bate-papo pode ser mais adequada.)
Bem, $20\equiv 1 \mod 19$ e entao $20\cdot x\equiv 1\cdot x\mod 19$.
O resto é como você explicou: Multiplicando $4x\equiv 3\mod 19$ por $5$ em ambos os lados dá $20x\equiv 15\mod 19$, ou seja, $x\equiv 15\mod 19$.
Daqui
$$20x\equiv 15 \mod19$$
nós temos isso
$$20x=19x+x \implies 20x\equiv x \mod19$$
Portanto
$$20x\equiv x\equiv 15 \mod19$$
Na verdade, por definição
$$a\equiv b \mod n \iff a-b=kn$$
Portanto $20x\equiv x \mod 19 $ Desde a $20x-x=19x$.
Você pode dividir os lados da relação que resultaram na etapa 1 pelos lados da relação que resultaram na etapa 2:
$\frac{20x}{20x} ≡ \frac {15} x \mod (19)$
⇒ $1 ≡ \frac {15} x \mod (19)$
⇒ $x ≡ 15 \mod (19)$