Elementary Number Theory - 4.4 Liner Congruence and The Chinese remainder Theorem

4.4 Liner Congruence and The Chinese remainder Theorem

선형 합동식과 중국인의 나머지 정리

위 책 91p의 내용이다.

합동식을 연구하면서 아주 유용한 방법에 대해 이야기 해볼까 한다.

'합동식'은 '방정식'과는 다른 것이다. 기호도 다르다. 합동식은 작대기 세개 ≡ 를 쓰고, 부등식은 작대기 두개 = 를 쓴다. 처음에는 헷갈리지만 하다보면 구분하게 된다.

내가 이 부분을 잘 이해를 하고 있었으면 정수론을 공부하는 내내 굉장히 편했겠다 하는 생각이 든다.

정수론은 여기부터 계속 '합동식'에 관해 다룬다. 합동식을 연구할 때 이 선형 합동식 이론을 염두해 두고 공부해 나간다면 답답함이 많이 줄어들 것이라 생각된다.

ax ≡ b (mod n) 꼴의 방정식을 '선형합동식'이라고 부르며 이 방정식의 해를 x0라고 할 때 ax0 ≡ b (mod n)이라고 쓴다. 정의에서 n은 ax0 - b 를 나누거나 ax0 - b = ny0에 해당하는 y0가 존재해야 한다.

예를들어 x = 3, x = -9는 둘 다 3x ≡ 9 (mod 12)를 만족한다. 합동식에서는 3, -9를 같은 해로 본다.

Theorem 4.7 The liner congruence ax ≡ b (mod n) has a solution if and only if d|b, where d = gcd(a, n). If d|b, then it has d mutually incongruent solutions modulo n.

선형합동식 ax ≡ b (mod n)은 d = gcd(a, n)일 때 d|b는 경우 해를 갖는다. d|b이면 n에 대해서 d개의 서로 합동이 아닌 해를 가진다.

end.