3. 합동식

Posted by Bitssam
2015. 7. 18. 00:10 전공수학/Number Theory

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
3. 합동식  (0) 2015.07.18
2. 소수와 소인수분해  (0) 2015.07.17
1. 정수의 성질  (0) 2015.07.17
0. 개관  (0) 2015.07.17