"펠 방정식(Pell's equation)"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
잔글 (찾아 바꾸기 – “수학사연표” 문자열을 “수학사 연표” 문자열로)
23번째 줄: 23번째 줄:
  
 
무리수 <math>\alpha</math>에 대하여, 유리수 <math>p/q</math>가 아래의 부등식을 만족시키는 경우,  <math>p/q</math>는 무리수 <math>\alpha</math>의 단순연분수 전개의 convergents 중의 하나이다
 
무리수 <math>\alpha</math>에 대하여, 유리수 <math>p/q</math>가 아래의 부등식을 만족시키는 경우,  <math>p/q</math>는 무리수 <math>\alpha</math>의 단순연분수 전개의 convergents 중의 하나이다
−
 
+
:<math>|\alpha-\frac{p}{q}|<\frac{1}{2{q^2}}</math>
−
<math>|\alpha-\frac{p}{q}|<\frac{1}{2{q^2}}</math>
 
  
 
이 정리를 이용하자.
 
이 정리를 이용하자.
  
−
펠 방정식의 정수해 <math>x_ {1}^2-dy_ {1}^2=1</math> 는 <math>x_ {1}^2-dy_ {1}^2=(x_{1}+\sqrt{d}y_{1})(x_{1}-\sqrt{d}y_{1})=1</math>를 만족시키므로,
+
펠 방정식 <math>x_ {1}^2-dy_ {1}^2=1</math>의 정수해 $(x_1,y_1)$는  
−
 
+
:<math>x_ {1}^2-dy_ {1}^2=(x_{1}+\sqrt{d}y_{1})(x_{1}-\sqrt{d}y_{1})=1</math>를 만족시키므로,
−
<math>|x_{1}-\sqrt{d}y_{1}|=\frac{1}{|x_{1}+\sqrt{d}y_{1}|}</math>
+
:<math>|x_{1}-\sqrt{d}y_{1}|=\frac{1}{|x_{1}+\sqrt{d}y_{1}|}</math>
−
 
+
:<math>|\sqrt{d}-\frac{x_{1}}{y_{1}}|=\frac{1}{|x_{1}+\sqrt{d}y_{1}||y_{1}|}<\frac{1}{\sqrt{d}y_ {1}^{2}}\leq \frac{1}{2y_ {1}^{2}}</math>
−
<math>|\sqrt{d}-\frac{x_{1}}{y_{1}}|=\frac{1}{|x_{1}+\sqrt{d}y_{1}||y_{1}|}<\frac{1}{\sqrt{d}y_ {1}^{2}}\leq \frac{1}{2y_ {1}^{2}}</math>
 
−
 
 
−
따라서,  펠 방정식의 해는 연분수 전개의 convergents 중에서 찾을 수 있다. \[FilledSquare]
 
  
−
   
+
따라서, 펠 방정식의 해는 연분수 전개의 convergents 중에서 찾을 수 있다. ■
  
 
   
 
   
 +
==예==
 +
===d=7인 경우===
  
−
==d=7인 경우==
+
* <math>\sqrt{7}</math>의 연분수 전개를 통한 유리수근사:<math>\frac{2}{1},\frac{3}{1},\frac{5}{2},\frac{8}{3},\frac{37}{14}\cdots</math>
−
 
+
*  펠 방정식의 해 찾기:<math>2^2-d\cdot 1^2=-3</math>:<math>3^2-d\cdot 1^2=2</math>:<math>5^2-d\cdot 2^2=-3</math>:<math>8^2-d\cdot 3^2=1</math>:<math>37^2-d\cdot 14^2=-3</math>
−
* <math>\sqrt{7}</math>의 연분수 전개를 통한 유리수근사:<math>\frac{2}{1},\frac{3}{1},\frac{5}{2},\frac{8}{3},\frac{37}{14}\cdots</math><br>
 
−
*  펠 방정식의 해 찾기:<math>2^2-d\cdot 1^2=-3</math>:<math>3^2-d\cdot 1^2=2</math>:<math>5^2-d\cdot 2^2=-3</math>:<math>8^2-d\cdot 3^2=1</math>:<math>37^2-d\cdot 14^2=-3</math><br>
 
 
* 따라서 펠 방정식 <math>x^2-7y^2=1</math>의 fundamental solution 은 <math>(8,3)</math> 이된다
 
* 따라서 펠 방정식 <math>x^2-7y^2=1</math>의 fundamental solution 은 <math>(8,3)</math> 이된다
  
 
   
 
   
  
−
+
===d=13===
−
 
 
−
==d=13==
 
  
 
* fundamental solution <math>(x_ 1,y_ 1)</math> 가 <math>y_ 1>6</math> 를 만족시키는 가장 작은 d
 
* fundamental solution <math>(x_ 1,y_ 1)</math> 가 <math>y_ 1>6</math> 를 만족시키는 가장 작은 d
59번째 줄: 53번째 줄:
 
   
 
   
  
−
==d=61==
+
===d=61===
  
 
   
 
   
65번째 줄: 59번째 줄:
 
   
 
   
  
−
==d=109==
+
===d=109===
−
 
 
−
*  페르마의 문제<br>
 
−
* <math>158070671986249^2 -109\cdot15140424455100^2=1</math><br>
 
  
−
   
+
* 페르마의 문제
−
 
+
* <math>158070671986249^2 -109\cdot15140424455100^2=1</math>
−
 
  
 
   
 
   
96번째 줄: 86번째 줄:
 
* [[체비셰프 다항식]]
 
* [[체비셰프 다항식]]
 
* [[루카스 수열]]
 
* [[루카스 수열]]
 +
  
 
==매스매티카 파일 및 계산 리소스==
 
==매스매티카 파일 및 계산 리소스==
101번째 줄: 92번째 줄:
 
* https://docs.google.com/leaf?id=0B8XXo8Tve1cxNTU4ZmMyMmQtMjNkZi00YWIwLWIzM2ItNzNiNTQ2YTRkMWY1&sort=name&layout=list&num=50
 
* https://docs.google.com/leaf?id=0B8XXo8Tve1cxNTU4ZmMyMmQtMjNkZi00YWIwLWIzM2ItNzNiNTQ2YTRkMWY1&sort=name&layout=list&num=50
 
* [http://projecteuler.net/problem=66 Project Euler, Problem 66]
 
* [http://projecteuler.net/problem=66 Project Euler, Problem 66]
−
* http://www.wolframalpha.com/input/?i=
 
−
* http://functions.wolfram.com/
 
−
* [http://dlmf.nist.gov/ NIST Digital Library of Mathematical Functions]
 
−
* [http://www.research.att.com/%7Enjas/sequences/index.html The On-Line Encyclopedia of Integer Sequences]
 
  
−
* [[매스매티카 파일 목록]]
 
  
 
==사전 형태의 자료==
 
==사전 형태의 자료==
115번째 줄: 101번째 줄:
 
   
 
   
  
−
 
  
 
==관련논문==
 
==관련논문==
  
−
* [http://arxiv.org/abs/math/0311306 Conics - a Poor Man's Elliptic Curves]Franz Lemmermeyer, arXiv:math/0311306v1<br>
+
* [http://arxiv.org/abs/math/0311306 Conics - a Poor Man's Elliptic Curves]Franz Lemmermeyer, arXiv:math/0311306v1
−
* [http://www.ams.org/notices/200202/fea-lenstra.pdf Solving the Pell Equation]H. W. Lenstra Jr. Notices of the AMS 49 (2002), 182\[Dash]92
+
* [http://www.ams.org/notices/200202/fea-lenstra.pdf Solving the Pell Equation]H. W. Lenstra Jr. Notices of the AMS 49 (2002), 182-92
 
* Lehmer, D. H. 1928. On the Multiple Solutions of the Pell Equation. The Annals of Mathematics 30, no. 1/4. Second Series (January 1): 66-72. doi:[http://dx.doi.org/10.2307/1968268 10.2307/1968268].  
 
* Lehmer, D. H. 1928. On the Multiple Solutions of the Pell Equation. The Annals of Mathematics 30, no. 1/4. Second Series (January 1): 66-72. doi:[http://dx.doi.org/10.2307/1968268 10.2307/1968268].  
−
* [http://www.jstor.org/action/doBasicSearch?Query=Pell %27 s+equation http://www.jstor.org/action/doBasicSearch?Query=Pell's+equation]
 
−
* http://www.jstor.org/action/doBasicSearch?Query=
 
−
 
−
 
  
−
 
−
 
−
 
−
*  도서검색<br>
 
−
** http://books.google.com/books?q=
 
−
** http://www.amazon.com/s/ref=nb_ss _gw?url=search-alias %3 Dstripbooks&field-keywords=
 
−
** http://book.daum.net/search/mainSearch.do?query=
 
−
 
−
 
−
 
−
 
  
−
==블로그==
+
[[분류:초등정수론]]
−
* 구글 블로그 검색 http://blogsearch.google.com/blogsearch?q=펠방정식
 

2013년 4월 16일 (화) 08:05 판

개요

  • \(x^2-dy^2=1\) (\(d\) 는 완전제곱수를 약수로 갖지 않는 1보다 큰 자연수)형태의 디오판투스 방정식
  • 연분수 전개를 통하여 모든 해를 구할 수 있음
  • 해의 집합은 군의 구조를 통하여 이해할 수 있음
  • \(x^2-dy^2=\pm 1\) 의 자연수 해를 구하는 문제는 실수 이차 수체의 unit 을 구하는 문제와 같음



연분수 전개와 fundamental solution

  • \(\sqrt{d}\) 를 연분수 전개할때 얻어지는 convergents \({h_i}/{k_i}\) 가 펠 방정식의 해가 되는 \(x=h_i, y=k_i\) 를 찾을 수 있으며, 이 때 \(x\)값을 가장 작게 하는 해를 fundamental solution 이라 한다.

(정리)

펠 방정식의 해는 연분수 전개의 convergents 중에서 찾을 수 있다.

(증명)

연분수와 유리수 근사 에서 펠 방정식에 관련한 중요한 정리는 다음과 같다

무리수 \(\alpha\)에 대하여, 유리수 \(p/q\)가 아래의 부등식을 만족시키는 경우, \(p/q\)는 무리수 \(\alpha\)의 단순연분수 전개의 convergents 중의 하나이다 \[|\alpha-\frac{p}{q}|<\frac{1}{2{q^2}}\]

이 정리를 이용하자.

펠 방정식 \(x_ {1}^2-dy_ {1}^2=1\)의 정수해 $(x_1,y_1)$는 \[x_ {1}^2-dy_ {1}^2=(x_{1}+\sqrt{d}y_{1})(x_{1}-\sqrt{d}y_{1})=1\]를 만족시키므로, \[|x_{1}-\sqrt{d}y_{1}|=\frac{1}{|x_{1}+\sqrt{d}y_{1}|}\] \[|\sqrt{d}-\frac{x_{1}}{y_{1}}|=\frac{1}{|x_{1}+\sqrt{d}y_{1}||y_{1}|}<\frac{1}{\sqrt{d}y_ {1}^{2}}\leq \frac{1}{2y_ {1}^{2}}\]

따라서, 펠 방정식의 해는 연분수 전개의 convergents 중에서 찾을 수 있다. ■


예

d=7인 경우

  • \(\sqrt{7}\)의 연분수 전개를 통한 유리수근사\[\frac{2}{1},\frac{3}{1},\frac{5}{2},\frac{8}{3},\frac{37}{14}\cdots\]
  • 펠 방정식의 해 찾기\[2^2-d\cdot 1^2=-3\]\[3^2-d\cdot 1^2=2\]\[5^2-d\cdot 2^2=-3\]\[8^2-d\cdot 3^2=1\]\[37^2-d\cdot 14^2=-3\]
  • 따라서 펠 방정식 \(x^2-7y^2=1\)의 fundamental solution 은 \((8,3)\) 이된다


d=13

  • fundamental solution \((x_ 1,y_ 1)\) 가 \(y_ 1>6\) 를 만족시키는 가장 작은 d
  • \(649^2-13\cdot180^2=1\)



d=61

d=109

  • 페르마의 문제
  • \(158070671986249^2 -109\cdot15140424455100^2=1\)


역사



메모

관련된 항목들


매스매티카 파일 및 계산 리소스


사전 형태의 자료



관련논문

원본 주소 "https://wiki.mathnt.net/index.php?title=펠_방정식(Pell%27s_equation)&oldid=27638"