단순 연분수

수학에서, 단순 연분수(영어: simple continued fraction) 또는 정칙 연분수(영어: regular continued fraction)는 다음과 같은 꼴의 분수를 뜻한다.

${\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots }}}}}}}}}$

여기서 ${\displaystyle a_{0}}$은 정수, ${\displaystyle a_{1},a_{2},a_{3},\dots }$은 유한 또는 무한 개의 양의 정수이다.

모든 단순 연분수는 유일한 실수를 나타내며, 모든 실수는 본질적으로 유일한 단순 연분수 전개를 갖는다. 실수의 단순 연분수 전개가 유한할 필요충분조건은 유리수인 것이다. 실수의 단순 연분수 전개가 순환일 필요충분조건은 2차 대수적 수인 것이다. 실수 ${\displaystyle x}$의 단순 연분수 전개가 순순환일 필요충분조건은 ${\displaystyle x}$가 2차 대수적 수이며, ${\displaystyle x>1}$이며, ${\displaystyle x}$의 (${\displaystyle \mathbb {Q} (x)}$에서의) 켤레 ${\displaystyle {\bar {x}}}$가 ${\displaystyle -1<{\bar {x}}<0}$을 만족시키는 것이다.

단순 연분수의 이론과 방법은 실수의 유리수 근사와 펠 방정식의 풀이 등에 사용된다.

단순 연분수를 이루는 수열의 선택은 임의적이며, 실수의 단순 연분수 전개의 근사분수들은 최적 유리 근사를 통해 특징지을 수 있다. 이는 일반적인 연분수가 지니지 않는 좋은 성질이다. 예를 들어, 대각 연분수는 일부 수열에 대하여 정의되지 않으며, 최근 정수 연분수의 근사분수들은 간단하게 특징지을 수 없다.^{[1]:16, Notes, §2} 따라서 단순 연분수는 다른 종류의 연분수보다 널리 응용되며, 흔히 연분수로 줄여 부른다.

정의

정수 ${\displaystyle a_{0}\in \mathbb {Z} }$와 양의 정수 ${\displaystyle a_{1},\dots ,a_{n}\in \mathbb {Z} ^{+}}$의 유한 단순 연분수(영어: finite simple continued fraction)는 다음과 같다.

${\displaystyle [a_{0};a_{1},\dots ,a_{n}]=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{n}}}}}}}}}}$

정수 ${\displaystyle a_{0}\in \mathbb {Z} }$와 양의 정수 ${\displaystyle a_{1},a_{2},\dots \in \mathbb {Z} ^{+}}$의 무한 단순 연분수(영어: finite simple continued fraction)는 다음과 같은 형식적인 식이다.

${\displaystyle [a_{0};a_{1},a_{2},\dots ]=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots }}}}}}}}}$

만약 이 무한 단순 연분수의 유한한 절단 ${\displaystyle [a_{0};a_{1},\dots ,a_{n}]}$들로 이루어진 수열이 어떤 실수로 수렴한다면, 무한 단순 연분수 ${\displaystyle [a_{0};a_{1},\dots ,a_{n}]}$가 이 실수로 수렴한다고 한다. 즉, 무한 단순 연분수의 값을 다음과 같이 정의한다.

${\displaystyle [a_{0};a_{1},a_{2},\dots ]=\lim _{n\to \infty }[a_{0};a_{1},\dots ,a_{n}]}$

양의 정수 ${\displaystyle k}$가 주어졌을 때,

• 주기 ${\displaystyle k}$의 순환 단순 연분수(영어: periodic simple continued fraction)는 다음과 같은 꼴의 무한 단순 연분수이다.

  ${\displaystyle [a_{0};a_{1},\dots ,a_{n-1},a_{n},\dots ,a_{n+k-1},a_{n},\dots ,a_{n+k-1},\dots ]}$

• 주기 ${\displaystyle k}$의 순순환 단순 연분수(영어: purely periodic simple continued fraction)는 다음과 같은 꼴의 순환 단순 연분수이다.

  ${\displaystyle [a_{0};\dots ,a_{k-1},a_{0},\dots ,a_{k-1},\dots ]}$

순환 단순 연분수의 최소 주기를 줄여서 주기라고 한다.

유한 또는 무한 단순 연분수 ${\displaystyle [a_{0};a_{1},a_{2},\dots ]}$의 ${\displaystyle n}$번째 근사분수(convergent)는

${\displaystyle [a_{0};a_{1},\dots ,a_{n}]}$

를 뜻한다. 이는 다음과 같은 점화식을 통해 정의할 수도 있다.

${\displaystyle [a_{0};a_{1},\dots ,a_{n}]=h_{n}/k_{n}}$

${\displaystyle h_{-2}=0}$

${\displaystyle h_{-1}=1}$

${\displaystyle h_{n}=a_{n}h_{n-1}+h_{n-2}}$

${\displaystyle k_{-2}=1}$

${\displaystyle k_{-1}=0}$

${\displaystyle k_{n}=a_{n}k_{n-1}+k_{n-2}}$

이 경우 ${\displaystyle h_{n}}$와 ${\displaystyle k_{n}}$은 항상 서로소 정수쌍이다.

유한 또는 무한 단순 연분수 ${\displaystyle [a_{0};a_{1},a_{2},\dots ]}$의 반근사분수(semiconvergent)들은 다음과 같은 꼴의 분수들을 뜻한다.

${\displaystyle [a_{0};a_{1},\dots ,a_{n},a]=(h_{n-1}+ah_{n})/(k_{n-1}+ak_{n})\qquad (n\in \mathbb {Z} ^{+},\;0\leq a\leq a_{n+1})}$

그 밖에도, 유한 또는 무한 단순 연분수 ${\displaystyle [a_{0};a_{1},a_{2},\dots ]}$에 대하여 다음과 같은 용어들을 정의한다.

• ${\displaystyle n}$번째 부분몫(partial quotient): ${\displaystyle a_{n}}$
• ${\displaystyle n}$번째 완전몫(complete quotient): ${\displaystyle [a_{n};a_{n+1},a_{n+2},\dots ]}$

성질

유한 단순 연분수

모든 유한 단순 연분수는 유리수이다. 반대로 모든 유리수는 정확히 두 가지 유한 단순 연분수로 나타내어지며, 이는 다음과 같은 꼴이다.

${\displaystyle [a_{0};a_{1},\dots ,a_{n}]}$

${\displaystyle [a_{0};a_{1},\dots ,a_{n-1},a_{n}-1,1]}$

유리수의 단순 연분수 전개는 유클리드 호제법을 사용하여 다음과 같이 구할 수 있다. 유리수 ${\displaystyle r/s}$가 주어졌을 때 (${\displaystyle r\in \mathbb {Z} }$, ${\displaystyle s\in \mathbb {Z} ^{+}}$), 유클리드 호제법에 따라

${\displaystyle {\begin{aligned}r_{0}&=r\\r_{1}&=s\\r_{0}&=a_{0}r_{1}+r_{2}&r_{2}&<r_{1}\\r_{1}&=a_{1}r_{2}+r_{3}&r_{3}&<r_{2}\\&\vdots \\r_{n-1}&=a_{n-1}r_{n}+r_{n+1}&r_{n+1}&<r_{n}\\r_{n}&=a_{n}r_{n+1}\end{aligned}}}$

인 ${\displaystyle r_{0},a_{0}\in \mathbb {Z} }$ 및 ${\displaystyle r_{1},\dots ,r_{n+1},a_{1},\dots ,a_{n}\in \mathbb {Z} ^{+}}$가 존재한다. 이 경우 ${\displaystyle a_{n}\geq 2}$이며,

${\displaystyle r/s=[a_{0};a_{1},\dots ,a_{n}]=[a_{0};a_{1},\dots ,a_{n-1},a_{n}-1,1]}$

이다.

무한 단순 연분수

모든 무한 단순 연분수는 항상 수렴하며, 극한은 항상 무리수이다. 반대로 모든 무리수는 무한 단순 연분수로 나타낼 수 있으며 그 방법은 유일하다. 무리수 ${\displaystyle x\in \mathbb {R} \setminus \mathbb {Q} }$의 연분수 전개

${\displaystyle x=[a_{0};a_{1},a_{2},\dots ]}$

는 다음과 같다.

${\displaystyle x_{0}=x}$

${\displaystyle a_{0}=\lfloor x\rfloor }$

${\displaystyle x_{n+1}=1/(x_{n}-a_{n})}$

${\displaystyle a_{n+1}=\lfloor x_{n+1}\rfloor }$

무리수 ${\displaystyle x\in \mathbb {R} \setminus \mathbb {Q} }$와 그 단순 연분수 전개

${\displaystyle x=[a_{0};a_{1},a_{2},\dots ]}$

와 근사분수들

${\displaystyle x^{(n)}=[a_{0};a_{1},\dots ,a_{n}]}$

이 주어졌을 때, 다음이 성립한다.

${\displaystyle x^{(0)}<x^{(2)}<x^{(4)}<\cdots <x<\cdots <x^{(5)}<x^{(3)}<x^{(1)}}$

즉, 짝수째 근사분수는 실제 값보다 작은 데 비하여, 홀수째 근사분수는 실제 값보다 크다. 또한 짝수째 근사분수는 증가 수열, 홀수째 근사분수는 감소 수열을 이룬다.

순환·순순환 단순 연분수

무리수 ${\displaystyle x\in \mathbb {R} \setminus \mathbb {Q} }$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle x}$의 단순 연분수 전개는 순환 단순 연분수이다.
• ${\displaystyle x}$는 (실수인) 2차 대수적 수이다. 즉, ${\displaystyle x}$는 어떤 정수 계수 2차 방정식의 근이며, 또한 이 2차 방정식의 판별식은 제곱수가 아닌 양의 정수이다. 즉, ${\displaystyle x=r+s{\sqrt {d}}}$인 제곱 인수가 없는 양의 정수 ${\displaystyle d\in \mathbb {Z} ^{+}}$ 및 ${\displaystyle r,s\in \mathbb {Q} }$가 존재하며, 또한 ${\displaystyle s\neq 0}$이다.

2차 대수적 수 ${\displaystyle r+s{\sqrt {d}}}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle r+s{\sqrt {d}}}$의 단순 연분수 전개는 순순환 단순 연분수이다.
• ${\displaystyle r+s{\sqrt {d}}>1}$이며 ${\displaystyle -1<r-s{\sqrt {d}}<0}$이다.

최적 유리 근사

 이 부분의 본문은 디오판토스 근사입니다.

${\displaystyle x\in \mathbb {R} }$가 실수, ${\displaystyle a\in \mathbb {Z} }$가 정수, ${\displaystyle b\in \mathbb {Z} ^{+}}$가 양의 정수라고 하자. 그렇다면, 다음이 성립한다.

• ${\displaystyle |bx-a|=\min _{a'\in \mathbb {Z} ,b'\in \mathbb {Z} ^{+}}^{b'\leq b}|b'x-a'|}$일 필요충분조건은 ${\displaystyle a/b}$가 ${\displaystyle x}$의 연분수 전개의 근사분수인 것이다.
• 만약 ${\displaystyle |x-a/b|=\min _{a'\in \mathbb {Z} ,b'\in \mathbb {Z} ^{+}}^{b'\leq b}|x-a'/b'|}$라면, ${\displaystyle a/b}$는 ${\displaystyle x}$의 연분수 전개의 반근사분수이다. 그러나 그 역은 성립하지 않는다.

${\displaystyle x\in \mathbb {R} }$가 실수이며, ${\displaystyle h_{n}/k_{n}}$가 ${\displaystyle x}$의 연분수 전개의 ${\displaystyle n}$번째 근사분수라고 하자. 그렇다면, 임의의 ${\displaystyle n=0,1,2,\dots }$에 대하여

${\displaystyle |k_{n}x-h_{n}|=\min _{a\in \mathbb {Z} ,b\in \mathbb {Z} ^{+}}^{b<k_{n+1}}|bx-a|}$

이다.

${\displaystyle x\in \mathbb {R} }$가 실수이며, ${\displaystyle h_{n}/k_{n}}$가 ${\displaystyle x}$의 연분수 전개의 ${\displaystyle n}$번째 근사분수라고 하자. 그렇다면, 임의의 ${\displaystyle n=0,1,2,\dots }$에 대하여 다음이 성립한다.

• ${\displaystyle 1/(k_{n}(k_{n}+k_{n+1}))\leq |x-h_{n}/k_{n}|\leq 1/k_{n}^{2}}$. (물론, ${\displaystyle x}$가 무리수인 경우 엄격한 부등식이 성립한다.)
• 다음 두 부등식 가운데 적어도 하나가 성립한다.
  • ${\displaystyle |x-h_{n}/k_{n}|<1/(2k_{n}^{2})}$
  • ${\displaystyle |x-h_{n+1}/k_{n+1}|<1/(2k_{n+1}^{2})}$
• (후르비츠 정리) 다음 세 부등식 가운데 적어도 하나가 성립한다.
  • ${\displaystyle |x-h_{n}/k_{n}|<1/({{\sqrt {5}}k_{n}^{2}})}$
  • ${\displaystyle |x-h_{n+1}/k_{n+1}|<1/({\sqrt {5}}k_{n+1}^{2})}$
  • ${\displaystyle |x-h_{n+2}/k_{n+2}|<1/({\sqrt {5}}k_{n+2}^{2})}$

반대로, 디오판토스 근사에 대한 르장드르 정리(영어: Legendre’s theorem)에 따르면 다음이 성립한다. 임의의 ${\displaystyle x\in \mathbb {R} }$ 및 정수 ${\displaystyle a\in \mathbb {Z} }$와 양의 정수 ${\displaystyle b\in \mathbb {Z} ^{+}}$의 서로소 정수쌍에 대하여, 만약

${\displaystyle |x-a/b|<1/2b^{2}}$

라면, ${\displaystyle a/b}$는 ${\displaystyle x}$의 연분수 전개의 근사분수이다.

펠 방정식

 이 부분의 본문은 펠 방정식입니다.

${\displaystyle n\in \mathbb {Z} ^{+}}$이 제곱수가 아닌 양의 정수이며, ${\displaystyle k}$가 ${\displaystyle {\sqrt {n}}}$의 연분수 전개의 주기이며, ${\displaystyle h_{i}/k_{i}}$가 ${\displaystyle {\sqrt {n}}}$의 연분수 전개의 ${\displaystyle i}$번째 근사분수라고 하자. 그렇다면, 펠 방정식

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

의 음이 아닌 정수해는 다음과 같다.

• 만약 ${\displaystyle k}$가 짝수라면,

  ${\displaystyle (x_{i},y_{i})=(h_{ik-1},k_{ik-1})\qquad (i=0,1,2,3,\dots )}$

• 만약 ${\displaystyle k}$가 홀수라면,

  ${\displaystyle (x_{i},y_{i})=(h_{ik-1},k_{ik-1})\qquad (i=0,2,4,6,\dots )}$

또한, 펠 방정식

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

의 음이 아닌 정수해는 다음과 같다.

• 만약 ${\displaystyle k}$가 짝수라면, 해가 존재하지 않는다.
• 만약 ${\displaystyle k}$가 홀수라면,

  ${\displaystyle (x_{i},y_{i})=(h_{ik-1},k_{ik-1})\qquad (i=1,3,5,7,\dots )}$

또한, (${\displaystyle k}$의 홀짝성과 관계 없이) 다음이 성립한다.

${\displaystyle h_{ik-1}+k_{ik-1}{\sqrt {d}}=(h_{k-1}+k_{k-1}{\sqrt {d}})^{i}\qquad (i=0,1,2,3,\dots )}$

예

예를 들어, 원주율 파이(${\displaystyle \pi }$)의 근사분수들을 계산해 보자.

${\displaystyle {\begin{aligned}a_{0}&=\lfloor \pi \rfloor =3&u_{1}&={\frac {1}{\pi -3}}\approx {\dfrac {113}{16}}=7.0625\\a_{1}&=\lfloor u_{1}\rfloor =7&u_{2}&={\frac {1}{u_{1}-7}}\approx {\dfrac {31993}{2000}}=15.9965\\a_{2}&=\lfloor u_{2}\rfloor =15&u_{3}&={\frac {1}{u_{2}-15}}\approx {\dfrac {1003}{1000}}=1.003\end{aligned}}}$

(${\displaystyle \lfloor x\rfloor }$는 ${\displaystyle x}$보다 작은 최대 정수)

이런 식으로 계속 나간다.

이를 반복하면, 무한 연분수

${\displaystyle {\begin{aligned}\pi &=[3;7,15,1,292,1,1,1,2,\cdots ]\\&=3+{\cfrac {1}{7+{\cfrac {1}{15+{\cfrac {1}{1+{\cfrac {1}{292+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{2+{\cfrac {1}{\ddots }}}}}}}}}}}}}}}}}}\end{aligned}}}$

를 얻는다.

${\displaystyle \pi }$의 세 번째 근사분수는 ${\displaystyle [3;7,15,1]={\frac {355}{113}}=3.14159292035\cdots }$이며,이는 실제 ${\displaystyle \pi }$ 값에 매우 가까운 값이다.