펠 방정식
"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차
1. 개요
펠 방정식은 제곱수가 아닌 양의 정수 n에 대해, $x^2 - ny^2 = 1$ 형태의 부정 방정식을 말한다. 고대 그리스와 인도에서 2의 제곱근의 유리수 근사값과 관련하여 연구되었으며, 브라마굽타, 바스카라 2세 등의 인도 수학자들은 펠 방정식의 해를 구하는 방법을 개발했다. 17세기에는 유럽 수학자들이 펠 방정식을 재발견하고, 윌리엄 브롱커가 일반 해법을 제시했으며, 라그랑주가 일반 이론을 개발했다. 펠 방정식은 연분수를 이용하여 해를 구할 수 있으며, 대수적 수론, 체비셰프 다항식, 스토르메르 정리 등 다양한 수학 분야에 응용된다.
더 읽어볼만한 페이지
- 연분수 - 파데 근사
파데 근사는 함수의 도함수 값이 일치하도록 유리 함수로 근사하는 방법으로, 발산 급수 재합산, 특이점 분석 등에 응용되며 다점 파데 근사 등으로 일반화될 수 있다. - 연분수 - 불완전 감마 함수
불완전 감마 함수는 감마 함수의 적분 구간을 나누어 정의되며 상부 불완전 감마 함수와 하부 불완전 감마 함수로 나뉘고, 확률론, 통계학, 물리학 등 다양한 분야에서 응용되는 함수이다. - 디오판토스 방정식 - 베주 항등식
베주 항등식은 주 아이디얼 정역에서 두 원소의 최대공약수를 그 두 원소의 정수 배의 합으로 나타낼 수 있다는 정리이며, 확장 유클리드 알고리즘을 통해 베주 계수를 구할 수 있고, 정수, 다항식 등 다양한 대수적 구조로 확장 가능하다. - 디오판토스 방정식 - 피타고라스 삼조
피타고라스 삼조는 a² + b² = c²을 만족하는 양의 정수 세 쌍 (a, b, c)이며, 특히 서로소인 세 정수로 이루어진 경우를 원시 피타고라스 삼조라고 한다.
| 펠 방정식 | |
|---|---|
| 개요 | |
| 유형 | 디오판토스 방정식 |
| 변수 | x y n |
| 방정식 | x² - ny² = 1 |
| 역사 | |
| 기원 | 고대 인도 수학 |
| 관련된 수학자 | 페르마 오일러 펠 (오류로 인해) |
| 방법 | 차크라발라 법 |
2. 역사
펠 방정식은 이미 기원전 수 세기전부터 무리 제곱근의 유리 근삿값을 구하기 위하여 널리 연구되었다. 기원전 400년경 인도와 그리스의 수학자들은 $x^2 - 2y^2 = 1$ 및 이와 밀접하게 관련된 방정식 $x^2 - 2y^2 = -1$ 에서 나오는 수들을 연구했는데, 이는 이러한 방정식들이 2의 제곱근과 관련이 있기 때문이다.[6]
아르키메데스는 3의 제곱근을 유리수로 근사했고, 아르키메데스의 소떼 문제는 펠 방정식으로 다시 공식화하여 풀 수 있다. 문제가 담긴 원고에는 아르키메데스가 고안하여 에라토스테네스에게 보낸 편지에 기록되었다고 명시되어 있으며, 아르키메데스의 저술이라는 주장은 현재 일반적으로 받아들여진다.[7][8][9]
인도 수학에서 브라마굽타는 브라마굽타의 항등식을 발견하고, 이를 이용하여 $x^2 - Ny^2 = k$의 해를 생성할 수 있었다. 바스카라 2세는 차크라발라(순환) 방법을 제시하여 펠 방정식을 푸는 일반적인 방법을 제시했다.
17세기 여러 유럽 수학자들이 펠 방정식을 푸는 방법을 재발견했다. 피에르 드 페르마는 방정식을 푸는 방법을 찾았고, 존 월리스와 윌리엄 브롱커가 이 문제에 대한 해를 제시했다. 레온하르트 오일러는 이 해가 존 펠 때문이라고 잘못 생각하여 펠의 이름을 따서 방정식의 이름을 지었다.[16] 이후 조제프루이 라그랑주는 펠 방정식의 일반 이론을 개발했다.[17]
2. 1. 고대 그리스와 인도
기원전 400년경, 그리스와 인도의 수학자들은 $x^2 - 2y^2 = 1$ 형태의 방정식을 연구했는데, 이는 2의 제곱근의 유리수 근사값과 관련이 있다.[6] 바우다야나는 ''x'' = 17, ''y'' = 12와 ''x'' = 577, ''y'' = 408이 펠 방정식의 해임을 발견하고, 이를 통해 2의 제곱근에 대한 근사값을 제시했다.[5] 아르키메데스는 3의 제곱근을 유리수로 근사하기 위해 펠 방정식을 사용했으며,[6] 그의 아르키메데스의 소떼 문제는 펠 방정식으로 해결할 수 있는 고대 문제 중 하나이다.[7][8][9] 디오판토스는 $a^2x^2 + c = y^2$ 형태의 방정식을 연구했는데, 이는 펠 방정식과 동등하다.[10]2. 2. 인도 수학
7세기경 브라마굽타는 저서 《브라마스푸타시단타》(ब्राह्मस्फुटसिद्धान्तsa)에서 오늘날 '''브라마굽타 항등식'''이라고 불리는 공식을 사용하여 펠 방정식의 해에 대한 점화식을 발견하였다. 12세기 바스카라 2세(भास्कराचार्यsa, 1114–1185)는 1150년에 일반적인 ''n''에 대한 펠 방정식의 일반해(차크라발라 방법)를 제시하고, 인 경우의 해:
를 제시하였다.
2. 3. 중세 이슬람 수학
10세기 페르시아의 수학자 알 카라지(아부 바크르 카라지fa)는 디오판토스의 기법을 바탕으로 펠 방정식에 대한 연구를 계속하였다.[10]2. 4. 유럽 수학
17세기 여러 유럽 수학자들이 펠 방정식을 푸는 방법을 재발견했다. 피에르 드 페르마는 방정식을 푸는 방법을 찾았고, 1657년 편지에서 영국 수학자들에게 도전 과제로 제시했다.[12] 케넬름 디그비에게 보낸 편지에서 베르나르 프레니클 드 베시는 페르마가 150까지의 ''N''에 대한 가장 작은 해를 찾았다고 말했고, 존 월리스에게 ''N'' = 151 또는 313인 경우를 풀도록 도전했다. 월리스와 윌리엄 브롱커는 이 문제에 대한 해를 제시했지만, 월리스는 편지에서 해가 브롱커 때문이라고 제안했다.유럽 수학에서 펠 방정식의 일반해는 17세기 영국의 윌리엄 브롱커가 최초로 발견하였다. 조제프루이 라그랑주는 1766년~1769년 동안 브롱커의 해법이 옳고, 이 해법으로 모든 해를 구할 수 있다는 것을 증명하였으며, 펠 방정식이 항상 무한히 많은 해를 가진다는 것을 증명하였다.
"펠 방정식"이라는 이름은 영국의 수학자 존 펠(1611 – 1685)의 이름을 딴 것이다. 레온하르트 오일러가 1759년에 펠과 브롱커의 이름을 혼동하여 잘못 이름붙였는데, 펠은 펠 방정식과 별다른 관계가 없었다.[46] 존 펠과 방정식의 관련성은 그가 토마스 브랭커의 번역[14]인 요한 라인의 1659년 책 ''Teutsche Algebra''[15]를 영어로 개정하면서, 방정식에 대한 브런커의 해에 대한 논의를 포함시켰기 때문이다. 오일러는 이 해가 펠 때문이라고 잘못 생각하여 펠의 이름을 따서 방정식의 이름을 지었다.[16]
라그랑주는 형태의 수에 대한 연분수와 대수적 조작을 기반으로 하는 펠 방정식의 일반 이론을 1766년에서 1769년 사이에 개발했다.[17] 특히 라그랑주는 브런커-월리스 알고리즘이 항상 종료됨을 증명했다.
3. 해법
펠 방정식의 해법은 주어진 *n*에 대해 최소 해인 기본해를 찾고, 그 기본해로부터 다른 모든 해를 계산하는 방식으로 이루어진다.
제곱수가 아닌 양의 정수 *n*에 대해 펠 방정식은 항상 자명한 해 (1, 0) 이외의 정수해를 갖는다. 펠 방정식의 최소 해는 연분수 전개를 통해 구한 근사 분수를 이용하는 방법으로 찾을 수 있다.[35] 예를 들어 $n=7$의 경우, $\sqrt{7} = [2; \overline{1, 1, 1, 4}]$ 로 주기가 4(짝수)이므로, $[2; 1, 1, 1]$에서 근사 분수 $\frac{8}{3}$를 통해 최소 해 (8, 3)을 얻는다.
하나의 해 $(x, y)$를 얻었다면, 다음 식을 통해 다른 해들을 계산할 수 있다.
:
펠 방정식의 모든 해는 최소 해의 거듭제곱으로 표현된다.
해의 공식에서 $\alpha=x+y\sqrt{n},\; \beta=x-y\sqrt{n}$이라고 하면,
:
을 얻는다. 즉, 펠 방정식의 해에 대해 $\frac{y_k}{y}, 2x_k$는 뤼카 수열을 구성한다.
3. 1. 기본해 계산
fundamental solution영어이라고 불리는 기본해는 $\sqrt{n}$의 연분수 전개를 통해 계산할 수 있다. $\sqrt{n}$의 정칙 연분수에 대한 수렴값 수열을 $\frac{h_i}{k_i}$라고 하면, 펠 방정식을 만족하며 x를 최소화하는 양의 정수쌍 $(x_1, y_1)$은 어떤 i에 대해 $x_1 = h_i$이고 $y_1 = k_i$를 만족한다. 이 쌍을 기본해라고 한다.[35]$\sqrt{n}$의 정칙 연분수는 $\left[\lfloor\sqrt{n}\rfloor;\overline{a_1,a_2,\ldots,a_{p-1}, 2\lfloor\sqrt{n}\rfloor}\right]$ 형태로 표현 가능하며, $(a_1, a_2, \ldots, a_{p-1})$는 회문이다. 기본해는 주기의 길이 p에 따라 다음과 같이 결정된다.[35]
$\qquad (x_1,y_1)=\begin{cases}(h_{p-1},k_{p-1}),&\text{ p가 짝수일 때}\\(h_{2p-1},k_{2p-1}),&\text{ p가 홀수일 때}\end{cases}$
예를 들어, $n = 7$인 경우, $\sqrt{7}$의 연분수는 $[2; \overline{1, 1, 1, 4}]$이다. 주기의 길이가 4(짝수)이므로, 기본해는 $[2;1,1,1] = \frac{8}{3}$에서 $(x_1, y_1) = (8, 3)$이다.
$n=13$인 경우, $\sqrt{13}=[3;\overline{1,1,1,1,6}]$으로 주기가 홀수이다. 이때 기본해는 주기의 두 번째 발생 직전의 연분수인 $\frac{649}{180}$로부터 $(x_1, y_1)=(649, 180)$이다.
다음은 $n \le 128$에 대한 $x^2 - ny^2 = 1$의 기본해 목록이다. (n이 완전제곱수인 경우는 제외)
| n | x | y |
|---|---|---|
| 2 | 3 | 2 |
| 3 | 2 | 1 |
| 5 | 9 | 4 |
| 6 | 5 | 2 |
| 7 | 8 | 3 |
| 8 | 3 | 1 |
| 10 | 19 | 6 |
| 11 | 10 | 3 |
| 12 | 7 | 2 |
| 13 | 649 | 180 |
| 14 | 15 | 4 |
| 15 | 4 | 1 |
| 17 | 33 | 8 |
| 18 | 17 | 4 |
| 19 | 170 | 39 |
| 20 | 9 | 2 |
| 21 | 55 | 12 |
| 22 | 197 | 42 |
| 23 | 24 | 5 |
| 24 | 5 | 1 |
| 26 | 51 | 10 |
| 27 | 26 | 5 |
| 28 | 127 | 24 |
| 29 | 9801 | 1820 |
| 30 | 11 | 2 |
| 31 | 1520 | 273 |
| 32 | 17 | 3 |
| 33 | 23 | 4 |
| 34 | 35 | 6 |
| 35 | 6 | 1 |
| 37 | 73 | 12 |
| 38 | 37 | 6 |
| 39 | 25 | 4 |
| 40 | 19 | 3 |
| 41 | 2049 | 320 |
| 42 | 13 | 2 |
| 43 | 3482 | 531 |
| 44 | 199 | 30 |
| 45 | 161 | 24 |
| 46 | 24335 | 3588 |
| 47 | 48 | 7 |
| 48 | 7 | 1 |
| 50 | 99 | 14 |
| 51 | 50 | 7 |
| 52 | 649 | 90 |
| 53 | 66249 | 9100 |
| 54 | 485 | 66 |
| 55 | 89 | 12 |
| 56 | 15 | 2 |
| 57 | 151 | 20 |
| 58 | 19603 | 2574 |
| 59 | 530 | 69 |
| 60 | 31 | 4 |
| 61 | 1766319049 | 226153980 |
| 62 | 63 | 8 |
| 63 | 8 | 1 |
| 65 | 129 | 16 |
| 66 | 65 | 8 |
| 67 | 48842 | 5967 |
| 68 | 33 | 4 |
| 69 | 7775 | 936 |
| 70 | 251 | 30 |
| 71 | 3480 | 413 |
| 72 | 17 | 2 |
| 73 | 2281249 | 267000 |
| 74 | 3699 | 430 |
| 75 | 26 | 3 |
| 76 | 57799 | 6630 |
| 77 | 351 | 40 |
| 78 | 53 | 6 |
| 79 | 80 | 9 |
| 80 | 9 | 1 |
| 82 | 163 | 18 |
| 83 | 82 | 9 |
| 84 | 55 | 6 |
| 85 | 285769 | 30996 |
| 86 | 10405 | 1122 |
| 87 | 28 | 3 |
| 88 | 197 | 21 |
| 89 | 500001 | 53000 |
| 90 | 19 | 2 |
| 91 | 1574 | 165 |
| 92 | 1151 | 120 |
| 93 | 12151 | 1260 |
| 94 | 2143295 | 221064 |
| 95 | 39 | 4 |
| 96 | 49 | 5 |
| 97 | 62809633 | 6377352 |
| 98 | 99 | 10 |
| 99 | 10 | 1 |
| 101 | 201 | 20 |
| 102 | 101 | 10 |
| 103 | 227528 | 22419 |
| 104 | 51 | 5 |
| 105 | 41 | 4 |
| 106 | 32080051 | 3115890 |
| 107 | 962 | 93 |
| 108 | 1351 | 130 |
| 109 | 158070671986249 | 15140424455100 |
| 110 | 21 | 2 |
| 111 | 295 | 28 |
| 112 | 127 | 12 |
| 113 | 1204353 | 113296 |
| 114 | 1025 | 96 |
| 115 | 1126 | 105 |
| 116 | 9801 | 910 |
| 117 | 649 | 60 |
| 118 | 306917 | 28254 |
| 119 | 120 | 11 |
| 120 | 11 | 1 |
| 122 | 243 | 22 |
| 123 | 122 | 11 |
| 124 | 4620799 | 414960 |
| 125 | 930249 | 83204 |
| 126 | 449 | 40 |
| 127 | 4730624 | 419775 |
| 128 | 577 | 51 |
3. 2. 추가 해 계산
펠 방정식의 기본해 $(x_1, y_1)$이 주어지면, 나머지 해 $(x_k, y_k)$는 다음 점화식을 통해 계산할 수 있다.[18]:
:
또는, 다음 공식을 이용하여 계산할 수도 있다.[18]
:
3. 3. 효율적인 계산 방법
$\sqrt{n}$의 정칙 연분수에 대한 수렴값의 수열을 $\frac{h_i}{k_i}$로 나타낼 때, 펠 방정식을 풀고 x를 최소화하는 양의 정수쌍 $(x_1, y_1)$은 어떤 i에 대해 $x_1 = h_i$이고 $y_1 = k_i$를 만족한다. 이 쌍을 기본해라고 한다. $\sqrt{n}$의 정칙 연분수에서 정수열 $[a_0; a_1, a_2, \ldots]$은 항상 주기적이므로, 기본해는 다음과 같이 구할 수 있다.[35]$\qquad (x_1,y_1)=\begin{cases}(h_{p-1},k_{p-1}),&\text{ p가 짝수일 때}\\(h_{2p-1},k_{2p-1}),&\text{ p가 홀수일 때}\end{cases}$
빠른 정수 곱셈을 위한 Schönhage–Strassen 알고리즘을 이용하면 연분수 방법으로 기본해를 찾는 시간을 단축할 수 있다. 하지만 해의 자릿수가 입력값 n의 자릿수의 다항식보다 훨씬 큰 $\sqrt{n}$만큼 클 수 있기 때문에 다항 시간 알고리즘은 아니다.[18]
기본 해 $(x_1, y_1)$는 다음과 같은 형태로 간결하게 나타낼 수 있다.[18]
:
예를 들어 아르키메데스의 소떼 문제에서 펠 방정식 $x^2 - 410286423278424 y^2 = 1$의 기본 해는 매우 큰 수이지만, 다음과 같이 표현할 수 있다.[18]
:
여기서
:
이고 $x'_1$과 $y'_1$는 각각 45자리와 41자리의 십진수 자릿수만을 가진다.
소인수분해를 위한 quadratic sieve(이차체) 접근 방식과 관련된 방법을 사용하여 위와 같은 곱 표현을 찾을 수 있다. 이 알고리즘은 연분수 방법보다 효율적이지만 여전히 다항 시간 이상이 걸린다. 일반화된 리만 가설을 가정하면, 다음과 같이 표현할 수 있다.[18]
:
여기서 $N$ = log $n$은 입력 크기이다.
양자 컴퓨터를 이용하면 펠 방정식의 해에 대한 곱셈 표현을 다항 시간 내에 찾을 수 있다는 연구 결과가 있다.[19][20]
제곱수가 아닌 양의 정수 $n$에 대해 펠 방정식은 항상 자명한 해 $(x = 1, y = 0)$ 이외의 정수해를 갖는다. 또한 하나의 해 $(x, y)$를 얻었다면,
:
는 모두 펠 방정식의 해가 된다.
최소 해를 얻는 방법으로는 연분수 전개에서의 근사 분수를 이용하는 방법이 자주 사용된다. $\sqrt{n}$의 연분수 전개를 $[a_0; a_1, a_2, \ldots, a_m]$로 두고, 근사 분수 $\frac{P}{Q}$를 $[a_0; a_1, a_2, \ldots, a_{m-1}]$로 하면, $(x, y) = (P, Q)$가 해가 된다. 단, 주기 $m$이 홀수인 경우에는 우변 = −1의 해가 얻어지므로, 1의 해를 얻으려면 위 식을 제곱해야 한다.
예를 들어 $n$이 7이라면, $\sqrt{7} = [2; 1, 1, 1, 4]$ (주기는 4로 짝수)이므로, $[2; 1, 1, 1]$에서 근사 분수 $\frac{8}{3}$가 얻어지고, $(x, y) = (8, 3)$이 최소 해가 된다.
해의 공식에서
:
이라고 하면,
:
을 얻는다. 즉, 펠 방정식의 해에 대해 $\frac{y_k}{y}, 2x_k$는 뤼카 수열을 구성한다.
4. 확장된 펠 방정식
$x^2 - ny^2 = -1$ 형태의 방정식(음의 펠 방정식)이나 $x^2 - dy^2 = N$ 형태의 방정식(일반화된 펠 방정식)도 펠 방정식이라고 불린다.
4. 1. 펠 방정식 (우변이 -1)
$x^2 - ny^2 = -1$ 형태의 방정식도 펠 방정식이라고 불린다. 이 방정식은 $n$ 값에 따라 해가 없을 수도 있다. 해가 존재하는지는 $\sqrt{n}$을 연분수 전개했을 때 순환절의 길이(주기)가 홀수인 경우로 판별할 수 있다.[42]해가 존재하는 $n$의 필요조건은 다음과 같다.[42]
- 4의 배수가 아니다.
- 4k + 3 형태의 소인수를 갖지 않는다.
- $k^2 + \frac{2k}{a}$ (단, $0 < a < 2k$, $a$는 $2k$의 약수) 형태가 아니다.
$n$이 4k + 1 형태의 소수이거나 8k + 5 형태의 소수의 2배인 경우에는 반드시 해를 갖는다는 보고도 있다.[44] 또한, $n = k^2 + 1$ 형태라면 $(x, y) = (k, 1)$이 해가 된다.[45]
$x^2 - ny^2 = -1$이 풀 수 있는 처음 몇 개의 수 $n$은 다음과 같다.
: 1, 2, 5, 10, 13, 17, 26, 29, 37, 41, 50, 53, 58, 61, 65, 73, 74, 82, 85, 89, 97, ...
음의 펠 방정식이 특정 $n$에 대해 해를 갖는 경우, 그 기본 해는 정의 방정식의 양변을 제곱하여 양의 경우($x^2-ny^2=1$)에 대한 기본 해를 이끌어낼 수 있다. 즉, $(x^2 - ny^2)^2 = (-1)^2$ 이므로, $(x^2 + ny^2)^2 - n(2xy)^2 = 1$이 된다.
음의 펠 방정식의 해는 연분수 방법을 사용하여 찾을 수 있다. $(x + \sqrt{n} y)(x - \sqrt{n} y) = -1$이므로, $k$가 홀수일 때 다음 해는 $i(x_k + \sqrt{n} y_k) = (i(x + \sqrt{n} y))^k$에 따라 결정된다. 결과적인 재귀 관계는 다음과 같다.
:$x_k = x_{k-2} x_1^2 + n x_{k-2} y_1^2 + 2 n y_{k-2} y_1 x_1$
:$y_k = y_{k-2} x_1^2 + n y_{k-2} y_1^2 + 2 x_{k-2} y_1 x_1$
이는 음의 펠 방정식에 대한 무한한 해의 집합을 제공한다.
4. 2. 일반화된 펠 방정식
::위 식은 '''일반화된'''[33][34] (또는 '''일반'''[35]) '''펠 방정식'''이라고 한다. 방정식 은 해당 '''펠 방정식의 해'''이다.[35] 라그랑주는 1768년에 이 방정식을 푸는 재귀 알고리즘을 제시하여 문제를 인 경우로 축소했다.[36][37] 이러한 해는 위에 설명된 연분수 방법을 사용하여 도출할 수 있다.
이 의 해이고 이 의 해라면, 인 은 의 해이다. 이 원리는 ''곱셈 원리''라고 한다.[35] 해 을 해 의 ''펠 배수''라고 한다.
에 대해 모든 해가 그 집합의 해의 펠 배수인 유한한 해 집합이 존재한다. 특히, 가 의 기본 해라면, 방정식의 각 해는