PROOF 78
증명하라.
순환마디의 길이는 분모보다 작다
유리수 ℚ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
q ≥ 2 인 자연수 q 와 0 ≤ p < q 인 정수 p 에 대하여, r₀ = p 로 두고 각 k ≥ 0 에서 10rₖ = q·dₖ₊₁ + rₖ₊₁, 0 ≤ rₖ₊₁ < q 로 dₖ₊₁ 과 rₖ₊₁ 을 정한다. dₖ 를 p/q 의 소수점 아래 k 번째 자리라 한다.
증명.
(1)각 단계에서 그러한 dₖ₊₁ 과 rₖ₊₁ 은 존재하고 하나뿐이다.A1
(2)그러므로 rₖ 이 정해지면 dₖ₊₁ 과 rₖ₊₁ 이 하나로 정해진다.(1), A1
(3)모든 k 에 대하여 0 ≤ rₖ ≤ q−1(1), A1
∎
정의 D2
어떤 i ≥ 0 과 자연수 L 이 있어 모든 k > i 에서 dₖ₊ₗ = dₖ 일 때, 그러한 L 가운데 가장 작은 것을 순환마디의 길이라 한다.
증명.
그러한 L 들의 모임이 비어 있지 않으면 최소원이 있으므로 길이는 하나로 정해진다.A7
∎
보조정리 L1
i < j 이고 rᵢ = rⱼ 이면, L = j − i 에 대하여 모든 k ≥ i 에서 rₖ = rₖ₊ₗ 이고 dₖ₊₁ = dₖ₊₁₊ₗ 이다.
증명.
(1)k = i 일 때 rᵢ = rᵢ₊ₗ 는 가정이다.가정
(2)rₖ = rₖ₊ₗ 이라 하자.가정
(3)10rₖ = 10rₖ₊ₗ 이므로 두 단계는 같은 수를 q 로 나눈다.(2)
(4)몫과 나머지가 하나뿐이므로 dₖ₊₁ = dₖ₊₁₊ₗ 이고 rₖ₊₁ = rₖ₊₁₊ₗ(3), D1, A1
(5)그러므로 모든 k ≥ i 에서 성립한다.(1), (4), R
∎
보조정리 L2
모든 k 에서 rₖ ≠ 0 이면, rᵢ = rⱼ 인 0 ≤ i < j ≤ q−1 이 있다.
증명.
(1)모든 k 에서 rₖ ≠ 0 이라 하자.가정
(2)0 ≤ rₖ ≤ q−1 이므로 rₖ 은 1 부터 q−1 까지의 값 가운데 하나다.(1), D1
(3)그 값은 q−1 개다.(2), A3
(4)r₀ 부터 세어 처음 q 개의 나머지를 본다.약속
(5)q 개를 q−1 개의 칸에 넣으면 같은 칸에 둘이 들어간다.(3), (4), A2
(6)그러므로 rᵢ = rⱼ 인 0 ≤ i < j ≤ q−1 이 있다.(5)
∎
정리 T1
모든 k 에서 rₖ ≠ 0 이면 순환마디의 길이는 q−1 이하다.
증명.
(1)rᵢ = rⱼ 인 0 ≤ i < j ≤ q−1 을 잡는다.L2
(2)L = j − i 라 하면 모든 k > i 에서 dₖ₊ₗ = dₖ(1), L1
(3)L ≤ q−1(1), A4
(4)순환마디의 길이는 그러한 L 가운데 가장 작은 것이므로 q−1 이하다.(2), (3), D2
∎
따름정리 C
q ≥ 2 일 때 p/q 의 순환마디의 길이는 언제나 q 보다 작다.
증명.
(1)어떤 k 에서 rₖ = 0 이라 하자.가정
(2)10·0 = q·0 + 0 이므로 그 뒤의 자리는 모두 0 이고 나머지도 모두 0 이다.(1), D1, A1
(3)이때 순환마디의 길이는 1 이다.(2), D2
(4)q ≥ 2 이므로 1 ≤ q−1A6
(5)나머지가 한 번도 0 이 아니면 길이는 q−1 이하다.T1
(6)두 경우 모두 길이는 q−1 이하다.(3), (4), (5)
(7)q−1 < q 이므로 순환마디의 길이는 q 보다 작다.(6), A5
∎
비고
A2 는 이 증명에서 제거할 수 있는가.
이 증명은 나머지를 한 번도 실제로 계산하지 않는다. 그 대신 무엇을 쓰는지 확인하라.