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과 서로소인 것들의 모임이다.
'전공수학 > Number Theory' 카테고리의 다른 글
5. 원시근과 이산로그 (0) | 2015.07.18 |
---|---|
4. 페르마소정리, 오일러정리 (0) | 2015.07.18 |
2. 소수와 소인수분해 (0) | 2015.07.17 |
1. 정수의 성질 (0) | 2015.07.17 |
0. 개관 (0) | 2015.07.17 |