관리 메뉴




수악중독

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

수능 수학/수리논술

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

수악중독 2017.06.14 22:36

정수 $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 b \; ({\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}$ 은 $41$ 로 나누어 떨어짐을 증명하여라.




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






-->