정수론, 그 열세 번째 이야기 | 합동이론

 

여기에서는 정수론에서 다루는 강력한 도구 중 하나인 합동식에 대해 다룰 것이다.

우선 합동은 다음과 같이 정의한다.

 

주어진 양의 정수 $n$ 에 대해, $n \mid \left ( a - b \right )$ 인 두 정수 $a, b$ 에 대해       $a, b$ 를 법 $n$ 에 대해 합동이라고 하고, $a \equiv b \left ( mod n \right )$ 라고 쓴다.

 

이 때, 합동에 대해서 알아야 할 가장 기본적인 성질은 나머지와 관련된 것이다.

 

임의의 정수 $a, b$ 에 대해 $a \equiv b \left ( \mathrm{mod} n \right )$ 일 필요충분조건은      $a, b$ 가 $n$ 으로 나누었을 때 나머지가 같은 것이다.

 

Proof :

먼저 $a \equiv b \left ( mod n \right )$ 이라고 하자. 이는 $n \mid \left (a  - b \right )$ 이므로

$\exists k \in \mathbb{Z}\;s.t.\;a-b=kn \Leftrightarrow a = b + kn$ 이다.

 

$b$ 를 $n$ 으로 나눈 나머지가 $r$ 이라고 하면, $\exists q \in \mathbb{Z}\;s.t.\; b = qn + r$ ( 단, $0 \leq r < n$ )

따라서 $a = b + kn = \left (qn + r \right ) + kn = \left (q + n \right )n + r$ 이 성립하므로 $a$ 를 $n$ 으로 나눈 나머지도 $r$ 이다.

 

이제 $a, b$ 를 $n$ 으로 나눈 나머지가 $r$ 로 같다고 하자. (단, $0 \leq r < n$ )

이 때, $\exists q_1, q_2 \in \mathbb{Z}\;s.t.\;a = q_1n+r,\;b = q_2n + r$ 이므로

 

$a - b = \left (q_1n+r \right ) - \left (q_2n+r \right ) = \left ( q_1 - q_2 \right )n$ 이 성립한다.

따라서 $n \mid \left (a - b \right )$ 이므로 $a \equiv b \left ( \mathrm{mod} n \right )$ 이다.

 

 

또한, 합동에 대해서는 다음 여섯 가지 성질이 성립하는데, 하나하나 증명하도록 하자.

 

$n > 1$ 이 주어지고, $a, b, c, d$ 를 임의의 정수라고 하면 아래의 명제들은 참이다.      1. $a \equiv a \left ( \mathrm{mod} n \right )$      2. $a \equiv b \left ( \mathrm{mod} n \right ) \Rightarrow b \equiv a \left ( \mathrm{mod} n \right )$      3. $a \equiv b \left ( \mathrm{mod} n \right ) \wedge b \equiv c \left ( \mathrm{mod} n \right ) \Rightarrow a \equiv c \left ( \mathrm{mod} n \right )$      4. $a \equiv b \left ( \mathrm{mod} n \right ) \wedge c \equiv d \left ( \mathrm{mod} n \right ) \Rightarrow \left ( a + c \right ) \equiv \left ( b + d \right ) \left ( \mathrm{mod} n \right ) \wedge ac \equiv bd \left ( \mathrm{mod} n \right )$      5. $a \equiv b \left ( \mathrm{mod} n \right ) \Rightarrow \left (a + c \right ) \equiv \left ( b + c \right ) \left ( \mathrm{mod} n \right ) \wedge ac \equiv bc \left ( \mathrm{mod} n \right )$      6. $\forall k \in \mathbb{N},\;a \equiv b \left ( \mathrm{mod} n \right ) \Rightarrow a^k \equiv b^k \left ( \mathrm{mod} n \right )$

 

Part 1 :

$n \mid \left (a - a \right ) = 0$ 이므로 $a \equiv a \left ( \mathrm{mod} n \right )$

 

Part 2 :

$a \equiv b \left ( \mathrm{mod} n \right)$ 이므로 $\exists k \in \mathbb{Z}\;s.t.\;a - b = nk$

따라서 $b - a = \left (-k\right)n$ 이므로 $n \mid \left (b - a \right) $

그러므로 $b \equiv a \left (\mathrm{mod} n \right )$

 

Part 3 :

$a \equiv b \left (\mathrm{mod} n \right ) \wedge b\equiv c \left ( \mathrm{mod} n \right ) \Rightarrow \exists r, s \in \mathbb{Z}\;s.t.\; a - b = rn,\;b - c = sn$

이 때 $a - c = \left (a - b \right ) + \left ( b - c \right ) = rn + sn = \left (r + s \right ) n$ 이므로 $n \mid \left (a - c \right )$

따라서 $a \equiv c \left (\mathrm{mod} n \right)$

 

Part 4 :

$a \equiv b \left ( \mathrm{mod} n \right ),\;c\equiv d \left ( \mathrm{mod} n \right)$ 이면 $\exists k_1, k_2 \in \mathbb{Z}\;s.t.\;a-b=nk_1,\;c-d=nk_2$

 

따라서 $\left (a - b \right ) + \left ( c - d \right ) = \left (a + c\right) - \left (b + d\right) = nk_1 + nk_2 = n \left (k_1 + k_2 \right )$ 이므로

$ n\mid \left \{ \left (a + c\right) - \left ( b+d \right) \right \} \Leftrightarrow \left (a + c \right) \equiv \left (b + d\right) \left ( \mathrm{mod} n \right)$

 

또, $ac = \left ( b + nk_1 \right) \left ( d + nk_2 \right) = bd + \left (bk_2 + dk_1 + k_1k_2 n \right)n$ 이므로

$n \mid ac - bd \Leftrightarrow ac \equiv bd \left ( \mathrm{mod} n \right)$

 

Part 5 :

위의 4번 성질에서 $c \equiv c \left ( \mathrm{mod} n \right)$ 이므로 성립한다.

 

Part 6 :

수학적 귀납법을 사용하자. $k = 1$ 인 경우에는 자명하게 성립한다.

이제 어떤 자연수 $j$ 에 대해, $ a\equiv b \left ( \mathrm{mod} n \right ) \Rightarrow a^j \equiv b^j \left ( \mathrm{mod} n \right)$ 라고 가정하자.

 

이 때, 위의 4번 성질에서 $a \equiv b \left (\mathrm{mod} n \right) $ 이므로 $aa^j \equiv bb^j \left (\mathrm{mod} n \right)$ 이므로 $a^{j+1} \equiv b^{j+1} \left (\mathrm{mod} n \right)$ 이다.

 

따라서 수학적 귀납법에 의해 모든 자연수 $k$ 에 대해

$a \equiv b \left ( \mathrm{mod} n \right) \Rightarrow a^k \equiv b^k \left ( \mathrm{mod} n \right)$ 이 성립한다.

 

 

위에서 우리는 합동식의 양변에 덧셈과 곱셈을 해도 변화가 없음을 보였다.

뺄셈은 음수를 더하는 방식으로 생각할 수 있지만, 나눗셈의 경우에는 이야기가 다르다.

 

$ca \equiv cb \left (\mathrm{mod} n \right)$ 이면, $d = \mathrm{gcd} \left (c, n\right)$ 라 했을 때 $a \equiv b \left (\mathrm{mod} \frac{n}{d}\right)$ 이다.

 

Proof :

$ca \equiv cb \left (\mathrm{mod} n \right)$ 이므로 $\exists k\;s.t.\;c \left (a - b\right) = ca - cb = kn$

 

이 때, $d = \mathrm{gcd} \left (c, n\right)$ 이므로 $\exists r, s\;s.t.\;c = dr,\;n = ds,\;\mathrm{gcd} \left (r, s\right) = 1$

 

따라서 $c \left (a - b \right) = dr \left (a - b \right) = kds \Rightarrow r \left (a - b\right) = ks$

 

그러므로 $s \mid r\left(a - b\right)$ 인데 $\mathrm{gcd} \left (r, s\right) = 1$ 에서 유클리드 보조정리에 의해 $s \mid \left (a - b\right)$

따라서 $a \equiv b \left (\mathrm{mod} s \right)$ 이고, $n = ds$ 에서 $s = \frac{n}{d}$ 이므로

 

$a \equiv b \left (\mathrm{mod} \frac{n}{d}\right)$ 가 성립한다.

 

위의 정리는 $\mathrm{gcd} \left (c, n\right) = 1$ 일 때, 법이 변하지 않는 유용한 결과를 얻을 수 있다.