[정수론] 합동식1. 합동식의 정의

합동식의 정의

Definition. 양의 정수 $n$과 두 정수 $a, b$에 대하여 만약 $n \vert (a-b)$라면, 법 $n$에 대하여 $a$와 $b$는 합동이라고 하며, 기호로는 $a \equiv b \bmod n$ 으로 나타낸다. 

 

 

즉, 정수 $n$이 $a-b$를 나눈다면, 즉 $a-b$가 $n$으로 나누어 떨어진다면 $n$에 대하여 $a$와 $b$는 합동인 것이다. 

반대로 $a-b$가 $n$으로 나누어 떨어지지 않는다면 $a$와 $b$는 합동이 아니다. 

 

 

다르게 표현한다면, $\exists k \in \mathbb{Z}\, \mathrm{s.t.} \, a - b = nk$ 라면 $a \equiv b \bmod n$ 이다.

 

 

 

몇가지 예시를 생각해보자. 

$3 - 24 = -21$인데, $7 \vert -21$이므로 $3 \equiv 24 \bmod 7$이다. 

$25 - 12 = 13$인데, $7 \nmid 13$이므로 $25 \not\equiv 12 \bmod 7$이다. 

 

 

---

 

합동식의 성질

1이 아닌 양의 정수 $n$과 임의의 네 정수 $a, b, c, d$에 대하여 다음이 성립한다.

 

a. $a \equiv a \bmod n$

b. If $a \equiv b \bmod n$ then $b \equiv a \bmod n$

c. If $a \equiv b \bmod n$ and $b \equiv c \bmod n$ then $a \equiv c \bmod n$

d. If $a \equiv b \bmod n$ and $c \equiv d \bmod n$ then $a+c \equiv b+d \bmod n$

e. If $a \equiv b \bmod n$ and $c \equiv d \bmod n$ then $ac \equiv bd \bmod n$

f. If $a \equiv b \bmod n$ then $a+c \equiv b+c \bmod n$ and $ac \equiv bc \bmod n$

g. If $a \equiv b \bmod n$ then $a^k \equiv b^k \bmod n$ for any $k \in \mathbb{N}$

 

 

한마디로 정리하면, 합동 기호는 나눗셈을 제외하고는 정수 끼리의 덧셈, 곱셈, 뺄셈과 거듭제곱 연산에 대하여 마치 등호처럼 사용할 수 있다는 것이다!

 

 

---

 

합동식의 나눗셈?

합동식의 나눗셈을 살펴보기 전에, 아래 도움정리를 먼저 증명해보자.

 

Lemma 1. 정수 $a, b$에 대해 $d = \mathrm{gcd}(a,b)$ 라면, $ \mathrm{gcd}(a/d,b/d) = 1$이다. 

 

Proof. 귀류법을 이용해서 증명할 수 있다. $\mathrm{gcd}(a/d, b/d) \neq 1 $이라고 가정해보자. 

즉, $\mathrm{gcd}(a/d, b/d) = k$ for some $k \in \mathbb{Z}$, $k > 1$ 이다.

이때, $a/d$, $b/d$는 자명하게 정수이므로, 최대공약수를 정의할 수 있다. 정수인 이유는 스스로 생각해보자...

 

$a/d$와 $b/d$의 최대공약수가 1이 아닌 정수 $k$라면 다음이 만족한다.

$a/d = k \cdot s_{1}$, $b/d = k \cdot s_{2}$ for some $s_1, s_2 \in \mathbb{Z}$

 

즉, $a = k \cdot s_{1} \cdot d$, $b = k \cdot s_{2} \cdot d$가 성립한다.

따라서 $d \cdot k$는 $a, b$의 공약수이므로, 최대공약수인 $d$보다 큰 공약수가 존재하게 된다.

결과적으로 모순이 발생하므로, 우리는 가정이 틀렸음을 알 수 있다. $\blacksquare$

 

 

 

이제, 이 보조 정리를 이용해서 아래 theorem을 증명해보겠다.

 

 

 

Theorem. 정수 $a, b, c, n$에 대하여 $ca \equiv cb \bmod n$일 때, $a \equiv b \bmod (n/d)$ $($단, $d = \mathrm{gcd}(c, n)$$)$ 이다. 

 

Proof. $ca \equiv cb \bmod n$라면, 정의에 의해 $n \vert (ca - cb)$ 이므로 $n \vert  c(a-b) \cdots (1)$이다. 

 

이때, $d = \mathrm{gcd}(c, n)$이라고 하자. 즉, $c = k_{1}d$, $n = k_{2}d$를 만족시키는 정수 $k_1, k_2$가 존재한다. 

식 $(1)$을 다시 쓰면, $k_{2}d \vert k_{1}d(a-b)$ 이므로, 어떤 정수 $k'$에 대해 $k_{1}d(a-b) = k_{2}d \cdot k'$ 이다. 

 

양변을 $d$로 나누면 $k_{1}(a-b) = k_{2} \cdot k'$ 이므로, $k_{2} \vert k_{1}(a-b)$이다. 

이때, $k_1 = c/d, k_2 = n/d$이므로, lemma 1에 의해서 $\mathrm{gcd}(k_1, k_2) = 1$이다. 

따라서 $k_{2} \vert k_{1}(a-b)$라면 $k_{2} \vert a-b$가 성립한다.

즉, $a \equiv b \bmod k_2$ 이므로, $a \equiv b \bmod (n/d)$임을 알 수 있다. $\blacksquare$

 

 

 

예를 들어서, $14 \equiv 2 \bmod 12$ 일 때, $7 \equiv 1 \bmod 6$이다.

양변을 2로 나누는 것 처럼 위의 정리를 사용할 수 있다는 것이다.

 

특수한 상황으로, 만약 $n$과 $c$가 서로소라면, $ca \equiv cb \bmod n$일 때 $a \equiv b \bmod n$이다.

예를 들어서, $-35 \equiv 45 \bmod 8$일 때,  $5$와 $8$이 서로소이므로, $-7 \equiv 9 \bmod 8$이다.

이러한 특수한 경우에는, 합동식 양변을 5로 나누어도 성립한다는 것이다. 

 

*이 글은 Elementary Number Theory를 참고하여 작성하였다.*