정의 2.1.1. 합동(congruence)

임의의 두 정수 $a,\,b \in \Z$와 자연수 $m \in \N$에 대하여 $m \mid (a-b)$가 성립하면, $a$와 $b$는 법(modulo) $m$에 대하여 합동(congruent)이다라고 하고 기호로 $a \equiv b \pmod{m}$과 같이 나타낸다.

 

참고. 합동의 정의에 의해서 합동관계 $\equiv$는 동치관계(equivalence relation)임을 간단히 보일 수 있다.

 

정리 2.1.2.

임의의 정수 $a,\,b,\,c,\,d \in \Z$와 자연수 $m \in \N$에 대하여

1. $a \equiv b \pmod{m}$이고 $c \equiv d \pmod{m}$이면 $a \pm c \equiv b \pm d \pmod{m}$이 성립한다.
2. $a \equiv b \pmod{m}$이고 $c \equiv d \pmod{m}$이면 $ac \equiv bd \pmod{m}$이 성립한다.
3. $p(t)$가 정수 계수로 이루어진 다항식이라 하자. $a \equiv b \pmod{m}$이면, $p(a) \equiv p(b) \pmod{m}$이 성립한다.

 

다음의 정리는 주어진 합동식에 정수 $c \in \Z$를 곱하거나 나누었을 때에, 합동식이 어떻게 변화하는지를 보여준다.

 

정리 2.1.3.

임의의 정수 $a,\,b,\,c \in \Z$와 자연수 $m \in \N$에 대하여

1. $a \equiv b \pmod{m}$이면 $ca \equiv cb \pmod{cm}$이 성립한다.
2. $ca \equiv cb \pmod{m}$이면 $a \equiv b \pmod{m/\gcd(c,\,m)}$이 성립한다.
   특히, $ca \equiv cb \pmod{m}$이고 $\gcd(c,\,m) = 1$이면 $a \equiv b \pmod{m}$이 성립한다.

 

증명. (2) $d = \gcd(c,\,m)$이라 하자. $ca \equiv cb \pmod{m}$를 가정했으므로, $m \mid c(a-b)$를 얻고 따라서 $\frac{m}{d} \mid \frac{c}{d}(a-b)$를 얻는다. 한 편, $\gcd(\frac{m}{d},\, \frac{m}{c}) = 1$이므로 $\frac{m}{d} \mid (a-b)$이다. 즉, $a \equiv b \pmod{\frac{m}{d}}$이 성립한다..

 

이제부터 자연수 $m \in \N$을 언제나 주어진 합동식의 법으로 사용하도록 하자.

 

정의 2.1.4. 잉여류(residue class)

임의의 정수 $a \in \Z$에 대하여 $a$와 법 $m$에 대하여 합동인 모든 정수들의 집합 \[ \bar{a} = \set{b \in \Z}{a \equiv b \pmod{m}} \] 을 $a$의 법 $m$에 대한 잉여류(residue class) 또는 합동류(congruence class)라 한다.

 

참고. 합동관계 $\equiv$가 동치관계이므로 잉여류는 동치류(equivalence class)이다. 즉, 임의의 두 정수 $a,\,b \in \Z$에 대하여 $\bar{a} = \bar{b}$ 또는 $\bar{a} \cap \bar{b} = \emptyset$ 둘 중 하나만이 성립한다. 특히, $\bar{a} = \bar{b}$일 필요충분조건은 $a \equiv b \pmod{m}$인 것이다.

 

정리 2.1.5.

법 $m$에 대하여 $m$개의 서로 다른 잉여류가 존재하고 이는 다음과 같다. \[ \bar{0},\, \bar{1},\, \bar{2},\, \ldots,\, \overline{m-1} \]

 

정의 2.1.6. 완전잉여계(complete residue system)

법 $m$에 대한 $m$ 개의 서로 다른 잉여류에서 하나의 원소를 뽑아 만든 집합 $\{x_{1},\, x_{2},\, x_{3},\, \ldots,\, x_{m}\}$을 법 $m$에 대한 완전잉여계(complete residue system)라 한다.

 

법 $m$에 대한 가장 대표적인 완전잉여계로는 $\{0,\, 1,\, 2,\, \ldots,\, m-1\}$이 있다. 하지만 완전잉여계가 반드시 이와 같은 꼴인 것은 아니다. 예를 들어 법 $3$에 대한 대표적인 완전잉여계는 $\{0,\, 1,\, 2\}$지만, $\{1,\, 3,\, 5\}$ 또는 $\{1,\, 5,\, 6\}$ 또한 법 $3$에 대한 완전잉여계이다.

 

일반적으로 집합 $\{x_{1},\, x_{2},\, x_{3},\, \ldots,\, x_{m}\}$에 대하여 다음의 명제들은 동치이다.

1. $\{x_{1},\, x_{2},\, x_{3},\, \ldots,\, x_{m}\}$는 법 $m$에 대한 완전잉여계이다.
2. 임의의 정수 $a \in \Z$에 대하여, $a \equiv x_{i} \pmod{m}$을 만족하는 $x_{i}$가 유일하게 존재한다.
3. 임의의 $i,\,j \in \{1,\,2,\, \ldots,\, m\}$에 대하여 $i \neq j$ 이면 $x_{i} \not\equiv x_{j} \pmod{m}$이다.