합동, 합동식의 정의와 기본성질 알아보기

합동의 정의

양의 정수 $m$과 정수 $a, b$에 대해 $m$이 $a-b$의 약수, 즉 $m | (a-b)$일 때 $a$와 $b$를 법 $m$에 대해 합동이라 한다. 기호는

$a \equiv b ( \mod m)$ 으로 나타낸다.

 

$a$와 $b$가 법 $m$ 에 대해 합동이 아니라는 기호는

$ a \not\equiv b (\mod m) $으로 나타낸다.

 

임의의 정수 $a$를 양의 정수 $m$으로 나눌 때 몫을 $q$, 나머지를 $r$이라 하면

$a=qm+r$ $(0 \leq r < m)$ 이다.

$a-r = qm$ 이므로 $m | (a-r)$ 이다. 즉, $a \equiv r (\mod m)$ 이다.

따라서 임의의 정수는 $0, 1, 2, \cdots , m-1$ 중 어떤 하나와 법 $m$에 대해 합동이다.

그러므로 $a \equiv b ( \mod m)$은 $a$, $b$를 각각 $m$으로 나눈 나머지와 같다.

 

합동의 기본성질

임의의 정수 $a$, $b$, $c$, $d$와 양의 정수 $m$, $n$, $k$에 대해서

 

1. $a \equiv a ( \mod m)$이다.

 

2. $a \equiv b ( \mod m)$이면 $b \equiv a ( \mod m )$이다.

 

3. $a \equiv b ( \mod m)$이고 $b \equiv c ( \mod m)$이면 $a \equiv c ( \mod m)$이다.

 

4. $a \equiv b (\mod m)$이고 $c \equiv d ( \mod m)$이면

    $a \pm c \equiv b \pm d ( \mod m)$(복부호동순), $ac \equiv bd ( \mod m)$이다.

 

5. $a \equiv b ( \mod m)$이면,

    $a \pm c \equiv b \pm c ( \mod m)$ (복부호동순), $ac \equiv bd ( \mod m)$이다.

 

6. $a \equiv b ( \mod m)$이면, $a^k \equiv b^k ( \mod m)$이다.

 

7. $a \equiv b ( \mod m)$이고 $n | m$이면, $a \equiv b ( \mod n)$이다.

 

8. $a \equiv b ( \mod m)$이고 $c>0$이면, $ac \equiv bc (\mod mc)$이다.

 

9. $a \equiv b ( \mod m) $, $d|a$, $d|b$, $d | m$, $d>0$이면, $\frac{a}{d} \equiv \frac{b}{d} ( \mod \frac{m}{d} )$이다.

 

<증명을 위한 정리>

정리1. $a$가 $b, c$의 약수이면 임의의 정수 $x, y$에 대해 $a$는 $bx+cy$의 약수이다.

정리2. $a$가 $b$의 약수이고 $b$가 $c$의 약수이면 $a$는 $c$의 약수이다.

 

증명

1. $a-a=0$이고 $m \cdot 0 =0$이므로 $ m | 0$이다. 따라서 $a \equiv a ( \mod m)$ 이다.

 

2. $a \equiv b ( \mod m)$ 이면 $m | (a-b)$ 이다. 또한 $m | (a-b)$이므로 $m | (b-a)$이다.

따라서 $b \equiv a ( \mod m) $ 이다.

 

3. $a \equiv b ( \mod m)$이면 $m | (a-b)$이고 $b \equiv c ( \mod m)$이면 $m | (b-c) $이다. 이때 정리1에 의해 $m | (a-b) + (b-c) = a-c$이다. 따라서 $a \equiv c (\mod m)$이다.

 

4. $a \equiv b ( \mod m)$이면 $ m | (a-b)$이고 $c \equiv d (\mod m)$이면 $m | (c-d)$이다. 따라서 $m | (a-b) \pm (c-d) = (a\pm c)-(b \pm d)$ 이므로 $a\pm c \equiv b \pm c (\mod m)$이다. 또한 정리1에 의해 $(a-b)c+(c-d)b$는 $m$의 배수이다. $(a-b)c+(c-d)b=ac-bd$이므로 $m | (ac-bd)$이다. 따라서 $ac \equiv bd ( \mod m)$이다.

 

5. $a \equiv b (\mod m)$이므로 $m | (a-b)$이다. 또한 $(a \pm c) - (b \pm c) = a-b$이므로 $m | (a \pm c) - (b \pm c)$이다. $a \pm c \equiv b \pm c ( \mod m)$이다. 또한 $ac-bc = (a-b) c$이고 $m | (a-b)$이므로 $m | (a-b)c$이다.

따라서 $ac \equiv bc ( \mod m)$이다.

 

6. $a\equiv b ( \mod m) $이면 $m | (a-b)$이다. 또한 $k \geq 2$일 때 $a^k - b^k = (a-b)(a^{k-1}+ a^{k-2}b + \cdots + ab^{k-2}+b^{k-1})$이므로 $m | (a^k-b^k)$이다. 따라서 $a^k \equiv b^k ( \mod m)$이다.

 

7. $a \equiv b ( \mod m)$이면 $m | (a-b) $이다. 또한 $n | m$이면 정리2에 의해 $n | (a-b)$이다. 따라서 $a \equiv b (\mod n)$이다.

 

8. $a \equiv b (\mod m)$이면 $m | (a-b) $이다. $c>0$이면 $mc>0$이고 $mc | (a-b)c = ac-bc$이므로 $ac \equiv bc ( \mod mc)$이다.

 

9. $a \equiv b ( \mod m) $이면 $m | (a-b) $이다. $d|a$이면 $a=dd_1$,   $d|b$이면 $b=dd_2$,   $d|m$이면 $m=dd_3$ 이므로 $dd_3 | d(d_1-d_2)$이다. 따라서 $d_3 | (d_1 -d_2)$이다. 이때 $d_1 = \frac{a}{d}$,   $d_2 = \frac{b}{d}$,   $d_3=\frac{m}{d}$ 이므로 $\frac{m}{d} | \frac{a}{d} - \frac{b}{d}$ 이다. 따라서 $\frac{a}{d} \equiv \frac{b}{d} ( \mod \frac{m}{d} ) $이다.