정수론(Number theory)

연분수(Continued fraction)

수를 정수⁠(integer)⁠ 부분 + 1/(나머지)로 계속 풀어 쓴 표현. 중간에서 끊으면 그 크기의 분모로 만들 수 있는 가장 좋은 유리 근사가 나온다.

x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}}

먼저 보면 좋은 개념최대공약수와 유클리드 호제법

유클리드 호제법⁠(Euclidean algorithm)⁠의 정사각형 채우기를 가로 $x$ , 세로 1인 직사각형에 해 봅시다. $x =$ 이고, 단계까지 보입니다. 각 단계에 들어가는 정사각형의 개수가 연분수의 계수입니다: .

같은 색 정사각형 묶음 하나가 계수 하나입니다. 유리수라면 언젠가 딱 떨어지고, 무리수라면 끝없이 이어집니다.

연분수를 $k$ 번째 계수 $a_k$ 에서 끊으면 분수 $p_k/q_k$ (수렴분수)가 나옵니다. 분모 크기에 비해 아주 정확해서, 오차가 $1/q_k^2$ 보다 작고, $k \ge 1$ 이면 분모가 $q_k$ 이하인 다른 어떤 분수보다도 가깝습니다. 더 정확히는 오차가 $1/(a_{k+1} q_k^2)$ 보다 작습니다. 그래서 다음 계수가 크면 바로 앞에서 끊은 분수가 특히 좋습니다. $\pi$ 의 계수 $[3; 7, 15, 1, 292, \dots]$ 에서 292 바로 앞에서 끊은 $355/113$ 은 소수점 아래 여섯 자리까지 맞습니다(오차 약 $2.7 \times 10^{-7}$ ).

막대 높이는 각 수렴분수가 맞히는 소수⁠(prime number)⁠ 자릿수, 곧 −log₁₀(오차)입니다.

이런 근사가 항상 존재한다는 것, 곧 어떤 무리수⁠(irrational number)⁠ $x$ 에 대해서도 $|x - p/q| \lt 1/q^2$ 인 분수 $p/q$ 가 무한히 많다는 것은 비둘기집 원리⁠(pigeonhole principle)⁠로도 보일 수 있습니다. 19세기에 디리클레가 이렇게 증명해 디리클레 근사 정리라 부릅니다. 0과 $x, 2x, \dots, Qx$ 의 소수 부분⁠(fractional part)⁠, 모두 $Q+1$ 개를 폭 $1/Q$ 인 칸 $Q$ 개에 넣으면 두 개가 한 칸에 들어간다는 것이 핵심입니다.

반대로 계수가 모두 1인 황금비⁠(golden ratio)⁠는 근사가 가장 느리게 좋아지는, "가장 무리수다운" 수입니다. 그 수렴분수의 분자와 분모는 피보나치 수입니다. 유리수⁠(rational number)⁠는 계수가 유한하고, 무리수는 무한합니다. 유한한 정수 목록은 셀 수 있으니 유리수가 가산이라는 사실도 여기서 한 번 더 보입니다.

이 개념이 나오는 큰 생각근사와 오차 선형화: 휘어진 것을 곧게 보기

이 개념이 나오는 긴 글

정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다. 집합론 무한에도 크기가 있다 자연수와 짝수는 어느 쪽이 많을까? 칸토어는 무한을 세는 법을 찾았고, 무한이 하나가 아님을 보였다.

이 개념 위에 세워진 것

무리수 황금비

이 개념을 언급하는 페이지

뉴턴 방법
… = 2 에 적용하면 1 → 3/2 → 17/12 → 577/408이 나오는데, 이 분수들은 √2의연분수근사 중 일부입니다. 같은 반복을 복소평면에서 z^3 = 1 에 돌려 봅시다. 근은 세 개의 ⟦1의 …
리사주 곡선
… 영원히 없어서 곡선은 결코 닫히지 않고, 사각형 안의 모든 점에 한없이 가까이 지나갑니다. 무리수라도연분수로 잘 근사되는 수(예: π ≈ 22/7)는 한동안 거의 닫힌 것처럼 보이다가 천천히 어긋납니다. 연분수가 …
가산 집합
… 입니다. 조밀함과 크기는 다른 이야기입니다. 이런 나열은 이 밖에도 많습니다. 모든 유리수는 유한한연분수로 쓸 수 있는데, 연분수 계수들의 유한한 목록도 가산 개뿐입니다. 반대로 실수는 가산이 아닙니다. 어떤 …
비둘기집 원리
… 작은 분수 p/q 를 무한히 많이 갖는다는 것이 나옵니다. 가장 좋은 근사 분수를 차례로 내놓는 방법이연분수입니다. 사람이 두 명 이상인 모임에는 모임 안에서 아는 사람 수가 같은 두 사람이 반드시 있습니다. …
최대공약수와 유클리드 호제법
… 수에도 쓸 수 있고, RSA의 열쇠 계산에 쓰입니다. 각 단계의 정사각형 개수를 적어 두면 a/b 의연분수가 됩니다. 마지막 단계를 빼면 매번 정사각형이 딱 하나씩만 들어가는 쌍이 이웃한 ⟦피보나치 …
무리수
… 따릅니다. 예를 들어 3/2에서 (3 + 4)/(3 + 2) = 7/5가 나옵니다. 이 분수들은 √2를연분수1 + \cfrac{1}{2 + \cfrac{1}{2 + \cdots}} (줄여서 [1; 2, 2, 2, …
피보나치 수열
… , 황금비로 모입니다. 이 비들이 곧 \varphi = [1; 1, 1, \dots] 의연분수수렴분수입니다. 그림의 정사각형 채우기를 거꾸로 하면 유클리드 호제법이 됩니다. 이웃한 피보나치 …
황금비
황금비 \varphi 의연분수는 계수가 전부 1입니다. 계수가 크면 수렴분수가 급히 좋아지는데, 전부 1이면 가장 느리게 좋아집니다. …
대수적 수와 초월수
… 처음으로 해냈습니다. 그는 먼저 대수적 수는 분수로 아주 잘 근사될 수 없다는 것을 보였습니다(분수 근사는연분수의 주제입니다). 정확히는 n 차 다항식의 근인 무리수 \alpha 마다 양수 c 가 있어서, 어떤 분수 …
욕심쟁이 알고리즘
… b진법으로 쓴 각 자리의 숫자입니다. 수에서 정수 부분을 최대한 떼어 내고 나머지를 뒤집기를 되풀이하는연분수전개도 욕심쟁이 과정입니다. 욕심쟁이가 언제 옳은지는 매트로이드라는 구조로 깔끔하게 설명됩니다. …
수 체계: 자연수에서 실수까지
… 사다리를 아래에서 본 말입니다. 이어지는 곳. 실수를 유리수로 다가가는 방법으로는 진법의 소수 전개와연분수가 있고, 황금비는 연분수의 항이 모두 1이어서 분수로 가장 다가가기 어려운 수입니다. 실수의 …
고정점
… 2, 3/2, 5/3, 8/5, …가 나오는데, 이것은 피보나치 수열의 이웃한 두 항의 비이자 φ의연분수근사입니다. |f'(x^*)| = 1 이면 이 어림으로는 판정이 안 됩니다. sin x의 고정점 0이 그런 …
기술 집합론
… 무한 부분열을 고를 수 있는 무리수들의 집합이라는, 해석적이지만 보렐이 아닌 구체적인 예를 들었습니다(연분수). 수슬린은 내전 중이던 1919년 발진티푸스로 스물넷에 세상을 떠났습니다. 해석적 집합도 여전히 순하게 …
정수론
… 다 설명되지 않은 무늬가 보입니다. 이어지는 곳. 나누어떨어짐의 길은 유클리드 호제법, 소인수분해,연분수로, 나머지의 길은 모듈러 연산, 중국인의 나머지 정리, 원시근, 오일러 피 함수, ⟦원 …

이 페이지가 가리키는 개념

비둘기집 원리 페터 구스타프 르죈 디리클레 황금비 피보나치 수열 무리수 가산 집합