[Number Theory] 4. Congruence & Congruence Class(합동식 & 합동류)

0. Introduction

---

산술(정수론)적 요소들과 추상대수학의 연결다리 역할을 "Congruence(합동식)과 Modular Arithmetic(나머지 연산)"이 하게 될 것이다. Congruence는 모든 Congruence Class의 집합 $\mathbb{Z}$의 구성으로 이어지고, 이는 추상대수학에서 나올 대수적 구조들의 가장 간단한 모델이 될 것이다.

1. Congruence

---

자세하게 Congruence에 대해 알아보기전에, "동치 관계"에 대해서 가볍게 알고가자.

Def. Equivalent(동치)

---

어떤 이항 관계 "~"가 다음 세 조건을 만족한다고 하자.

임의의 객체 $a, b, c$에 대해
    i) 반사성 : $a$ ~ $a$
    ii) 대칭성 : $a$ ~ $b$이면, $b$ ~ $a$이다.
    iii) 추이성 : $a$ ~ $b$이고 $b$ ~ $c$이면, $a$ ~ $c$이다.

이 때, 이 이항 관계를 "동치 관계"라고 한다.

즉, 어떤 두 객체가 같다는 것을 추상화 시켜놓은 것이다.

이제 Congruence(합동)으로 돌아오면, Congruence의 기본 개념은, "동등 관계에 대한 일반화라고 생각할 수 있다."

1. 두 정수 $a, b$의 차이가 0이면, 같다(equal).
2. 그 차이가, 0의 배수이면 동치(equivalent)이다.
3. $n$이 양의 정수이고, $a, b$의 차이가 $n$만큼 난다면, "정수 $a, b$는 정수 $m$을 법으로하는 합동이다."(= a is congruent to b modulo n)라고 한다.

우리는 임의의 정수 $n$에 대해, $a - b = nk$라는 것은, $n$이 $a - b$를 나눈다는 것이고, 따라서 위의 3번 명제에 대해 엄밀하게 정의 내릴 수 있다.

Def. Congruence

---

$a, b, n$이 정수이고, $n > 0$이라고 하자. 이 때, $n$이 $a - b$를 나눈다면(나누어 떨어트린다면)
"$a, b$는 $n$을 법으로 하는 합동이다."라고 한다.(= a is congruent to b modulo n)
기호로는 $a \equiv b \pmod{n}$으로 표기한다.

Congruence 기호는 equal기호와 유사하며, 실제로도 동치관계와 많은 속성들을 공유한다.

Def. Congruence Class

---

$a$와 $n$이 정수이고, $n > 0$이라고 하자. $a$ modulo $n$의 합동류란(= The Congruence Class of a modulo n),
$a$ modulo $n$에 대해 합동인, 정수들의 집합을 의미한다.

$[a] = \{b \mid b \in{\mathbb{Z}}\ and\  b \equiv a \pmod{n}\}$

"$b \equiv a \pmod{n}$이  $b - a = nk$ or $b = a + nk$와 동치임을 의미한다.

따라서

$[a] = \{b \mid b \equiv a \pmod{n}\} = \{b \mid b = a + kn\ \  with\ \  k \in{\mathbb{Z}}\} = \{a + kn \mid k \in{Z}\}$