(수리논술) 합동식의 기본성질

정수 $a, \; b, \; m$ 에 대하여 $m \; | \; (a-b)$  (즉, 적당한 정수 $k$ 에 대하여 $a-b=km$) 일 때, $a \equiv b \; ({\rm mod} \;m)$ 이라고 쓴다.

 

합동식의 기본성질

 

양의 정수 $m, \; n, \; k$ 와 임의의 정수 $a, \; b, \; c, \; d$ 에 대하여 다음이 성립한다.

 

(1)	$a \equiv a \; ({\rm mod}\; m)$
	$a-a=0$ 이고, $m \cdot 0 =0$ 이므로 $m\; | \; 0$ 이다. 따라서 $a \equiv a \; ({\rm mod} \; m)$ 이다.
(2)	$a \equiv b\; ({\rm mod}\; m)$ 이면 $b \equiv a \; ({\rm mod} \; m)$ 이다.
	$a \equiv b\; ({\rm mod}\; m)$ 이면 $m \; | \; (a-b)$ 이다. 또 $m \; | \; (a-b)$ 이므로 $m \; | \; (b-a)$ 이다. 따라서 $b \equiv a\; ({\rm mod}\; m)$ 이다.
(3)	$a \equiv b\; ({\rm mod}\; m)$ , $b \equiv c\; ({\rm mod}\; m)$ 이면 $a \equiv c\; ({\rm mod}\; m)$ 이다.
	$a \equiv b\; ({\rm mod}\; m)$ 이면 $m \; | \; (a-b)$ 이고, $b \equiv c\; ({\rm mod}\; m)$ 이면 $m \; | \; (b-c)$ 이다. 그러므로 $m \; | \; \{(a-b)+(b-c)\}$ 이다. 즉, $m \; | \; (a-c)$ 이다. 따라서 $a \equiv c\; ({\rm mod}\; m)$ 이다,
(4)	$a \equiv b\; ({\rm mod}\; m)$, $c \equiv d\; ({\rm mod}\; m)$ 이면 $a \pm c \equiv b \pm d\; ({\rm mod}\; m)$ 이다. (복부호동순)
	$a \equiv b\; ({\rm mod}\; m)$ 이면 $m \; | \; (a-b)$ 이고, $c \equiv d\; ({\rm mod}\; m)$ 이면 $m \; | \; (c-d)$ 이다. 그러므로 $m \; | \; \{(a-b) \pm (c-d)\}$ 이다. 즉, $m \; | \; \{(a \pm c)-(b \pm d)\}$ 이다. 따라서 $a \pm c \equiv b \pm d\; ({\rm mod}\; m)$ 이다.
(5)	$a \equiv b\; ({\rm mod}\; m)$, $c \equiv d\; ({\rm mod}\; m)$ 이면 $ac \equiv bd\; ({\rm mod}\; m)$ 이다.
	$a \equiv b\; ({\rm mod}\; m)$ 이면 $m \; | \; (a-b)$ 이고, $c \equiv d\; ({\rm mod}\; m)$ 이면 $m \; | \; (c-d)$ 이다. 그러므로 $m \; | \; \{(a-b)c + (c-d)b\}$ 이다. 즉, $m \; | \; (ac-bd)$ 이다. 따라서 $ac \equiv bd\; ({\rm mod}\; m)$ 이다.
(6)	$a \equiv b\; ({\rm mod}\; m)$ 이면 $a^k \equiv b^k\; ({\rm mod}\; m)$ 이다.
	$a \equiv b\; ({\rm mod}\; m)$ 이면  $m \; | \; (a-b)$ 이다. 또, $k \ge 2$ 일 때, $a^k-b^k = (a-b)\left ( a^{k-1}+a^{k-2}b+ \cdots + ab^{k-2}+b^{k-1} \right )$ 이므로 $m \; | \; \left ( a^k-b^k \right )$ 이다. 따라서 $a^k \equiv b^k\; ({\rm mod}\; m)$ 이다.
(7)	$ab \equiv ac\; ({\rm mod}\; m)$ 이고, $d={\rm gcd}(a, \; m)$ 이면 $b \equiv c \left ( {\rm mod} \dfrac{m}{d} \right )$ 이다.
	$ab \equiv ac\; ({\rm mod}\; m)$ 이면 $m \; | \; a(b-c)$ 이다. $d={\rm gcd}(a, \; m)$ 이므로, $a=dx_1$, $m=dx_2$ 를 만족하는 정수 $x_1, \; x_2$ 가 존재한다. 또한 $dx_2 \; | \; dx_1(b-c)$ 이다. 또 $x_1$ 과 $x_2$ 가 서로소이므로 $x_2 \; | \; (b-c)$ 이다. 그런데 $x_2 = \dfrac{m}{d}$ 이므로, $\left . \dfrac{m}{d} \; \right | \; (b-c)$ 이다. 따라서 $b \equiv c \left ( {\rm mod} \dfrac{m}{d} \right )$ 이다.
(8)	$a \equiv b\; ({\rm mod}\; m)$ 이고, $n$ 이 $m$ 의 약수이면 $a \equiv b\; ({\rm mod}\; n)$ 이다.
	$a \equiv b\; ({\rm mod}\; m)$ 이면  $m \; | \; (a-b)$ 이다. 또, $n \; | m$ 이면 $n \; | \; (a-b)$ 이다. 따라서 $a \equiv b\; ({\rm mod}\; n)$ 이다.
(9)	$a \equiv b\; ({\rm mod}\; m)$ 이고, $d>0$ 이 $a, \; b, \; m$ 의 공약수이면, $\dfrac{a}{d} \equiv \dfrac{b}{d}\; \left ( {\rm mod} \; \dfrac{m}{d} \right )$ 이다.
	$a \equiv b\; ({\rm mod}\; m)$ 이면  $m \; | \; (a-b)$ 이다. 또, $d$ 가 $a, \; b, \; m$ 의 공약수이므로 $a=dx_1$, $b=dx_2$, $m=dx_3$ 를 만족하는 정수 $x_1, \; x_2, \; x_3$ 가 존재한다. 또한 $dx_3 \; | \; d(x_1-x_2)$ 이다. 그러므로, $x_3 \; | \; (x_1-x_2)$ 이다. 그런데 $x_1= \dfrac{a}{d}$, $x_2=\dfrac{b}{d}$, $x_3=\dfrac{m}{d}$ 이므로 $\left . \dfrac{m}{d} \right | \left ( \dfrac{a}{d} - \dfrac{b}{d} \right )$ 이다. 따라서 $\dfrac{a}{d} \equiv \dfrac{b}{d}\; \left ( {\rm mod} \; \dfrac{m}{d} \right )$ 이다.

 

 

<예제> $2^{20}-1$ 은 $41$ 로 나누어 떨어짐을 증명하여라.

 

 

$2^5 \equiv -9 \; ({\rm mod} \;41)$ 이므로 $\left (2^5 \right )^4 = (-9)^4 \; ({\rm mod} \; 41)$ 이다.

따라서 $2^{20} \equiv 81 \cdot 81 \equiv (-1) \cdot (-1) \equiv 1 \; ({\rm mod} \; 41)$ 이다.

결국 $2^{20}-1 \equiv 1-1 \equiv 0 \; ({\rm mod}\; 41)$ 이 된다.

 

 

 

<예제> $111^{333}+333^{111}$ 은 $7$ 의 배수임을 증명하여라.

 

 

$111 \equiv 6 \; ({\rm mod} \; 7)$

$111^2 \equiv 6^2 \equiv 1 \; ({\rm mod} \; 7)$

$\left (111^2 \right )^{166} \equiv 111^{332} \equiv 1^{162} \equiv 1 \; ({\rm mod} \; 7)$

$111^{332} \cdot 111 \equiv 111^{333} \equiv 1 \cdot 111 \equiv 6 \; ({\rm mod} \; 7)$

 

$333 \equiv 4 \; ({\rm mod} \; 7)$

$333^3 \equiv 4^3 \equiv 64 \equiv 1 \; ({\rm mod} \; 7)$

$\left (333^3 \right )^{37} \equiv 333^{111} \equiv 1^{37} \equiv 1 \; ({\rm mod} \; 7)$

 

따라서 $111^{333} + 333^{111} \equiv 6+1 \equiv 7 \equiv 0\; ({\rm mod} \; 7)$