펠 방정식

Pell-Fermat 방정식이라고도 불리는 Pell의 방정식은 $x$ ${\displaystyle 2^{}}$- ${\displaystyle {ny}^{}}$ 2 = 1${\displaystyle ,}$ ${\displaystyle$x^{2}-ny^{2}=${\displaystyle 1}$,} 형태의 모든 디오판토스 방정식이며, 여기서 n은 주어진 양의 비제곱 정수이고, x와 y에 대한 정수 해를 찾습니다. 데카르트 좌표에서 방정식은 쌍곡선으로 표현됩니다. x = 1이고 y = 0인 자명한 해처럼 x와 y 좌표가 둘 다 정수인 점을 곡선이 지나는 곳마다 해가 발생합니다. 조셉 루이스 라그랑주는 n이 완벽한 제곱이 아닌 한, 펠의 방정식에는 서로 다른 정수해가 무한히 많이 있습니다. 이러한 해는 x/y 형태의 유리수에 의해 n의 제곱근을 정확하게 근사하는 데 사용될 수 있습니다.

이 방정식은 브라마굽타를 시작으로 인도에서 광범위하게 처음 연구되었는데, 브라마굽타는 그의 브라흐마스푸 ṭ시단타 628년경에 ${\displaystyle 92}$ ${\displaystyle x^{}}$ ${\displaystyle 2{}^{}}$+ 1 = ${\displaystyle y^{}}$ 2 ${\$display 92x^{2}+1=y^{2}}의 정수 해를 발견했습니다. 12세기의 바스카라 2세와 14세기의 나라야나 판디트는 모두 펠 방정식과 다른 이차 불확정 방정식에 대한 일반적인 해를 발견했습니다. 바스카라 2세는 일반적으로 자야데바와 브라마굽타의 연구를 바탕으로 차크라발라 방법을 개발한 것으로 알려져 있습니다. n=2인 방정식에서 발생하는 펠 수와 같은 펠 방정식의 구체적인 예에 대한 해결책은 그리스의 피타고라스 시대와 인도의 비슷한 날짜 이후로 훨씬 더 오래 알려져 있었습니다. William Brounker는 Pell의 방정식을 푼 최초의 유럽인이었습니다. 펠 방정식의 이름은 레온하르트 오일러가 브로큰커의 방정식 해법을 존 펠에게 잘못 귀속시킨 데서 비롯되었습니다.^{[3][4][note 1]}

역사

일찍이 기원전 400년에 인도와 그리스에서 수학자들은 n=2인 펠 방정식에서 나오는 수를 연구했습니다.

${\displaystyle x^{2}-2y^{2}=1,}$

그리고 밀접하게 연관된 방정식으로부터

${\displaystyle x^{2}-2y^{2}=-1}$

이 방정식들이 2의 제곱근에 연결되어 있기 때문입니다.^[5] 실제로 x와 y가 이 방정식을 만족하는 양의 정수라면 x/y는 √2의 근사치입니다. 이러한 근사식에 등장하는 x와 y, 즉 변과 지름의 숫자는 피타고라스인들에게 알려져 있었고, 프로클로스는 반대 방향에서 이 숫자들이 이 두 방정식 중 하나를 따른다는 것을 관찰했습니다.^[5] 마찬가지로 Baudhayana는 x = 17, y = 12 및 x = 577, y = 408이 Pell 방정식의 두 해이며, 17/12 및 577/408은 2의 제곱근에 매우 가까운 근사치임을 발견했습니다.

나중에 아르키메데스는 3의 제곱근을 유리수 1351/780으로 근사했습니다. 그는 자신의 방법을 설명하지 않았지만, 이 근사는 펠 방정식의 해와 같은 방법으로 얻어질 수 있습니다.^[5] 마찬가지로 태양신 헬리오스의 소의 수를 찾는 고대 단어 문제인 아르키메데스의 소 문제도 펠의 방정식으로 재구성하면 해결할 수 있습니다. 문제가 담긴 원고에는 아르키메데스가 고안하여 에라토스테네스에게 보낸 편지에 기록되어 있으며,^[7] 아르키메데스에 대한 귀속은 오늘날 일반적으로 받아들여지고 있습니다.^[8][9]

AD 250년경에 디오판토스는 방정식을 고려했습니다.

${\displaystyle a^{2}x^{2}+c=y^{2},}$

여기서 a와 c는 고정된 숫자이고, x와 y는 풀어야 할 변수입니다. 이 방정식은 펠의 방정식과는 형식이 다르지만 동등합니다. 디오판토스는 (a, c)에 대해 (1, 1), (1, -1), (1, 12), (3, 9)와 같은 방정식을 풀었습니다. 10세기 페르시아 수학자인 알 카라지는 디오판토스와 비슷한 문제를 연구했습니다.^[10]

인도 수학에서 브라마굽타는 다음을 발견했습니다.

${\displaystyle (x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{2})=(x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2},}$

오늘날 브라마굽타의 정체성으로 알려진 형태의 한 형태 ${\displaystyle 이}$를 사용하여 그는 ${\displaystyle x^{}{}^{}{}^{}}$ - ${\displaystyle Ny}$ 2$$= k${\$displaystyle x^{2}-${\displaystyle {Ny}_{}}$^{2}의 솔루션인 트리플 (x 1, y${\displaystyle {}_{}}$1, ${\displaystyle {}_{}}$ ${\displaystyle 1_{}}${\$displaystyle ($$x_{1$},$$$y_{1$},$$$k_{$1}}$$및$$(${\displaystyle x_{}}$2, ${\displaystyle 2_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle 2_{}}${\$displaystyle x$^{2}-Ny^{2}=k}를 " compose"하여 새 트리플을 생성할 수 있었습니다.

${\displaystyle (x_{1}x_{2}+Ny_{1}y_{2},x_{1}y_{2}+x_{2}y_{1},k_{1}k_{2})}$ and ${\displaystyle (x_{1}x_{2}-Ny_{1}y_{2},x_{1}y_{2}-x_{2}y_{1},$$k_{1}k_{2}).$$}$

이것은 하나의 해로 $시작$하여 x${\displaystyle 2^{}}$ - ${\displaystyle {Ny}^{}}$ 2 = ${\$display x^{2}-Ny^{2}=1}에 대해 무한히 많은 해를 생성할 수 있는 방법을 제공했을 뿐만 아니라, 이러한 구성을 k 1 k 2 {\display k_{1}k_{2}}로 나누어 정수 또는 "nearly 정수" 해를 얻을 수 있는 경우가 많았습니다. 예를 들어 $N$ = ${\displaystyle 92}$ ${\$displaystyle N = $92}$의 경우 Brahamugta는 새로운 트리플(192, 20, 64)을 얻기 위해 트리플(10, 1, 8)(102 - 92(12)) = 8 {\displaystyle 10^{2}-92(1^{2) = 8}부터)을 스스로 구성했습니다. $x{\displaystyle }$ ${\displaystyle x}$와 y ${\displaystyle$ y$}$에 대해 전체를 64("8$")$로 나누면 트리플(24, 5/2, 1)을 얻을 수 있으며, 이 트리플은 자신과 함께 구성할 때 원하는 정수 솔루션(1151, 120, 1)을 제공합니다. 브라마굽타는 이 방법으로 많은 Pell의 방정식을 풀었고, k = ±1, ±2 또는 ±${\displaystyle 4}$에 ${\displaystyle {대해}^{}}$x ${\displaystyle {}^{}}$ - ${\displaystyle {Ny}^{}}$ 2 = k ${\display$ x^{2}-Ny^{2} = k}의 정수 해에서 시작하는 해를 제공한다는 것을 증명했습니다.

펠 방정식을 풀기 위한 첫 번째 일반적인 방법은 1150년 Bháskara II에 의해 주어졌고, Bhamagupta의 방법을 확장했습니다. chakravala (cyclic) 메소드라고 불리는 이 메소드는 비교적 소수인 두 개의 정수 $a{\displaystyle }${\$displaystyle a}$와$b{\displaystyle }$ {\$displaystyle$b$\}$를 선택한 다음 트리플 (${\displaystyle a,}$ ${\displaystyle b,}$ k${\displaystyle )}$ ${\displaystyle (a,$ b, k$)}$를 구성하는 것으로 시작됩니다. $$즉, one which satisfies ${\displaystyle a^{2}-Nb^{2}=k}$) with the trivial triple ${\displaystyle (m,1,m^{2}-N)}$ to get the triple ${\displaystyle {\big (}am+Nb,a+bm,k(m^{2}-N){\big )}}$, which can be scaled down to

${\displaystyle \left({\frac {am+Nb}{k}}, {\frac {a+bm}{k}}, {\frac {m^{2}-N}{k}\right).}$

${\displaystyle \frac{}{}}$ ${\displaystyle m}$을(를) 선택하여${\displaystyle \frac{}{}}$+ bm k {\$displaystyle {\frac {a+bm}{k$$}}}$는 정수이고, 나머지 두 개의 숫자들도 마찬가지입니다. 이러한 $m {\displaystyle$ m$}$중에서 ${\displaystyle \frac{{m2\mathrm{}}^{}}{}}$- ${\displaystyle \frac{}{}}${\$displaystyle${\$frac {m^{2}-N}{k}}$를 최소화하는 것을 선택하고$$ 이 과정을 반복합니다. 이 방법은 항상 해결책으로 끝납니다. Baskara는 이를 사용하여 N=61 사례에 대한 솔루션 x = 1766319049, y = 226153980을 제공했습니다.

17세기에 유럽의 여러 수학자들이 펠의 방정식을 푸는 방법을 재발견했습니다. 피에르 드 페르마는 방정식을 푸는 방법을 발견했고, 1657년 편지에서 영국 수학자들에게 도전이라고 발표했습니다.^[12] 베르나르 프레니클 드 베시는 케넬름 디비에게 보낸 편지에서 페르마는 N에서 150까지의 가장 작은 해를 찾았고, 존 월리스에게 N = 151 또는 313의 경우를 해결하도록 도전했다고 말했습니다. Wallis와 William Brounker 모두 이러한 문제에 대한 해결책을 제시했지만 Wallis는 편지에서 해결책이 Brounker 때문이라고 제안했습니다.^[13]

존 펠이 방정식과 연결된 것은 토마스 브랭커가 요한 란의 1659년 저서 튜셰 대수를^{[note 2]} 영어로 번역한^[14] 것을 브랭커의 방정식 풀이에 대한 토론과 함께 수정했다는 것입니다. 레온하르트 오일러는 이 풀이가 펠 때문이라고 잘못 생각했고, 그 결과 방정식의 이름을 펠의 이름을 따서 지었습니다.^[4]

$P{\displaystyle +Qa,}$ ${\displaystyle P+Q{\sqrt {a}}$ 형태의 숫자로 계속되는 분수와 대수적 조작에 기초한 펠 방정식의 일반적인 이론은 1766-1769년 라그랑주에 의해$$ 개발되었습니다.^[15] 특히 라그랑주는 브루커-월리스 알고리즘이 항상 종료된다는 증거를 제시했습니다.

솔루션

연속 분수를 통한 근본적인 해결

${\displaystyle {hi}_{}}$/ ${\displaystyle {ki}_{}}$ ${\$는 $n{\displaystyle \sqrt{}}$ ${\$에 대한 정규 연속 분수에 대한 수렴 순서를 나타냅니다$$$.$ 이 순서는 독특합니다. 그러면 (${\displaystyle {}_{}}$ ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle 1_{}}$ ${\displaystyle (x_{1}, y_{1})}$쌍이 펠 방정식을 풀고 x를 최소화하면 어떤 i에 대하여 x = h 와 y = k를 만족합니다. 이 쌍을 근본적인 해결책이라고 합니다. 따라서, Pell의 방정식에 대한 해가 발견될 때까지 계속적인 분수 팽창을 수행하고 각각의 연속적인 수렴을 테스트함으로써 근본적인 해를 찾을 수 있습니다.^[16]

빠른 정수 곱셈을 위한 Schönhage-Strassen 알고리즘의 도움을 받아 연속 분수법을 사용하여 기본적인 해를 찾는 시간은 (${\displaystyle {x\mathrm{}}_{}}{\displaystyle }$1${\displaystyle {}_{}}$ ${\displaystyle {y\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle$ ($x_{1}, y_{1})}$ 쌍의 자릿수인 해 크기의 로그 인자 내에 있습니다$.$ 그러나 이것은 다항 시간 알고리즘이 아닙니다. 왜냐하면 용액의 자릿수가 입력 값 n의 자릿수의 다항식보다 훨씬 큰 √n만큼 클 수 있기 때문입니다.

기본 솔루션의 추가 솔루션

기본적인 해가 발견되면, 나머지 모든 해들은 대수적으로^[17] 다음으로부터 계산될 수 있습니다.

${\displaystyle x_{k}+y_{k}{\sqrt {n}}=(x_{1}+y_{1}{\sqrt {n}})^{k}}$

오른쪽을 확장하여 양쪽에서$$ $n{\displaystyle \sqrt{}}$ ${\$의 계수를 동일하게 하고 양쪽에서 다른 항을 동일하게 합니다. 이것은 재발 관계를 산출합니다.

${\displaystyle x_{k+1}=x_{1}x_{k}+ny_{1}y_{k},}$

${\displaystyle y_{k+1}=x_{1}y_{k}+y_{1}x_{k}}$

간결한 표현과 더 빠른 알고리즘

기본적인 해 (x₁₁, y)를 이진수의 쌍으로 적는 것은 많은 수의 비트를 필요로 할 수도 있지만, 많은 경우에 더 간결하게 형태로 표현될 수 있습니다.

${\displaystyle x_{1}+y_{1}{\sqrt {n}}=\prod _{i=1}^{t}(a_{i}+b_{i}{\sqrt {n}})^{c_{i}}}$

훨씬_ii 작은 정수 a, b, c를_i 사용합니다.

예를 들어, 아르키메데스의 소 문제는 Pell 방정식 ${\displaystyle x^{}}2$ - ${\displaystyle 410}$ ${\displaystyle 286}$ ${\displaystyle 423}$ ${\displaystyle 278}$ ${\displaystyle {}^{}}$ ${\displaystyle y^{}}$ 2 = ${\displaystyle$ x^{2}-410\,286\,423\,278\,424y^{2}=1}과 같으며, 그 근본적인 해는 명시적으로 기록될 경우 206545자리입니다. 그러나 솔루션도 다음과 같습니다.

${\displaystyle x_{1}+y_{1}{\sqrt {n}}=u^{2329},}$

어디에

${\displaystyle u=x'_{1}+y'_{1}{\sqrt {4\,729\,494}}=(300\,426\,607\,914\,281\,713\,365{\sqrt {609}}+84\,129\,507\,677\,858\,393\,258{\sqrt {7766}})^{2}}$

$그리고{\displaystyle {}_{}^{}}$ x ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\$과 $y{\displaystyle {}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\$은 각각 45자리와 41자리의 소수점을 갖습니다$$.^[17]

정수 인수분해를 위한 2차 체 접근법과 관련된 방법은 √어에 의해 생성된 수 필드에서 소수들 사이의 관계를 수집하고 이러한 관계를 결합하여 이러한 유형의 곱 표현을 찾는 데 사용될 수 있습니다. Pell의 방정식을 푸는 결과 알고리즘은 여전히 다항식 이상의 시간이 걸리지만 연속분수법보다 더 효율적입니다. 일반화된 리만 가설의 가정하에서, 그것은 시간이 걸리는 것으로 보일 수 있습니다.

${\displaystyle \exp O({\sqrt {\log N\log N}}),}$

여기서 N = log n은 2차 체와 마찬가지로 입력 크기입니다.

양자 알고리즘

Hallgren은 양자 컴퓨터가 다항식 시간에 Pell의 방정식의 해에 대한 곱의 표현을 위에서 설명한 바와 같이 찾을 수 있다는 것을 보여주었습니다.^[18] 홀그렌의 알고리즘은 실제 이차수 장의 단위군을 구하는 알고리즘으로 해석할 수 있는데, 슈미트와 뵐머에 의해 보다 일반적인 장으로 확장되었습니다.^[19]

예

예를 들어, n = 7에 대한 펠 방정식의 예를 생각해 보십시오. 즉,

${\displaystyle x^{2}-7y^{2}=1.}$

7의 제곱근에 대한 수렴 순서는

h/k(conver젠트)	h2 - 7k2 (펠형 근사치)
2/1	−3
3/1	+2
5/2	−3
8/3	+1

따라서 근본적인 해결책은 쌍(8, 3)에 의해 형성됩니다. 이 해에 순환 공식을 적용하면 해의 무한한 수열이 생성됩니다.

(1, 0); (8, 3); (127, 48); (2024, 765); (32257, 12192); (514088, 194307); (8193151, 3096720); (130576328, 49353213); ... (sequence A001081 (x) and A001080 (y) in OEIS)

가장 작은 솔루션은 매우 클 수 있습니다. $예$를 들어, ${\displaystyle x^{}}$2 - ${\displaystyle {}^{}}$ ${\displaystyle y^{}}$ 2 =${\displaystyle 1}${\displaystyle x^{2}-313 y^{2}=1}의 가장 작은 해는 (32188120829134849, 1819380158564160)이며, 이것이 바로 Frenicle이 Wallis에게 도전한 방정식입니다. $x$ ${\displaystyle 2^{}}$- ${\displaystyle {}^{}}$ ${\displaystyle 2^{}}$ = 1${\$displaystyle x^{2}-ny^{2}=${\displaystyle 1}$}의 최소 해가 n의 최소 해보다 크도록 n의 값은 다음과 같습니다.

1, 2, 5, 10, 13, 29, 46, 53, 61, 109, 181, 277, 397, 409, 421, 541, 661, 1021, 1069, 1381, 1549, 1621, 2389, 3061, 3469, 4621, 4789, 4909, 5581, 6301, 6829, 8269, 8941, 9949, ... (sequence A033316 in the OEIS).

(이러한 기록은 x의 경우 OEIS: A033315, y의 경우 OEIS: A033319를 참조하십시오.)

펠 방정식의 기본해법 목록

다음은 n ≤ 128인 $x$ ${\displaystyle 2^{}}$- n ${\displaystyle 2^{}}$ = 1${\$displaystyle x^{2}-ny^{2}=${\displaystyle 1}$}에 대한 기본 솔루션 목록입니다. n이 정수 제곱일 때 자명한 해(1, 0)를 제외하고는 해가 없습니다. x의 값은 시퀀스 A002350이고 y의 값은 OEIS의 시퀀스 A002349입니다.

n	x	y
1	–	–
2	3	2
3	2	1
4	–	–
5	9	4
6	5	2
7	8	3
8	3	1
9	–	–
10	19	6
11	10	3
12	7	2
13	649	180
14	15	4
15	4	1
16	–	–
17	33	8
18	17	4
19	170	39
20	9	2
21	55	12
22	197	42
23	24	5
24	5	1
25	–	–
26	51	10
27	26	5
28	127	24
29	9801	1820
30	11	2
31	1520	273
32	17	3

n	x	y
33	23	4
34	35	6
35	6	1
36	–	–
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
49	–	–
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
64	–	–

n	x	y
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
81	–	–
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

n	x	y
97	62809633	6377352
98	99	10
99	10	1
100	–	–
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
121	–	–
122	243	22
123	122	11
124	4620799	414960
125	930249	83204
126	449	40
127	4730624	419775
128	577	51

연결

펠의 방정식은 수학의 다른 중요한 과목들과 연관이 있습니다.

대수적 수론

펠의 방정식은 공식과 같이 대수적 수론과 밀접한 관련이 있습니다.

${\displaystyle x^{2}-ny^{2}=(x+y{\sqrt {n}})(x-y{\sqrt {n}})}$

는 링 $Z{\displaystyle \mathbb{}}$[ ${\displaystyle n}$] ${\displaystyle \mathbb {Z} [{\sqrt {n}}}$ 및$$ 밀접하게 관련된 $2차{\displaystyle \mathbb{}}$ 필드 Q${\displaystyle }$(${\displaystyle n)}$ ${\displaystyle \mathbb {Q}({\sqrt {n}})$의 표준입니다$.$ 따라서, $x{\displaystyle }$+ ${\displaystyle y}$ ${\$ x$+y{\sqrt {n}}$가 $Z{\displaystyle \mathbb{}}$[${\displaystyle n]}$ ${\displaystyle \mathbb {Z} [{\sqrt {n}}$에서 norm 1인 단위인 경우에만 정수 쌍${\displaystyle }$(${\displaystyle x,}$ ${\displaystyle y)}$ ${\displaystyle (x,$ y$)}$는 Pell의 방정식을 해결합니다$.$^[21] 디리클레의 단위 정리, $Z{\displaystyle \mathbb{}}$[${\displaystyle n]}$ ${\displaystyle \mathbb {Z} [{\sqrt {n}}$의 모든 단위가 단일 기본 단위의 거듭제곱(및 부호에 의한 곱)으로 표현될$$ 수 있다는 것은 펠 방정식에 대한 모든 해가 기본 해로부터 생성될 수 있다는 사실을 대수적으로 재표명한 것입니다.^[22] 기본 단위는 일반적으로 Pell과 같은 방정식을 풀면 찾을 수 있지만 기본 단위가 1이 아닌 norm -1을 가질 수 있고 계수가 정수가 아닌 반 정수일 수 있기 때문에 항상 Pell 방정식 자체의 기본 솔루션과 직접적으로 일치하는 것은 아닙니다.

체비셰프 다항식

Demeyer는 Pell의 방정식과 체비셰프 다항식 사이의 관계를 언급합니다. 만약 ${\displaystyle {Ti}_{}}$(${\displaystyle x)}$ ${\displaystyle T_{i}(x)}$와 ${\displaystyle {Ui}_{}}$ (${\displaystyle x)}$ ${\displaystyle U_{i}(x)}$가 각각 제1종과 제2종의 체비셰프 다항식이라면, 그런 다음 이 다항식들은 $n$ = ${\displaystyle x^{}2}$ -$$1 {\displaystyle n = x^{2}-1$\}$인 임의의 다항식 $R{\displaystyle }$[${\displaystyle x}$] ${\displaystyle R[x]}$에서 펠 방정식의 형태를 만족합니다.

${\displaystyle T_{i}^{2}-(x^{2}-1)U_{i-1}^{2}=1.}$

따라서 이러한 다항식은 기본 해의 거듭제곱에 대한 펠 방정식의 표준 기법에 의해 생성될 수 있습니다.

${\displaystyle T_{i}+U_{i-1}{\sqrt {x^{2}-1}}=(x+{\sqrt {x^{2}-1}})^{i}.}$

$({\displaystyle {xi}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle (x_{i}, y_{i})}$가 임의의 정수 펠 방정식의 해일 경우 ${\displaystyle {xi}_{}}$ = ${\displaystyle Ti}$ (${\displaystyle x_{}}$1) {\displaystyle x_{i}=$T_{i}(x_{1})}$ ${\displaystyle {및}_{}}$ y $=$ ${\displaystyle y}$ $Ui$ - 1(x 1) {\displaystyle y_{i} $=$ y_{1$}U_{i-1}(x_{1$^[24]

연속분수

n {\displaystyle {\sqrt {n}}의 연속 분수의 관점에서 Pell의 $방정식$ ${\displaystyle x^{}}$2 - ${\displaystyle {ny}^{}}$ 2 = ${\$displaystyle x^{2}-ny^{2}=1}의 해의 일반적인 전개를 제시할 수 있습니다. 해 x와 y는 n의 제곱근에 근사하므로 2차 무리수에 대한 연속 분수 근사의 특별한 경우입니다.^[16]

연속 분수에 대한 관계는 Pell의 방정식에 대한 해가 모듈식 그룹의 반군 부분 집합을 형성한다는 것을 의미합니다. 따라서, 예를 들어, p와 q가 펠 방정식을 만족하면,

${\displaystyle {\begin{pmatrix}p&q\nq&p\end{pmatrix}}}$

단위 행렬식입니다. 그러한 행렬의 곱은 정확히 같은 형태를 취하므로 모든 그러한 곱은 Pell의 방정식에 대한 해를 산출합니다. 이것은 부분적으로 연속적인 분수의 연속적인 수렴이 동일한 성질을 공유한다는 사실로부터 발생하는 것으로 이해될 수 있습니다: 만약_k−1 p/q와_k−1 p/q가_kk 연속적인 분수의 연속적인 두 수렴이라면, 행렬은

${\displaystyle {\begin{pmatrix}p_{k-1}&p_{k}\\q_{k-1}&q_{k}\end{pmatrix}}}$

행렬식(-1)이 있습니다.^k

매끄러운 숫자

Störmer의 정리는 Pell 방정식을 적용하여 연속적인 매끄러운 수의 쌍, 즉 소수 인자가 모두 주어진 값보다 작은 양의 정수를 찾습니다.^[25][26] 이 이론의 일환으로 Störmer는 Pell의 방정식에 대한 해들 간의 분할 관계도 조사했는데, 특히 기본 해 이외의 해들은 각각 분할되지 않는 소인수를 가지고 있음을 보여주었습니다.^[25]

음의 펠 방정식

음의 펠 방정식은 다음과 같이 주어집니다.

${\displaystyle x^{2}-ny^{2}=-1}$

또한 광범위하게 연구되어 왔습니다. 같은 방법의 연속분수로 풀 수 있으며, 연속분수의 주기가 홀수 길이인 경우에만 해를 갖습니다. 그러나 어떤 뿌리가 홀수 주기 길이를 갖는지 알 수 없으며 따라서 음의 Pell 방정식이 언제 풀 수 있는지 알 수 없습니다. 용해성을 위해 필요한(충분하지는 않지만) 조건은 n이 4로 분할되지 않거나 4k + 3의 소수로 분할되지 않는 것입니다.^{[note 3]} 따라서 예를 들어 x - 3ny = -1은 절대 해결할 수 없지만 x - 5ny = -1은 해결할 수 있습니다.

x - ny = -1을 풀 수 있는 처음 몇 개의 수 n은 다음과 같습니다.

1, 2, 5, 10, 13, 17, 26, 29, 37, 41, 50, 53, 58, 61, 65, 73, 74, 82, 85, 89, 97, ...(OEIS에서 서열 A031396).

$\alpha$ = π${\displaystyle {}_{}}$ j j가 홀수(1 - 2 j) {\displaystyle \alpha =\Pi _{j\text{ is oder}}(1-2^{j})}입니다. 음의 펠 방정식이 풀 수 있는 형태 4m + 1의 k개의 소수로 나눈 제곱 없는 n의 비율은 적어도 α입니다.^[28] 소수의 개수가 고정되어 있지 않을 때 비율은 1 - α로 주어집니다.^[29][30]

음의 펠 방정식이 특정 n에 대한 해를 갖는 경우, 그 근본적인 해는 정의 방정식의 양변을 제곱함으로써 양의 경우에 대한 근본적인 해로 이어집니다.

${\displaystyle (x^{2}-ny^{2})^{2}=(-1)^{2}}$

암시하는

${\displaystyle (x^{2}+ny^{2})^{2}-n(2xy)^{2}=1.}$

앞에서 언급한 바와 같이 음의 펠 방정식을 풀 수 있다면 양의 펠 방정식과 같이 연속 분수의 방법을 사용하여 해를 구할 수 있습니다. 그러나 재귀 관계는 약간 다르게 작동합니다. $({\displaystyle x}$+ ${\displaystyle n}$ ${\displaystyle y}$)${\displaystyle }$(${\displaystyle x}$- ${\displaystyle n}$ y${\displaystyle }$) =${\displaystyle }$- 1$${\$displaystyle (x+{\sqrt {n}}y$) (x-${\sqrt {n}y$) = ${\displaystyle -1}$} 이므로, 다음 해는 i (x k + n y k ) = (i (x + n y$))$ k {\displaystyle i(x_{k}+{\sqrt {n}y_{k}) = (i(x+{\sqrt {n}}y)로 결정됩니다.$^{k}}:$ 매치가$$ 있을 때, 즉 k ${\displaystyle$ k$}$가 홀수일 $때{\displaystyle }$. 결과적인 재귀 관계는 (식의 2차 성질로 인해 중요하지 않은 모듈로 마이너스 부호)입니다.

${\displaystyle x_{k}=x_{k-2}x_{1}^{2}+nx_{k-2}y_{1}^{2}+2ny_{k-2}y_{1}x_{1},}$

${\displaystyle y_{k}=y_{k-2}x_{1}^{2}+ny_{k-2}y_{1}^{2}+2x_{k-2}y_{1}x_{1},}$

음의 펠 방정식에 대한 무한한 해의 탑을 제공합니다.

일반화 펠 방정식

방정식이.

${\displaystyle x^{2}-dy^{2}=N}$

일반화^{[citation needed]}(또는 일반화^[16]) 펠 방정식이라고 합니다. ${\displaystyle {방정식}^{}}$ $u$ 2${\displaystyle {}^{}}$- ${\displaystyle d}$ ${\displaystyle v^{}}$ ${\displaystyle 2}$ = 1${\$displaystyle u^{2} - dv^{2} = 1}은 대응하는 Pell의 분해능입니다. 1768년 라그랑주는 방정식을 풀기 위해 재귀적 알고리즘을 제시하여 를 N< ${\$N$<{\sqrt {d}}$ 경우로 줄였습니다^[31][32] 위에서 설명한 연속 분수 방법을 사용하여 이러한 해결책을 도출할 수 있습니다.

If ${\displaystyle (x_{0},y_{0})}$ is a solution to ${\displaystyle x^{2}-dy^{2}=N,}$ and ${\displaystyle (u_{n},v_{n})}$ is a solution to ${\displaystyle u^{2}-dv^{2}=1,}$ then ${\displaystyle (x_{n},$$y_{n})}$ such that ${\displaystyle x_{n}+y_{n}{\sqrt {d}}={\big (}x_{0}+y_{0}{\sqrt {d}}{\big )}{\big (}u_{n}+v_{n}{\sqrt {d}}{\big )}}$ is a solution to ${\displaystyle x^{2}-dy^{2}=N}$, 곱셈 원리라는 ^[16]원리 솔루션${\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle y_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle (x_{n}, y_{n})}$을 솔루션${\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle (x_{0}, y_{0})}$의 Pell 배수라고 합니다$$$.$

$x$ ${\displaystyle 2^{}}$- ${\displaystyle {dy}^{}}$ 2 = ${\$displaystyle x^{2}-dy^{2}= N}에 대한 유한 개의 해 집합이 존재하므로 모든 해는 해당 집합에서 해의 Pell 배수가 됩니다. 특히$,$ (${\displaystyle u,}$v$)$ {\$displaystyle (u,$ v$)}$가 u${\displaystyle {}^{}2}$ - ${\displaystyle {}^{}}$ v ${\displaystyle 2^{}}$ =${\displaystyle 1}${\display u^{2} - dv^{2}=1}의 기본 해일 경우, 방정식의 각 해는 해 (x, y) {\displaystyle (x,$y)}$ with ${\displaystyle x \leq {\sqrt { N }}\left({\sqrt { U }}+1\right)/2}$ and ${\displaystyle y \leq {\sqrt { N }}\left({\sqrt { U }}+1\right)/{\big (}2{\sqrt {d}}{\big )}}$, 여기서 $U$ = ${\displaystyle u}$+$v$ {\displaystyle U = u + v {\sqrt {d}}입니다.

x와 y가 < ${\$N$<{\sqrt {d}}$인 Pell's 방정식의 양의 정수 해이면x /${\displaystyle }y{\displaystyle }$ ${\displaystyle$ x$/y}$는 d ${\$의 연속 분수에 대한 수렴입니다$.$^[33]

일반화된 Pell's 방정식의 해는 특정 디오판토스 방정식과 특정 고리의 단위를 푸는 데 사용되며,^[34][35] 양자 정보 이론의 SIC-POVM 연구에서 발생합니다.^[36]

방정식이.

${\displaystyle x^{2}-dy^{2}=4}$

x 2 - dy 2 = 4 {\displaystyle x^{2}-dy^{2}=${\displaystyle 4}$}에 대한 최소 해를 찾을 수 있다면 방정식의 모든 해는 경우 N = 1 {\displaystyle N =1}과 유사한 방식으로 생성될 수 있다는 점에서 해상도 $x$ ${\displaystyle 2^{}}$- ${\displaystyle {dy}^{}}$ 2 = 1$${\$displaystyle x^{2}-dy^{2$}=1$}$과 유사합니다. For certain ${\displaystyle d}$, solutions to ${\displaystyle x^{2}-dy^{2}=1}$ can be generated from those with ${\displaystyle x^{2}-dy^{2}=4}$, in that if ${\displaystyle d\equiv 5{\pmod {8}},$$}$ then every third solution to ${\displaystyle x^{2}-dy^{2}=4}$ has ${\displaystyle x,y}$ even, generating a solution to ${\displaystyle x^{2}-dy^{2}=1}$.^[16]

메모들

참고문헌

더보기

• Edwards, Harold M. (1996) [1977]. Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. Graduate Texts in Mathematics. Vol. 50. Springer-Verlag. ISBN 0-387-90230-9. MR 0616635.
• Pinch, R. G. E. (1988). "Simultaneous Pellian equations". Math. Proc. Cambridge Philos. Soc. 103 (1): 35–46. Bibcode:1988MPCPS.103...35P. doi:10.1017/S0305004100064598. S2CID 123098216.
• Whitford, Edward Everett (1912). The Pell equation (PhD Thesis). Columbia University.
• Williams, H. C. (2002). "Solving the Pell equation". In Bennett, M. A.; Berndt, B. C.; Boston, N.; Diamond, H. G.; Hildebrand, A. J.; Philipp, W. (eds.). Surveys in number theory: Papers from the millennial conference on number theory. Natick, MA: A K Peters. pp. 325–363. ISBN 1-56881-162-4. Zbl 1043.11027.

외부 링크

• Weisstein, Eric W. "Pell's equation". MathWorld.
• O'Connor, John J.; Robertson, Edmund F., "Pell's equation", MacTutor History of Mathematics Archive, University of St Andrews
• 펠 방정식 해결사(n은 상한이 없음)
• Pell equation solver (n < 10, x - ny = ±1, ±2, ±3, ±4로 용액을 반송할 수 있음)