3. 합동식

III. 합동식

1. 합동

합동이란 Z상의 동치관계로서 다음과 같이 정의한다.

$m \in {Z^+}$에 대하여 $a \equiv b$ (mod m) $\Leftrightarrow m|a - b$

이는 반사, 대칭, 추이조건을 만족하므로 동치관계이다 (증명은 생략한다.)

합동의 연산의 법칙에 대해서 알아보자.

법 m에 대하여 $a \equiv b$ (mod m), $c \equiv d$ (mod m) 일 때, (1) $a \pm c \equiv b \pm d$ (mod m) , $ac \equiv bd$ (mod m) (2) $a \pm c \equiv b \pm c$ (mod m) , $ac \equiv bc$ (mod m) (3) $a \equiv b \Rightarrow {a^n} \equiv {b^n}$

일반 정수 방정식과 비슷하나 약분할 때는 서로소라는 조건이 필요하다. 서로소가 아니면 합동의 법이 달라진다.

$m \in {Z^+}$ , $a, b, c \in Z$ 일 때 (1) $(a, m) = 1$ 일 때, $ab \equiv 0$ (mod m) $\Leftrightarrow b \equiv 0$ (mod m) (2) $(a, m) = 1$ 일 때, $ab \equiv ac$ (mod m) $\Leftrightarrow b \equiv c$ (mod m) (3) $(a, m) = d$ 일 때, $ab \equiv ac$ (mod m) $\Leftrightarrow b \equiv c$ (mod m/d)

역수가 합동식에서도 존재하나 서로소라는 조건이 필요하다. 결국 약분과 깊은 관련이 있다.

$m \in Z$에 대하여 $(a, m) = 1 \Leftrightarrow \exists {a^*} : 법 \; m에 \; 관한 \; a의 \; 역수$

2. 합동식의 활용

합동식의 활용의 한 예로 나머지 구하기를 해보자.

k=1234에 대하여 k를 3으로 나눈 나머지를 구하시오 [풀이] $k = 1 \times {10^3} + 2 \times {10^2} + 3 \times {10^1} + 4 \times {10^0}$    $\equiv 1 \times {1^3}  + 2 \times {1^2}  + 3 \times {1^1}  + 4 \times {1^0} \equiv 1$ (mod 3)

3. 잉여류와 완전잉여계

법 $m \in Z$ 에 관하여

완전잉여계는 서로 다른 m개 정수로서 법 m에 대해 합동이 아닌 것의 모임이다.

표준잉여게는 완전잉여계중에 {0,1 $\cdots$ , m-1}을 말한다.

기약잉여계는 서로 합동이 아닌 정수로서 m과 서로소인 것들의 모임이다.