Continued Fractions and Matrices: More Lemmas

Today's blog continues exploring properties of continued fractions and matrices which are used in the solution for Pell's Equation. This blog assumes that you have already read the previous blog.

The details of today's blog is based on Harold M. Stark's An Introduction to Number Theory.

Lemma 1: if δ(1,√d) = (1,√d)M_n^-1M_n+kj, then there exists r_k, s_k, t_k, u_k such that:

and

(dt_k - s_k) + (r_k - u_k)√d = 0.

(1) By assumption, we let:
δ(1,√d) = (1,√d)M_n^-1M_n+kj [See here for an example where this assumption is true]

(2) Further, since we know that M_n^-1 is a 2 x 2 matrix (see here), we know that the product with M_n+kj is a 2x2 matrix (see here) and we can assume that there exists r_k, s_k, t_k, u_k such that:


(3) Now, we know that:
δ(1,α) = (δ,δα) [See here for review of matrix math]

(4) From a previous result, we know that:
δ(1,α) = (1,α)M_n^-1M_n+j [See here]

(5) Combining #4 and #5 with #2 gives us:


(6) From #6 (see here for review of matrix math), we can conclude that:

(δ, δα) = (r_k+t_kα, s_k+u_kα)

(7) This means that:

δ = r_k + t_kα

δα = s_k + u_kα

(8) Combining these two equations gives:

(r_k + t_kα)α = s_k + u_kα

(9) Which means that:

r_kα + t_kα² = s_k + u_kα

(10) And subtracting the left-side value from both sides give us:

t_kα² + r_kα - u_kα - s_k = 0

which is:

t_kα² + α(r_k - u_k) - s_k = 0

(11) Since we know that α = √d (see here for review of α)

t_kα² + α(r_k - u_k) - s_k = t_kd +√d (r_k - u_k) - s_k

(12) So, this gives us finally:
(dt_k - s_k) + (r_k - u_k)√d= 0.

QED

Lemma 2: M_n = M_m → n = m.

(1) Assume that M_n = M_m but n ≠ m

(2) M_n =


(3) M_m =


(4) Since M_n = M_m, we have:

q_n-2 = q_m-2
q_n-1 = q_m-1

(5) Now q₁ is less than q₂ and so on (see here for proof). So, m-2, n-2, n-1, m-1 must all be less than 1. (Otherwise, they cannot be equal)

(6) q₀ and q_-2 = 1 while q_-1 = 0.

(7) So, m-2, n-2, n-1, m-1 cannot equal -1. [Since by #6 no other value = 0]

(8) On the other, it is possible for q_-2 = q₀ = q₁ since all could = 1. (See here and here)

(9) So n-2, m-2, n-1, m-1 must equal -2,0, or 1.

(10) So n must = 2 (so that n-1 = 1, n-2 = 0). [Note: n=0 doesn't work since n-1 = -1; n=1 doesn't work since n-2=-1; and n=3 doesn't work since n-1 = 2]

(11) But then m must also = 2 (so that m-1=1, m-2=0) but this goes against our assumption.

(12) So we have a contradiction. There is no way that M_n = M_m without n = m.

QED