SU_DING_GI

중국인의 나머지 정리 연립 합동식의 유일한 공통해를 찾는 정리 r 개의 서로 다른 서로소인 양의 정수 n1, n2, ... , nr에 대하여 연립 선형 합동식 x ≡ a1 (mod n1) x ≡ a2 (mod n2) . . . x ≡ ar (mod nr) mod n1n2...nr에 대하여 유일한 공통 해를 가진다 예시 x ≡ 2 (mod 3) → a --- (1) x ≡ 3 (mod 5) → b --- (2) x ≡ 1 (mod 7) → c --- (3) 각 a, b, c를 세 연립 합동식의 해라고 하고, 중국인의 나머지 정리를 증명하기 위해 x ≡ a + b + c (mod 3·5·7) --- (4) 로 둘 수 있다 식 (1)을 만족하기 위해 a는 3으로 모듈러 연산을 하였을 때 0이 되면 안되고, 마..

유클리드 호제법 A = Bq + R 유클리드 호제법 : A와 B의 최대 공약수(Greatest Common Divisor)가 G이면 B와 R의 최대 공약수도 G이다. 증명 A = aG B = bG 로 표현할 수 있고, a와 b는 서로소이다. 이 두 식을 위 식에 대입하면 aG = bGq + R 이다. 따라서, R = (a - bq)G 이다. B와 R의 최대 공약수가 G임을 보이기 위해서는 b와 a - bq가 서로소임을 보이면 된다. 만약 b와 a - bq가 서로소가 아니라고 가정해보자 b = b'C a - bq = a'C a - bq에 b = b'C를 대입하면, a - b'Cq = a'C a = (b'q + a')C 가 된다. 그렇게 되면 a와 b가 C라는 공약수를 갖게 되면서 기존의 서로소라는 가정에 ..