동치식

진도를 나가기 전에 다음 식이 동등하다는 것을 반드시 이해해야 합니다.
  • AB (mod C) A \equiv B\ (\text{mod }C)
  • A, space, m, o, d, space, C, equals, B, space, m, o, d, space, C
  • C, space, vertical bar, space, left parenthesis, A, minus, B, right parenthesis | 기호는 나누기 또는 ()의 인수라는 뜻입니다.
  • A, equals, B, plus, K, dot, C (K는 어떤 정수)
같은 개념을 나타내는 다른 형태들에 대해 알아봅시다.
예를 들어 다음 식은 동치관계에 있습니다.
  • 1323 (mod 5) 13 \equiv 23\ (\text{mod }5)
  • 13 mod 523 mod 5 13 \text{ mod } 5 \equiv 23 \text{ mod }5
  • 5, space, vertical bar, space, left parenthesis, 13, minus, 23, right parenthesis, left parenthesis, 5, space, vertical bar, space, minus, 10, 이기 때문에 참입니다 right parenthesis
  • 13, equals, 23, plus, K, dot, 5.일 때 성립합니다: 13, equals, 23, plus, left parenthesis, minus, 2, right parenthesis, times, 5

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

파이

앞의 예제에 나온 조각들은 다음과 같은 성질이 있다는 것을 확실하게 이해해야 합니다.
  • 각 조각 안에 있는 값의 쌍은 서로 연관됩니다.
  • 같은 값을 둘 이상의 조각에서 찾을 수는 없습니다. (조각은 둘씩 서로 만나지 않습니다)
  • 모든 조각을 하나로 합치면 모든 값을 포함하는 파이가 됩니다.
이런 성질을 가진 조각으로 나눠진 파이는 동치 관계에 있습니다.
동치 관계는 파이를 어떻게 조각들(동치류) 로 자르는지 규정합니다 (우리가 가진 값들을 어떻게 분할하는지).
일반적으로 동치 관계는 다음과 같은 성질을 가져야 합니다:
  • 파이: 관심이 있는 값을 모두 모은 것
  • 파이 한 조각: 동치류
  • 파이를 여러 조각으로 자른 것: 동치 관계
특별히 앞의 예제는 다음과 같은 특성이 있습니다:
  • 파이: 모든 정수를 모은 것
  • 파이 조각 B: 모든 값이 m, o, d, space, C, equals, B인 동치류
  • 파이를 여러 조각으로 자르는 방법: 모듈 C에 대한 합동 관계, (mod C) \equiv (\text{mod } C)
위와 같은 특성으로 인해 모듈 C에 대한 합동 관계는 동치 관계입니다. 이 연산은 정수들을 C개의 서로 다른 동치류로 분할합니다.

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

모듈 C에 대한 합동 관계가 동치 관계라는 것을 알게 되면 이것이 반드시 가져야 할 특성에 대해 알 수 있습니다.
동치 관계는 다음과 같은 특성을 갖는 관계입니다:
  • 반사성: A가 A와 관계가 있습니다
  • 대칭성: A가 B와 관계가 있다면, B도 A와 관계가 있습니다
  • 추이성: A가 B와 관계가 있고, B가 C와 관계가 있다면, A와 C도 관계가 있습니다
이는 모듈에 대한 합동 관계가 (mod C) 와 동치 관계이기 때문입니다. 이것이 의미하는 바는 다음과 같습니다:
  • AA (mod C) A \equiv A \ (\text{mod } C)
  • AB (mod C) A \equiv B \ (\text{mod }C) 이면
  • 이고 이면 입니다

예제

mod5
m, o, d, space, 5, colon를 이용하여 이 특성들을 구체적인 예에 적용시켜 봅시다.
  • 33  mod 5 3 \equiv 3\ \text{ mod } 5 (반사성)
  • 38 (mod 5) 3 \equiv 8\ (\text{mod }5) 이면 83 (mod 5) 8 \equiv 3\ (\text{mod }5) 입니다 (대칭성)
  • 38 (mod 5)3 \equiv 8\ (\text{mod }5) 이고 818 (mod 5) 8 \equiv 18\ (\text{mod }5) 이면 318  mod 5 3 \equiv 18\ \text{ mod }5 입니다 (추이성)