PROOF 78

Prove.

The repetend is shorter than the denominator

On the rational numbers ℚ.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

For a natural number q ≥ 2 and an integer p with 0 ≤ p < q, set r₀ = p, and for each k ≥ 0 determine dₖ₊₁ and rₖ₊₁ by 10rₖ = q·dₖ₊₁ + rₖ₊₁, 0 ≤ rₖ₊₁ < q. Call dₖ the k-th digit of p/q after the decimal point.

Proof.

(1)At each step such dₖ₊₁ and rₖ₊₁ exist and are unique.A1

(2)Therefore once rₖ is fixed, dₖ₊₁ and rₖ₊₁ are fixed to single values.(1), A1

(3)For every k, 0 ≤ rₖ ≤ q−1(1), A1

∎

Definition D2

When there are some i ≥ 0 and a natural number L such that dₖ₊ₗ = dₖ for every k > i, the least such L is called the length of the repetend.

Proof.

If the collection of such L is nonempty, it has a least element, so the length is fixed to a single value.A7

∎

Lemma L1

If i < j and rᵢ = rⱼ, then for L = j − i and every k ≥ i, rₖ = rₖ₊ₗ and dₖ₊₁ = dₖ₊₁₊ₗ.

Proof.

(1)For k = i, rᵢ = rᵢ₊ₗ is the hypothesis.assumption

(2)Suppose rₖ = rₖ₊ₗ.assumption

(3)10rₖ = 10rₖ₊ₗ, so the two steps divide the same number by q.(2)

(4)The quotient and remainder are unique, so dₖ₊₁ = dₖ₊₁₊ₗ and rₖ₊₁ = rₖ₊₁₊ₗ(3), D1, A1

(5)Therefore it holds for every k ≥ i.(1), (4), R

∎

Lemma L2

If rₖ ≠ 0 for every k, then there exist 0 ≤ i < j ≤ q−1 with rᵢ = rⱼ.

Proof.

(1)Suppose rₖ ≠ 0 for every k.assumption

(2)Since 0 ≤ rₖ ≤ q−1, each rₖ is one of the values from 1 to q−1.(1), D1

(3)There are q−1 such values.(2), A3

(4)Consider the first q remainders, counting from r₀.convention

(5)Putting q items into q−1 boxes puts two into the same box.(3), (4), A2

(6)Therefore there exist 0 ≤ i < j ≤ q−1 with rᵢ = rⱼ.(5)

∎

Theorem T1

If rₖ ≠ 0 for every k, the length of the repetend is at most q−1.

Proof.

(1)Pick 0 ≤ i < j ≤ q−1 with rᵢ = rⱼ.L2

(2)Setting L = j − i, for every k > i, dₖ₊ₗ = dₖ(1), L1

(3)L ≤ q−1(1), A4

(4)The length of the repetend is the least such L, hence at most q−1.(2), (3), D2

∎

Corollary C

For q ≥ 2, the length of the repetend of p/q is always less than q.

Proof.

(1)Suppose rₖ = 0 for some k.assumption

(2)10·0 = q·0 + 0, so all subsequent digits are 0 and all subsequent remainders are 0.(1), D1, A1

(3)In this case the length of the repetend is 1.(2), D2

(4)Since q ≥ 2, 1 ≤ q−1A6

(5)If the remainder is never 0, the length is at most q−1.T1

(6)In both cases the length is at most q−1.(3), (4), (5)

(7)Since q−1 < q, the length of the repetend is less than q.(6), A5

∎

Remark

Can A2 be removed from this proof?

This proof never actually computes a single remainder. Check what it uses instead.