시작하며
정수론 분야에서 펠 방정식 (Pell’s equation)은 가장 아름답고 깊은 이론적 배경을 가진 디오판토스 방정식 중 하나로 알려져 있습니다. 본 기사에서는 이 방정식의 기본적인 정의와 성질부터 시작하여, 연분수(Continued fractions)를 이용한 우아하고 효율적인 해법, 나아가 무한히 존재하는 해의 생성 메커니즘까지 매우 상세하게 해설합니다. 수학을 사랑하는 모든 분들을 위해 수식의 유도부터 알고리즘의 시각화, 그리고 프로그래밍 언어를 이용한 구현까지 망라했습니다.
1. 펠 방정식이란 무엇인가?
펠 방정식이란 다음과 같은 형태를 가진 2변수 2차 디오판토스 방정식을 말합니다.
$$ x^2 - ny^2 = 1 $$여기서 $n$ 은 제곱수가 아닌(square-free 또는 최소한 완전제곱수가 아닌) 양의 정수입니다. 우리의 목표는 이 방정식을 만족하는 미지의 정수 $x$ 와 $y$ 의 쌍을 찾는 것입니다. 만약 $n$ 이 완전제곱수, 즉 $n = k^2$ ($k$ 는 정수)라고 가정해 봅시다. 그러면 방정식은 다음과 같이 변형할 수 있습니다.
$$ x^2 - k^2y^2 = 1 $$$$ (x - ky)(x + ky) = 1 $$$x$ 와 $y$ , 그리고 $k$ 는 모두 정수이므로 $(x - ky)$ 와 $(x + ky)$ 도 정수가 됩니다. 곱해서 1이 되는 정수의 조합은 $(1, 1)$ 또는 $(-1, -1)$ 밖에 존재하지 않습니다. 이를 풀면 $y = 0$ 이 되어, 해는 $(x, y) = (\pm 1, 0)$ 이라는 매우 단순한 것으로 한정되어 버립니다. 따라서 펠 방정식에서 $n$ 이 완전제곱수가 아니라는 조건은 의미 있는 해를 찾기 위한 필수적인 전제가 됩니다.
2. 역사적 배경: 펠과 페르마, 그리고 고대 인도의 수학자들
이 방정식에는 ‘펠’이라는 이름이 붙어 있지만, 역사적인 사실을 살펴보면 조금 기묘한 배경이 있습니다. 사실 이 방정식의 일반적인 해법을 근대 유럽에서 처음으로 연구하고, 해가 항상 존재한다고 강력히 주장한 사람은 프랑스의 위대한 수학자 피에르 드 페르마 (Pierre de Fermat)입니다.
나중에 레온하르트 오일러 (Leonhard Euler)가 영국의 수학자 존 펠 (John Pell)의 이름을 이 방정식에 잘못 연결하는 바람에, 오늘날까지도 ‘펠 방정식‘으로 널리 정착되고 말았습니다. 펠 자신은 이 방정식의 해법에서 중심적인 역할을 수행한 것은 아닙니다.
시대를 더 거슬러 올라가면, 페르마보다 수백 년 전에 인도의 수학자 브라마굽타 (Brahmagupta)와 바스카라 2세 (Bhāskara II)는 차크라발라법(Chakravala method)이라는 세련된 알고리즘을 사용하여 이러한 종류의 방정식의 해를 계산하고 있었습니다. 고대에서 중세, 그리고 근대로 이어지는 수학자들의 탐구의 역사가 이 방정식에 새겨져 있습니다.
3. 자명한 해와 비자명한 해의 차이
펠 방정식 $x^2 - ny^2 = 1$ 에는 $n$ 의 값에 상관없이 항상 $(x, y) = (\pm 1, 0)$ 이라는 해가 존재합니다. 방정식에 대입하면 $1^2 - n \cdot 0^2 = 1$ 이 되어 명백히 성립합니다. 이를 자명한 해 (trivial solution)라고 부릅니다.
하지만 수학자들이 진정으로 흥미를 가지는 것은 $y \neq 0$ 이 되는 비자명한 해 (non-trivial solution)입니다. 놀랍게도, $n$ 이 완전제곱수가 아닌 양의 정수라면, 펠 방정식에는 무한히 많은 비자명한 해 가 존재한다는 것이 수학적으로 증명되어 있습니다. 게다가 그 무한한 해 중에서 $x, y$ 가 모두 양의 정수인 가장 작은 해를 기본해 (fundamental solution)라고 부르며, 이것만 찾으면 나머지 모든 해를 대수적인 조작으로 쉽게 생성할 수 있습니다.
4. 연분수 전개와 펠 방정식의 깊은 관계
기본해를 효율적으로 찾기 위한 가장 강력하고 표준적인 도구가 바로 연분수 (Continued fraction)입니다. 무리수 $\sqrt{n}$ 은 무한 소수이므로 유한한 분수로는 나타낼 수 없지만, 무한히 이어지는 주기적인 정칙 연분수로 아름답게 표현할 수 있습니다.
$$ \sqrt{n} = [a_0; \overline{a_1, a_2, \dots, a_k, 2a_0}] $$여기서 $a_0$ 은 $\sqrt{n}$ 의 정수 부분(즉, $\lfloor \sqrt{n} \rfloor$ )이며, 위에 선이 그어진 부분은 연분수의 주기 부분을 나타냅니다. 이 주기의 길이를 $m$ 이라고 정의합시다.
연분수의 전개를 무한히 계속하는 것이 아니라 도중의 어느 항에서 끊어서 얻어지는 유리수 $\frac{p_i}{q_i}$ 를 근사분수 (convergent)라고 부릅니다. 근사분수는 무리수 $\sqrt{n}$ 에 대한 최선의 유리수 근삿값을 제공합니다. 펠 방정식의 기본해 $(x_1, y_1)$ 은 놀랍게도 이 $\sqrt{n}$ 의 연분수 전개에서 특정한 근사분수의 분자 $p$ 와 분모 $q$ 로부터 직접 얻어집니다. 구체적으로는 주기 $m$ 의 길이에 따라 다음과 같이 결정됩니다.
- 주기 $m$ 이 짝수인 경우: 기본해는 $(p_{m-1}, q_{m-1})$ 이 됩니다.
- 주기 $m$ 이 홀수인 경우: 기본해는 $(p_{2m-1}, q_{2m-1})$ 이 됩니다.
5. 기본해를 구하는 방법: 알고리즘의 철저한 해설
근사분수 $\frac{p_i}{q_i}$ 는 아래에 제시된 점화식을 이용하여 컴퓨터 상에서 매우 빠르게 계산할 수 있습니다.
$$ p_i = a_i p_{i-1} + p_{i-2} $$$$ q_i = a_i q_{i-1} + q_{i-2} $$초기 조건은 알고리즘을 원활하게 시작하기 위해 다음과 같이 설정합니다.
- $p_{-1} = 1, \quad p_{-2} = 0$
- $q_{-1} = 0, \quad q_{-2} = 1$
연분수의 각 항 $a_i$ 역시 정수의 사칙연산만을 이용하여 순차적으로 구할 수 있습니다. 이를 통해 부동소수점 연산의 오차를 완전히 배제한 정확한 정수 연산이 가능해집니다.
해를 탐색하는 일련의 과정을 시각화하기 위해 다음과 같은 상태 전이도를 준비했습니다.
flowchart TD
Start["시작: 정수 n 을 입력"] --> CheckSquare["n 이 완전제곱수인지 판정"]
CheckSquare --|"Yes"| Trivial["자명한 해만 존재 (종료)"] --> End["종료"]
CheckSquare --|"No"| InitContFrac["연분수의 점화식을 초기화"]
InitContFrac --> CalcNext["다음 연분수 항 a_i 와 근사분수 (p_i, q_i) 를 계산"]
CalcNext --> CheckEq["조건: p_i^2 - n * q_i^2 == 1 을 평가"]
CheckEq --|"False"| CalcNext
CheckEq --|"True"| Found["기본해 (x_1, y_1) = (p_i, q_i) 를 발견"] --> End
6. 구체적인 예: n = 7 인 경우의 연분수 전개와 기본해 유도
추상적인 이론뿐만 아니라, 구체적으로 $n = 7$ 인 경우에 대해 계산을 따라가 봅시다. 펠 방정식은 $x^2 - 7y^2 = 1$ 이 됩니다.
먼저 $\sqrt{7}$ 의 정수 부분은 $a_0 = 2$ 입니다. 나머지 소수 부분의 역수를 취하고 정수 부분을 빼내는 조작을 반복하면, $\sqrt{7}$ 의 연분수 전개는 다음과 같이 구해집니다.
$$ \sqrt{7} = [2; \overline{1, 1, 1, 4}] $$주기는 $m = 4$ 이며 짝수입니다. 따라서 기본해는 근사분수 $\frac{p_3}{q_3}$ 에서 얻어져야 합니다. 점화식을 사용하여 근사분수를 순서대로 계산해 봅시다.
- $i=0$: $a_0=2$ 일 때, $\frac{p_0}{q_0} = \frac{2}{1}$
- $i=1$: $a_1=1$ 일 때, $p_1 = 1 \times 2 + 1 = 3$ , $q_1 = 1 \times 1 + 0 = 1$ . 따라서 $\frac{p_1}{q_1} = \frac{3}{1}$
- $i=2$: $a_2=1$ 일 때, $p_2 = 1 \times 3 + 2 = 5$ , $q_2 = 1 \times 1 + 1 = 2$ . 따라서 $\frac{p_2}{q_2} = \frac{5}{2}$
- $i=3$: $a_3=1$ 일 때, $p_3 = 1 \times 5 + 3 = 8$ , $q_3 = 1 \times 2 + 1 = 3$ . 따라서 $\frac{p_3}{q_3} = \frac{8}{3}$
여기서 얻어진 $(p_3, q_3) = (8, 3)$ 을 방정식에 대입하여 검산해 보겠습니다. $8^2 - 7 \times 3^2 = 64 - 7 \times 9 = 64 - 63 = 1$ . 조건을 훌륭하게 만족하고 있으며, 이것이 $n = 7$ 인 경우의 기본해 $(x_1, y_1) = (8, 3)$ 이 됩니다.
7. 무한한 해의 생성: 행렬과 점화식을 이용한 접근
기본해 $(x_1, y_1)$ 이 하나라도 찾아지면, 나머지 모든 양의 정수해 $(x_k, y_k)$ 는 다음의 대수적인 관계식으로부터 무한히 생성할 수 있습니다.
$$ x_k + y_k \sqrt{n} = (x_1 + y_1 \sqrt{n})^k \quad \text{for} \quad k = 1, 2, 3, \dots $$이 식을 전개하고 유리수 부분과 무리수 부분($\sqrt{n}$ 의 계수)을 비교함으로써, 다음번 해 $(x_{k+1}, y_{k+1})$ 를 이전 해 $(x_k, y_k)$ 로부터 계산하는 점화식을 얻을 수 있습니다. 이를 행렬의 형식으로 표현하면 매우 깔끔한 형태가 됩니다.
$$ \begin{pmatrix} x_{k+1} \\ y_{k+1} \end{pmatrix} = \begin{pmatrix} x_1 & n y_1 \\ y_1 & x_1 \end{pmatrix} \begin{pmatrix} x_k \\ y_k \end{pmatrix} $$임의의 $k$ 번째 해는 행렬의 거듭제곱을 이용하여 다음과 같이 직접 계산할 수도 있습니다.
$$ \begin{pmatrix} x_k \\ y_k \end{pmatrix} = \begin{pmatrix} x_1 & n y_1 \\ y_1 & x_1 \end{pmatrix}^{k-1} \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} $$이러한 성질은 펠 방정식의 해가 단순한 숫자의 나열이 아니라, 대수적인 구조(군의 구조)를 가지고 있음을 강력하게 시사합니다.
8. 브라마굽타의 항등식과 차크라발라법
고대 인도의 수학에서 펠 방정식의 해법에 있어 중심적인 역할을 수행한 것이 브라마굽타의 항등식 (Brahmagupta’s identity)입니다. 이 항등식은 다음과 같은 형태를 띠고 있습니다.
$$ (x_1^2 - ny_1^2)(x_2^2 - ny_2^2) = (x_1 x_2 + n y_1 y_2)^2 - n(x_1 y_2 + x_2 y_1)^2 $$이 항등식의 놀라운 점은 $x^2 - ny^2 = k_1$ 의 해 $(x_1, y_1)$ 과 $x^2 - ny^2 = k_2$ 의 해 $(x_2, y_2)$ 를 조합함으로써, 새롭게 $X^2 - nY^2 = k_1 k_2$ 가 되는 해 $(X, Y)$ 를 직접 합성해 낼 수 있다는 것입니다.
인도의 수학자들은 이 강력한 항등식을 교묘하게 이용하여, 작은 오차를 가지는 해들을 차례로 합성해 나감으로써 최종적으로 오차가 $1$ 이 되는 해, 즉 펠 방정식의 해에 도달하는 차크라발라법 을 고안해 냈습니다. 이는 연분수 전개와 동등하거나 그 이상의 효율성을 가지는, 인류 수학사에 남을 위대한 성과입니다.
9. Python을 이용한 구현 예시와 해설
이론적인 배경을 충분히 이해했으니, 실제로 프로그램을 작성해 봅시다. 다음의 Python 스크립트는 지정된 $n$ 에 대하여 연분수의 점화식을 실행하고, 펠 방정식의 기본해를 탐색합니다. 계산 과정에서 부동소수점 수를 쓰지 않고 모두 정수의 연산으로 처리하기 때문에 정밀도 손실의 우려가 없습니다.
| |
이 코드를 실행하면 방금 손으로 계산해서 구했던 대로, 기본해 $(x, y) = (8, 3)$ 이 순식간에 출력됩니다. $n$ 의 값을 예를 들어 $61$ 과 같이 크게 해보면, 해가 거대한 숫자($x = 1766319049, y = 226153980$)가 되는 것을 확인할 수 있으며, 펠 방정식의 심오함을 실감할 수 있을 것입니다.
10. 대수적 정수론으로의 가교: 디리클레 단수 정리와의 관계
펠 방정식은 단순한 퍼즐 같은 정수 문제에 머물지 않습니다. 근대 수학에서는 실이차체 (real quadratic field) $\mathbb{Q}(\sqrt{n})$ 이론으로 들어가는 중요한 입구로 자리매김하고 있습니다.
펠 방정식의 해는 실이차체의 대수적 정수환에 있는 단수 (unit, 역원도 대수적 정수가 되는 원소)와 밀접하게 대응합니다. 기본해는 이 단수군을 생성하는 기본 단수 (fundamental unit)에 대응하며, 펠 방정식에 무한한 해가 존재한다는 사실은 더 고차원적인 정리인 디리클레 단수 정리 (Dirichlet’s unit theorem)의 특수한 경우로 간주할 수 있습니다. 기본 단수의 성질을 이해하는 것은 이차체의 류수(class number) 공식이나 아이디얼 류의 구조를 깊이 연구하는 데 있어서 극히 중요합니다.
11. 정리
본 기사에서는 디오판토스 방정식 중에서도 특히 매력적인 펠 방정식 에 대하여 그 기초부터 응용까지 자세히 탐구해 보았습니다. 완전제곱수가 아닌 $n$ 에 대해서는 항상 무한한 비자명한 해가 존재한다는 놀라운 사실, 연분수 전개를 이용한 효율적인 해 탐색 알고리즘, 그리고 생성된 기본해로부터 행렬을 이용하여 차례로 새로운 해를 합성해 나가는 역동성을 해설했습니다.
수백 년 전에 페르마나 브라마굽타가 고찰했던 고전적인 문제가 현대의 컴퓨터 알고리즘으로서 아름답게 구현될 수 있고, 더 나아가 고도의 대수적 정수론으로 연결되어 있다는 사실에는 시대를 뛰어넘는 수학의 깊은 낭만을 느끼지 않을 수 없습니다. 이 기사를 계기로 부디 Python 코드를 활용하여 다양한 $n$ 의 값에서 펠 방정식의 세계를 탐색하고, 수의 심오한 성질을 접해 보시길 바랍니다.