Continued Fractions: Purely Periodic Continued Fractions

In a previous blog, I showed a solution to Pell's Equation using continued fractions and matrices. One might reasonably ask if there is a simpler solution. It turns out that if we use the concept of purely periodic continued fractions, we can solve Pell's Equation using continued fractions but without needing to use matrix theory.

For those not familiar with continued fractions, start here. For those who are not familiar with Pell's Equation, start here. For those not familiar with how Pell's Equation fits into Fermat's Last Theorem, see here.

Today's blog is based on Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.

In a previous blog, I showed that a continued fraction is periodic if and only if it represents the root of a quadratic equation (see here).

A purely periodic continued fraction is a continued fraction where the entire fraction a₀ through a_n repeats. Here are some examples:

(a) This continued fraction is periodic but not purely periodic.

√6 = [ 2, 2, 4 ] (see here)

(b) This continued fraction is purely periodic.

√112 + 10/ 6 = [ 3, 2, 3, 10 ]

Just as periodic continued fractions correspond to quadratic equations, it turns out that purely periodic continued fractions correspond to what we will call "reduced" quadratic equations.

Definition: A reduced quadratic equation is any quadratic equation where the first root is a positive irrational greater than 1, its second root is a negative irrational that is greater than -1 and less than 0, and the discriminant is a nonsquare integer.

The discriminant refers to D in the following equation (see here):

x = (-b ± √d)/2a =(-b ± √b² - 4ac)/2a

So the discriminant D is always equal to: b² - 4ac.

In other words, the first root is a positive improper fraction (a fraction whose numerator is larger than or equal to its denominator such as 11/4 or 3/3) and the second root is a negative proper fraction (a fraction whose numerator is less than its denominator such as 1/2 or 1/3).

In my next blog, I will show how purely periodic continued fractions can be used to solve Pell's Equation.

Lemma 1: Every purely periodic continued fraction is a representation of a reduced quadratic equation.

(1) Let α be the purely periodic continued fraction with period n:

α = [ a₁, a₂, ...., a_n, a₁, ... ]

(2) Let N be an even multiple of n such that we have:

α = [ a₁, a_2,, ..., a_N, α ]

(3) We can assume that a₁, a₂, ... are integers greater than 0. [See here]

(4) Let P/Q be the Nth approximation of this continued fraction such that:
P/Q = [ a₁, a₂, ..., a_N ]

(5) Let p/q be the (N-1)th approximation of this continued fraction such that:
p/q = [ a₁, a₂, ..., a_N-1 ]

(6) According to previous results:

(a) Pq - Qp = 1 (see Lemma 2 here)

(b) α = (Pα + p)/(Qα + q) (see Lemma 1 here)

(c) α lies in between P/Q and p/q. It is greater than one and less than the other. (see Corollary 5.2 here )

(7) Rearranging (6b) gives us:

Qα² + qα - Pα - p = 0.

(8) If we set H = P - q, we get:

Qα² - Hα - p = 0.

(9) Solving for α gives us two roots such that:
α = H ± √H² + 4Qp/(2Q)

(10) The discriminant D = H² + 4Qp (see definition above) which means:

D = H² + 4Pq - 4 = (P + q)² - 4.

This shows that D is not a square (see here for proof )

(11) Let r = √D

(12) If we set α as the first root and α as the second root, we see that:

α = (H + r)/2Q

α = (H - r)/2Q

(13) We also note that r is greater than H since r = H² + 4Qp and 4Qp ≥ 4 (see here)

(14) So we know that α is positive and that α is negative (since r,Q are ≥ 1; Q is greater than 1 by above)

(15) We know that α is an improper fraction since in order for it to repeat, it needs to be equal to the reciprocal of a proper fraction (that is, 1/[α - floor(α)] ) so that all we have left is to prove that α is a proper fraction.

(16) α * α = (H+r)(H-r)/[(2Q)(2Q)] = H² - r²/4Q² =
=( H² - [H² + 4Qp])/4Q² =
-4Qp/4Q² = -p/Q

(17) So α = (p/Q)/α

(18) Since P is greater than p (see Corollary 4.2, here), Q is greater than q (see Lemma 4 here), we have:

- α is less than (P/Q)/α and less than (p/q)/α

(19) But since α lies between P/Q and p/q (see #6c above), we know that one value is greater than α and one value is less than α.

(20) A value less over α is a proper fraction and we have shown that - α lies between 0 and a proper fraction. So, therefore, it must be a proper fraction.

(21) We have thus proven that α is a reduced number -- that is, it is the root a reduced equation (see definition above)

QED

Lemma 2: All irrational numbers that result from the continued fraction expansion of a reduced number are themselves solutions to a quadratic equation.

(1) Let α be a reduced number.

That is, it is an improper fraction solution to:
ax² + bx + c = 0

Where: a,b,c are relatively prime integers and α is a negative proper fraction.

(2) For the start of the expansion, we note that:

α' = 1/(α - g)

That is: g is the largest whole number less than α and α' is the first derivative from α. In this case, g corresponds to a₀ of the continued fraction.

(3) Let's also define a', b', c' such that:

a' = -ag² - bg - c

b' = -2ag - b

c' = -a

We see in each of these cases that a',b', and c' are integers.

(4) Let D = the discriminant = b² - 4ac

(5) Let r = √D so that:

α = (-b + r)/2a

α = (-b - r)/2a

(6) From #2 and #3, we have:

α' = 1/(α - g) = 1/[(r-b)/2a - g] = 1/[(r - b - 2ag)/2a] = 2a/(r - b - 2ag) = 2a/(r + b')

(7) We can continue working with 2a/(r + b') to get:

2a/(r + b') = [2a(r - b')]/(r² - b'²)

(8) r² - b'² = b² - 4ac - (-2ag - b)² =
= b² - 4ac - 4a²g² - 4abg - b² =
= 2a(-2c - 2ag² -2bg) =
= (2a)(2)(-c + -ag² - bg) = (2a)(2a')

(9) Combining #7 and #8 gives us:

α' = 2a/(r + b') = (r - b')/(2a')

(10) Further, we note that:
b'² - 4a'c' = (-2ag - b)² - 4(-ag² - bg - c)(-a) =
= 4a²g² + 4abg + b² -4a²g² - 4abg - 4ac = b² - 4ac

(11) So that r = √b² - 4ac = √b'² - 4a'c'

(12) Putting together #9 and #11, gives us:

α' = [-b' + √b'² - 4a'c']/(2a')

(13) And this is a solution to a quadratic equation (see here) which gives us:

a'α² + b'α' + c' = 0.

(14) We know that α' is a positive, improper fraction since:

α' = 1/(α - g) and α - g is less than 1.

(15) Further, we can use the same reasoning to establish that:

α' = 1/(α - g) is the second solution to the same equation since:

α = (-b-r)/2a

1/(α - g) = 1/[(-b-r-2ag)/2a] = 2a/(-b -r -2ag) = 2a/(-r + b') = 2a(-r -b')/(r² - b'²)

Combining the above with #8 gives:
α' = (-r -b')/2a'

(16) By the equation in #15, we can also see that:

α' is a negative proper fraction since g is an integer greater than 1.

QED

Lemma 3: If α is a reduced number, then its continued fraction representation is purely periodic.

(1) Let α be a reduced number. That is:

(a) α is a positive, improper fraction of an integral quadratic equation such that:
aα² + bα + c = 0.

(b) α is the second root for the above equation and is a negative, proper fraction.

(c) The discriminant: D = b² - 4ac and is not a square.

(2) α * α =

(b² - b² + 4ac)/4a² = c/a

(3) α + α =

= -2b/2a = -b/a

(4) From #2 and #3, we can assume that c,b are negative and a is positive.

We know that product is negative and we know that the addition is positive since α is greater than α

(5) For a continued fraction, we know that:

α = g + 1/α'

We know that g is the greatest integer less than α.

We also know that α' is itself a reduced number.

(6) From lemma 2, we also know that:

α' = 1/(α - g)

1/α' = α - g

-1/α' = g - α

(7) As shown in Lemma 2, each reduced number in the continued fraction representation corresponds to the same discriminant D (see Lemma 2 above)

(8) The number of different reduced numbers that correspond to a given discriminant D is finite since:

(a) -ac is greater than 0 since a is positive and c is negative.

(b) We know that b is negative so that b can only take value -1, -2, ... -r since b² - 4ac must equal D.

(c) Additionally since D is nonsquare, we know that ac ≥ 1 and we know that b² must then be divisible by 4.

(d) From (c), we know that -ac = (D - b²)/4 which in turn gives us a finite amount of numbers a,c since for each (D - b²)/4 value there are only so many integers than when multiplied are equal to this result: a can take value from 1 thru (D - b²)/4 and c can take a value from -1 thru -(D - b²)/4 value.

(9) From #8, we know that there are a finite number of derived values (α') that can come up so eventually the continued fraction will repeat.

(10) So, let's assume that we have a pattern that repeats:

U = (K, L, u)
u = (h,k,l,u)

In the above case, u is the irrational number that repeats. K,L,h,k,l are integers.

(11) We know that the solution u is associated with a second root u

(12) Now, according to #6, we know that for the same second root, there must be the same previous floor value. So, we can conclude that L=l and K=k.

(13) In other words, all previous values of the continued fraction must match.

(14) The only way that this can work is if we are dealing with a purely periodic continued fraction.

Since, #13 is not true of a repeating continued fraction that is not a purely periodic continued fraction:

Consider √6 above, sometimes the value preceding the 2 is a 2 and sometimes it is a 4. In other words, it violates the assumption in #13.

On the other hand, this is true of a purely periodic continued fraction.

Consider √112 + 10/ 6 above, all integers will always have the same value beforehand the same value. It does not violate the assumption in #13.

QED

Theorem 1: An irrational number results in a purely periodic continued fraction if and only if it is a reduced number.

(1) All purely periodic continued fractions represent reduced numbers (Lemma 1)
(2) All reduced numbers result in purely periodic continued fractions (Lemma 3)

QED