Discriminants and Reduced Equations

In today's blog, I will go over some lemmas that are needed to complete the solution to Pell's Equation using purely periodic continued fractions.

The lemmas in today's proof is taken from Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.

Lemma 1: Let D = 4n and let g = floor(√n). The coefficients for a reduced quadratic equation are: a = 1, b = -2g, c = g² - n.

(1) The discriminant D = b² - 4ac (see here for review)

(2) We know that r + b is less than 2a which is less than r - b since:

(a) 2√n - 2g is less than 2 [since we defined g as the floor of √n, we know that this value - g is less than 1.

(b) We also know that 2 is less than 2√n + 2g since √n + g is greater than 1.

(c) Since r = 2√n and since we are assuming that b = -2g, r + b = 2√n - 2g and likewise r - b = 2√n + 2g

(3) This proves tht we have a reduced fraction since:

-(r + b)/2a is a negative proper fraction
r - b/2a is a positive improper fraction.

QED

Lemma 2: Let D = 4n + 1. Let g be the largest integer for which g² + g will be smaller than n [so that, (g + 1)² + (g+1) is greater than n]. In this case, setting a = 1, b = -(2g + 1), c = g² + g - n gives us a reduced quadratic equation.

(1) First, we note that √D - (2g + 1) is less than 2.

(a) From our assumption about g² + g, we know that (g + 1)² + (g+1) is greater than n and that:

(g+1)² + g + 1 = g² + 2g + 1 + g + 1 = g² + 3g + 2

(b) Multiplying the above by 4 and adding 1 to each side gives us:

4g² + 12g + 9 is greater than 4n + 1.

(c) So that we have:
(2g + 3)² is greater than D.

(d) From this, it follows that 2g + 3 is greater than √D

(e) Rearranging this gives us:
√D - (2g + 1) is less than 2.

(2) 2 is less than √D + 2g + 1 since:

D ≥ 1 and g≥ 1.

(3) We then have r + b is less than 2a since:

r = √D and b = -(2g + 1)

(4) We also have 2a is less than r - b.

(5) So using the same reasoning in Lemma 1 we are done.

QED