동치관계

동치식

• $A\equiv B(\text{mod }C)$‍
• $A\text{ mod }C=B\text{ mod }C$‍
• $C|(A-B)$‍ | 기호는 나누기 또는 ()의 인수라는 뜻입니다.
• $A=B+K\cdot C$‍ ($K$‍는 어떤 정수)

• $13\equiv 23(\text{mod }5)$‍
• $13\text{ mod }5=23\text{ mod }5$‍
• $5|(13-23)$‍, $(5|-10$‍, $\mathbf{5}\times \mathbf{(}\mathbf{-}\mathbf{2}\mathbf{)}\mathbf{=}\mathbf{-}\mathbf{10}$‍이기 때문에 참입니다 $)$‍
• $13=23+K\cdot 5$‍.$\mathbf{K}\mathbf{=}\mathbf{-}\mathbf{2}$‍일 때 성립합니다: $13=23+(-2)\times 5$‍

합동과 모듈의 동치 관계에 대해서 알아봅시다

• 각 조각 안에 있는 값의 쌍은 서로 연관됩니다.
• 같은 값을 둘 이상의 조각에서 찾을 수는 없습니다. (조각은 둘씩 서로 만나지 않습니다)
• 모든 조각을 하나로 합치면 모든 값을 포함하는 파이가 됩니다.

• 파이: 관심이 있는 값을 모두 모은 것
• 파이 한 조각: 동치류
• 파이를 여러 조각으로 자른 것: 동치 관계

• 파이: 모든 정수를 모은 것
• 파이 조각 $B$‍: 모든 값이 $\text{mod }C=B$‍인 동치류
• 파이를 여러 조각으로 자르는 방법: 모듈 C에 대한 합동 관계, $\equiv (\text{mod }C)$‍

모듈 C에 대한 합동 관계가 동치 관계라는 사실이 왜 중요할까요?

• 반사성: A가 A와 관계가 있습니다
• 대칭성: A가 B와 관계가 있다면, B도 A와 관계가 있습니다
• 추이성: A가 B와 관계가 있고, B가 C와 관계가 있다면, A와 C도 관계가 있습니다

• $A\equiv A(\text{mod }C)$‍
• $A\equiv B(\text{mod }C)$‍이면 $B\equiv A(\text{mod }C)입니다$‍
• $A\equiv \mathbf{B}\mathbf{(}\text{mod }\mathbf{C}\mathbf{)}$‍이고 $\mathbf{B}\equiv \mathbf{D}\mathbf{(}\text{mod }\mathbf{C}\mathbf{)}$‍이면 $\mathbf{A}\equiv \mathbf{D}\mathbf{(}\text{mod }\mathbf{C}\mathbf{)}$‍입니다

예제

• $3\equiv 3(\text{mod }5)$‍ (반사성)
• $3\equiv 8(\text{mod }5)$‍이면 $8\equiv 3(\text{mod }5)$‍입니다 (대칭성)
• $3\equiv 8(\text{mod }5)$‍이고 $8\equiv 18(\text{mod }5)$‍이면 $3\equiv 18(\text{mod }5)$‍입니다 (추이성)