Congruent는, 흔히 말하는 합동이다. 기하학에서 말하는 합동과 같은 의미면서도 다른 의미일수도 있는데, 같은 의미라는 것은 '같은 성질을 가진다'라는 뜻이고, 다른 의미라는 것은 '대수 영역이기 때문에 기하에서의 정의가 그대로 적용되지 않는다'라는 의미이다. 즉, 이 말을 정리하면 Congruent라는 의미는 좀 더 일반적인, 메타 정의이고, 대수, 기학 양쪽에서의 Congruent라는 것은 이 일반적인 의미를 구체화하여 적용한 것이다.
그렇다면, 대수에서의 Congruent라는 것은 어떤 의미인가? 정수 a, b, n이 주어졌다고 하고, n ≠ 0이라면,
a ≡ b (mod n)이며, a - b는 n의 배수일 때(양수이던지 음수던지) a는 b와 합동이라고 말한다(a is congruent to b).
여기서 n의 배수라는 것이 양수, 음수 여부에 상관없다는 점을 잘 눈여겨두라. 뒤에 언급할 것이다. 예를 들어서, 32 ≡ 7 (mod 5), -12 ≡ 37 (mod 7)..이다.
이 성질과 유클리드 알고리즘을 사용하면, 합동에 대한 방정식을 해결할 수 있다. 2x + 7 ≡ 3 (mod 17)과 같은 방정식이 주어졌다고 하자. 그렇다면, 2x ≡ -4 (mod 17)의 형태로 다시 쓸 수 있으며, x ≡ -2 (mod 17), 즉 어떤 수를 17로 나누었을 때 2가 모자라는 수를 구하는 문제로 바뀐다.
이런 경우, 구하고자 하는 수가 작다면 단순한 암산으로도 해결이 가능하겠지만, 수가 커질수록 직관적인 방법으로 해결하기 어려워진다. 예를 들어, 11111x ≡ 4 (mod 12345)와 같은 문제가 주어졌다고 하자. 암산으로 해결할 수 있겠는가? Congruent 의미에 익숙하지 않다면, 직관적으로 답 하기가 어려울 것이다.
이 문제를 해결하기 위해 위의 성질과 유클리드 알고리즘을 사용해보자. 먼저, ax + by = gcd(a, b)라는 문제를 해결하는데 유클리드 알고리즘이 사용된 것을 기억해보라. 11111x ≡ 4 (mod 12345)를 합동의 정의에 맞춰 다시 쓴다면, 11111x - 4 = 12345y라고 할 수 있으며, 11111x - 12345y = 4라고 할 수 있다. 이것은, gcd(12345, 11111) = 4라는 의미일까? gcd(12345, 11111)를 유클리드 알고리즘을 사용해서 구해보자.
12345 = 1 * 11111 + 1234
11111 = 9 * 1234 + 5
1234 = 246 * 5 + 4
5 = 1 * 4 + 1
4 = 4 * 1
유클리드 알고리즘에 따르면, gcd(12345, 11111) = 1이다. 4가 아니다. 그렇다면 11111x - 12345y = 4라는 것이 의미하는 것은 무엇일까? x와 y는 공통적으로 4로 나눌 수 있는, 어떤 수가 존재한다는 의미가 아닐까? 이제 x와 y를 구해보도록 하자. 이 과정은 확장된 유클리드 알고리즘(Extended Euclidean Algorithm)이라고 알려져 있는 방법을 이용한다.
12345 = a, 11111 = b라 하면,
a = b + 1234, 1234 = a - b
b = 9 * 1234 + 5, b = 9(a - b) + 5, -9a + 10b = 5
a - b = 246(-9a + 10b) + 4, a - b = -2214a + 2460b + 4, 2215a - 2461b = 4
-9a + 10b = 2215a - 2461b + 1, 2224a - 2471b = 1
여기서, 4를 곱해보면, 2224 * 4 * a - 2471 * 4 * b = 4, 11111x - 12345y = 4의 형태와 비교해본다면, 우리가 구하고자 하는 것은 11111x ≡ 4 (mod 12345)이므로, 2471 * 4가 원하는 답이 된다. 그리고, 11111 * 2471 ≡ 1(mod 12345)라는 식에서, 2471은 11111 (mod 12345)의 곱셈에 대한 역(inverse)이라 한다.
Library/Mathematics