펠 방정식(Pell's equation)

Edit

$\sqrt{d}$ 를 연분수 전개할때 얻어지는 convergents ${h_i}/{k_i}$ 가 펠방정식의 해가 되는 를 찾을 수 있으며, 이 때 값을 가장 작게 하는 해를 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}^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 중에서 찾을 수 있다. ■

$\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$
따라서 펠방정식 의 fundamental solution 은 이된다