합동 해결-솔루션의 단계를 이해할 수 없음 [중복]

Question

합동 및 숫자 이론의 새로운 기능

아래는 Joseph H. Silverman : A Friendly Introduction to Number Theory , 4th Edition, chapter 8, page 56 책의 텍스트입니다 .

---

해결하다

$4x\equiv 3 \pmod{19}$

우리는 양쪽에 곱할 것입니다 $5$. 이것은 준다

$20x\equiv 15 \pmod{19}$ - 1 단계

그러나 $20\equiv 1\pmod{19}$, 그래서 $20x\equiv x\pmod{19}$ - 2 단계

따라서 해결책은

$x\equiv 15\pmod{19}$

---

2 단계까지 이해했지만 2 단계의 솔루션에 도달하는 방법을 이해할 수 없습니다.

어떻게

$20x\equiv x \pmod{19}$
~로 이어지다
$x\equiv 15 \pmod{19}$

어디에서 $20$LHS 이동 중? 어떻게 했어$x$ RHS에서 $15$?

Answer 1

여기서 문제는 합동의 기본 속성과 관련이 있다고 생각합니다.

여러 가지 중요한면에서 일치는 평등과 똑같이 작동합니다. 즉, 세 가지 중요한 속성을 충족합니다.

$1)$ 반사적 : $a\equiv a \pmod n$.

$2)$ 대칭 : $a\equiv b \pmod n\iff b\equiv a \pmod n$

$3)$ 전이 : $a\equiv b\pmod n$ 과 $b\equiv c\pmod n$ 암시하다 $a\equiv c \pmod n$.

이들 각각은 일치의 핵심 정의에서 쉽게 따를 수 있습니다.

이 세 가지 속성은 합동을 https://en.wikipedia.org/wiki/Equivalence_relation. 그것은 그 자체로 중요한 개념입니다. 여러면에서 평등으로 작업하는 것과 같은 방식으로 등가 관계로 작업 할 수 있습니다. 그것이 주어진 계산에서 일어나는 일입니다.

이 경우에는 $$20x\equiv x\pmod {19}\quad \&\quad 20x\equiv 15\pmod {19}$$ 대칭 속성과 전이 속성을 결합하면 $x\equiv {15}\pmod {19}$.

하지만 평소처럼 중요한 것은 일반적인 원칙입니다. 이 세 가지 속성은 합동이 매우 유용하고 중요한 이유입니다. 합동이 왜 유지되는지 이해해야합니다.

Answer 2

나는 그것을 강조 할 것이다 $\gcd(5,19)=1$. 이후$5$ 계수에 coprime, 곱하기 $5$솔루션을 변경하지 않으므로이 두 합치는 동일합니다 ¹

$$4x\equiv3\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$$

이제부터 $x\equiv20x\pmod{19}$, 후자는 다음과 같습니다. $x\equiv15\pmod{19}$.

---

여기에있는 의견 (및 다른 답변에 대한)이 이것이 주요 문제임을 명확히 했으므로 마지막 동등성을 자세히 설명하겠습니다. (대칭과 전이성을 자유롭게 사용할 것입니다.)

• $x\equiv20x\pmod{19}$ 과 $20x\equiv15\pmod{19}$ 암시 $x\equiv15\pmod{19}$
• $20x\equiv x\pmod{19}$ $x\equiv15\pmod{19}$ 암시 $20x\equiv15\pmod{19}$
• 그래서 우리는 둘 다 $$20x\equiv15\pmod{19} \Longrightarrow x\equiv15\pmod{19}$$ 과 $$x\equiv15\pmod{19} \Longrightarrow 20x\equiv15\pmod{19}$$ 우리에게 동등성을 제공합니다 $x\equiv15\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$.

---

¹ 예 :

• https://math.stackexchange.com/q/1845718
• https://math.stackexchange.com/q/1752523

---

참고로 다음과 같은 채팅방이 존재한다고 언급하겠습니다. https://chat.stackexchange.com/transcript/12070 과 https://chat.stackexchange.com/transcript/77161. 그리고 또한https://chat.stackexchange.com/transcript/36. 또한보십시오:https://math.meta.stackexchange.com/q/26814#26817. (주로 댓글에서 여러 번 교환 한 것을 보았 기 때문에 언급하고 있습니다. 댓글이 너무 많으면 채팅 토론이 더 적합 할 수 있다는 신호일 수 있습니다.)

Answer 3

잘, $20\equiv 1 \mod 19$ 그래서 $20\cdot x\equiv 1\cdot x\mod 19$.

나머지는 설명 방법입니다. 곱하기 $4x\equiv 3\mod 19$ 으로 $5$ 양쪽에 준다 $20x\equiv 15\mod 19$즉, $x\equiv 15\mod 19$.

Answer 4

여기에서

$$20x\equiv 15 \mod19$$

우리는 그것을 가지고

$$20x=19x+x \implies 20x\equiv x \mod19$$

따라서

$$20x\equiv x\equiv 15 \mod19$$

실제로 정의에 따르면

$$a\equiv b \mod n \iff a-b=kn$$

따라서 $20x\equiv x \mod 19 $ 이후 $20x-x=19x$.

Answer 5

1 단계에서 얻은 관계의 변을 2 단계에서 얻은 관계의 변으로 나눌 수 있습니다.

$\frac{20x}{20x} ≡ \frac {15} x \mod (19)$

⇒ $1 ≡ \frac {15} x \mod (19)$

⇒ $x ≡ 15 \mod (19)$