일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 적분
- 수능저격
- 적분과 통계
- 함수의 그래프와 미분
- 수학1
- 확률
- 여러 가지 수열
- 중복조합
- 정적분
- 로그함수의 그래프
- 미적분과 통계기본
- 수악중독
- 수열의 극한
- 이정근
- 수열
- 함수의 연속
- 기하와 벡터
- 미분
- 행렬
- 수만휘 교과서
- 함수의 극한
- 경우의 수
- 수학2
- 이차곡선
- 수학질문
- 수학질문답변
- 행렬과 그래프
- 심화미적
- 도형과 무한등비급수
- 접선의 방정식
- Today
- Total
수악중독
(수리논술) 합동식의 기본성질 본문
정수 $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)$