칼큘러스와 정수론의 만남: Hensel의 lift 방법

칼큘러스는 연속량의 근사를 다루는 수학이고, 정수론은 이산량에 대한 정확한 문제를 다룹니다. 얼핏 보면 이 두 분야는 아무 관련이 없어 보이는데요. 그런데 쿠르트 헨셀이라는 수학자가 놀라운 발견을 했습니다. 칼큘러스의 아이디어를 활용하면 정수론 문제를 더 잘 이해할 수 있다는 겁니다.

이 글에서는 헨셀의 훌륭한 발견을 설명하기 위해 합동식에서 다항식 방정식을 풀어볼 겁니다. 구체적으로는, 다음 조건을 만족하는 모든 정수 x를 찾아보겠습니다.

$$x^3 - 17x^2 + 12x + 16 \equiv 0 \pmod{3000}$$

합동식에서 다항식을 푸는 이런 문제가 좀 낯설어 보일 수도 있지만, 놀랍게도 현대 정수론의 Langlands 프로그램과 직결되는 주제입니다.

중국인의 나머지 정리로 문제를 나누기

먼저 3000을 소인수분해하면:

$$3000 = 2^3 \times 3 \times 5^3$$

중국인의 나머지 정리에 따르면, 다음 하나의 합동식을 푸는 것은

$$x^3 -17x^2 + 12x + 16 \equiv 0 \pmod{3000}$$

이 세 개의 합동식을 각각 푸는 것과 동치입니다:

$$x^3 - 17x^2 + 12x + 16 \equiv 0\pmod{8}$$

$$x^3 - 17x^2 + 12x + 16 \equiv 0\pmod{3}$$

$$x^3 - 17x^2 + 12x + 16 \equiv 0\pmod{125}$$

일견 문제가 더 복잡해진 것 같지만, 사실은 훨씬 단순해졌습니다. 예를 들어, mod 8을 풀려면 x = 0, 1, 2, 3, 4, 5, 6, 7 총 8개 값만 대입하면 됩니다.

다항식을 mod 8로 정리하면:

$$x^3 - x^2 + 4x \equiv 0\pmod{8}$$

각 값을 대입해보면 해는 다음뿐입니다:

$$x \equiv 0, 4 \pmod{8}$$

마찬가지로 mod 3의 경우 x = 0, 1, 2를 시도해보면:

$$x \equiv 1 \pmod{3}$$

mod 125는 어떻게 할까?

안타깝게도 mod 125를 풀려면 x = 0부터 x = 124까지 125개 값을 모두 대입해야 합니다. 이건 너무 오래 걸릴 것 같은데요. 더 빠른 방법이 있을까요?

125 = 5³이라는 점에 주목해봅시다. 만약 x가 mod 125에서 해라면, 당연히 mod 5에서도 해여야 합니다. Mod 5는 훨씬 쉽습니다. x = 0, 1, 2, 3, 4를 대입하면:

$$x \equiv 2 \pmod{5}$$

이제 x = 2를 원래 다항식에 대입해보면:

$$2^3 - 17 \cdot 2^2 + 12 \cdot 2 + 16 = -20$$

흥미로운 점은 -20이 5로 나누어지지만, 125로는 나누어지지 않는다는 겁니다. 그런데 헨셀은 -20을 "125 mod에서 거의 0에 가깝다"고 생각했습니다. 왜냐하면 125 = 5³이고, -20은 최소한 5 한 번은 나누어지기 때문입니다.

이 생각만으로는 별로 도움이 안 될 것 같은데, 헨셀이 그 다음에 한 행동이 정말 놀라웠습니다.

뉴턴 방법: 칼큘러스에서의 근사

이를 설명하기 전에 잠깐 칼큘러스의 핵심 아이디어를 상기해봅시다.

뉴턴은 칼큘러스를 사용해 어떤 방정식의 근사해를 더 나은 근사해로 개선하는 방법을 보여줬습니다. 칼큘러스가 근사의 수학이니 당연하겠죠.

함수 g(x)가 있고, g(4) = 0.1이라고 알고 있다고 합시다. 0.1은 꽤 작으니, g(x) = 0의 해가 x = 4 근처에 있을 거라고 추측할 수 있습니다.

g(4 + ε) = 0을 만족하는 ε를 찾는다면, 뉴턴은 다음을 제시했습니다:

$$g(4 + \epsilon) \approx g(4) + g'(4) \cdot \epsilon$$

g'(4) = 2라면:

$$g(4 + \epsilon) \approx 0.1 + 2\epsilon$$

따라서 g(4 + ε) = 0의 근사해는 ε = -0.05이고, x = 3.95는 x = 4보다 실제 해에 더 가깝습니다. 더 좋은 해를 원하면 x = 3.95에서 같은 과정을 반복하면 됩니다. 이렇게 뉴턴은 복잡한 방정식의 해를 매우 정확하게 찾을 수 있었습니다.

헨셀의 아이디어

이제 헨셀로 돌아갑시다. 우리는 다음을 알았습니다:

$$x \equiv 2 \pmod{5}$$

는 다음의 해입니다:

$$x^3 - 17x^2 + 12x + 16 \equiv 0\pmod{5}$$

$f(x) = x^3 - 17x^2 + 12x + 16$이라고 하면, f(2) = -20입니다. -20은 5로는 나누어지지만 125로는 나누어지지 않습니다.

하지만 헨셀은 "5로 나누어진다"는 것이 "125로 나누어진다"는 것에 "가깝다"고 생각했습니다. 그래서 그는 뉴턴 방법을 적용하기로 결정했습니다. 마치 칼큘러스처럼, 2를 개선해서 f(x) ≡ 0 (mod 125)에 더 가까운 수를 찾으려는 거였죠.

f(x) ≡ 0 (mod 125)를 만족하는 정수 x는 반드시 x ≡ 2 (mod 5)를 만족해야 합니다. 따라서 다음과 같이 쓸 수 있습니다:

$$x = 2 + 5 \cdot n$$

여기서 n은 어떤 정수입니다.

헨셀이 발견한 놀라운 항등식이 있었습니다:

$$f(2 + 5n) = f(2) + f'(2) \cdot 5n + \text{(5의 더 높은 거듭제곱을 포함한 항들)}$$

이것은 정확히 뉴턴의 일차 근사 공식과 같은 형태입니다. 즉, 칼큘러스의 아이디어를 정수론에 직접 적용할 수 있다는 뜻입니다.

이렇게 헨셀이 발견한 방법은 mod 5에서의 해를 mod 5²으로, 그 다음 mod 5³으로 점진적으로 "들어올릴(lift)" 수 있게 해줍니다. 이것이 바로 현대 정수론에서 강력한 도구가 된 Hensel's Lemma의 핵심 아이디어입니다.