x ≡ 25 (mod 42)라는 수가 주어졌다고 하자. x를 결정하는 수를 대수로 풀어쓴다면, x = 25 + 42k라고 할 수 있을 것이다. 여기서 42k를 서로소인 두 수로 분해해본다면, (6, 7), (14, 3)과 같은 수가 있을 것이다. 즉, x = 25 + 6 * 7k, x = 25 + 14 * 3k라고 할 수 있다.
이것은, x ≡ 4 (mod 7), x ≡ 1 (mod 6)과 같은 형태로 다시 쓸 수 있는데, 여기서 중요한 것은 이 두 수가 서로소여야 한다. 만약, 두 수가 서로소가 아니라면, 이 합동식은 같은 나머지를 가지는 수로 나누었을 때 다른 나머지가 나온다는 모순이 생기기 때문이다.
x ≡ 25 (mod 42)는, x ≡ 4 (mod 7), x ≡ 1 (mod 6)의 형태로 다시 쓸 수 있으며, 두 식을 나누는 수 m, n의 gcd(m, n) = 1일 때, x (mod mn)은 하나의 해가 존재한다. 이것이 유명한 중국식 나머지 정리인데, 일반화하여 정리해보자.
Theorem. gcd(m, n) = 1이라고 했을 때, 두 정수 a, b가 있고, x ≡ a (mod m), x ≡ b (mod n)을 동시에 만족할 때 이것을 만족하는 x (mod mn)은 정확하게 하나가 존재한다.
예를 들어보자. x ≡ 3 (mod 7), x ≡ 5 (mod 15)라면, x는 얼마인가?
7로 나누었을 때 3이 남는 수의 목록을 만들어보고, 15로 나누었을 때 5가 남는 수의 목록을 작성해보자. 그리고 이 두 목록 중에서, 양쪽의 조건을 모두 만족하는 수가 바로 우리가 원하는 답이 된다.
5, 20, 35, 50, 65, 80..
3, 10, 17, 24, 31, 38, 45, 59, 66, 73, 80..
비교적 작은 수임에도 불구하고, 목록을 작성하는 것은 귀찮은 일이다. 즉, 수가 커진다면 이렇게 목록을 만들어서 일일이 확인할 수 없다는 말이 된다. 더 간단한 방법은 없을까? 위의 문제는 작은 수를 사용했기 때문에 일반화된 방법으로 해결하지 않았다. 그럼, 정말로 큰 수가 등장하는 문제를 살펴보자. 예륻 들어, x ≡ 7 (mod 12345), x ≡ 3 (mod 11111), 이것을 만족하는 x는?
x = 3 + 11111s, 3 + 11111s = 7 (mod 12345), 11111s = 4 (mod 12345)
여기서, 11111 (mod 12345)에 대한 inverse는 얼마인가? 유클리드 알고리즘을 이용해서 구해보면,
12345 = 1 * 11111 + 1234
11111 = 9 * 1234 + 5
1234 = 246 * 5 + 4
5 = 1 * 4 + 1
4 = 4 * 1, gcd(12345 11111) = 1
12345 = a, 11111 = b
a = b + 1234
b = 9( a - b) + 5, -9a + 10b = 5
a - b = 246(-9a + 10b) + 4, 2215a - 2461b = 4
-9a + 10b = 2215a - 2461b + 1
-2224a + 2471b = 1
2471임을 알 수 있다. 따라서, 11111 * 2471 * 4 = 4 (mod 12345)라는 결론을 얻을 수 있다.
여기서, 앞의 식을 다시 한번 살펴보자.
3 + 11111s ≡ 7 (mod 12345)인데, 11111s ≡ (7 - 3) (mod 12345), 위에서 얻은 식과 비교하면 s는 2741 *4 = 9884라는 것을 알 수 있다. 즉, x = 3 + 11111 * 9884 ≡ 109821127 (mod 11111 * 12345)이며, 이것이 유일한 해이다.
Library/Mathematics