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

Continued Fractions and Matrices Continued

Today's blog continues a previous blog on how 2x2 matrices can be used to represent continued fractions. The lemmas presented in today's blog are used in the solution to Pell's Equation. For those interested in the background to Pell's Equation, start here. For those who would like to proceed to its solution using continued fractions and matrices, go here. The solution to Pell's Equation is used as part of the proof for Fermat's Last Theorem, n=5.

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

For Lemma 1, α_n, q_n are defined here. For Lemma 2, M_n is defined here.

Lemma 1: α_nq_n-1 + q_n-2 ≠ 0

(1) Assume that α_nq_n-1 + q_n-2 = 0.

(2) Then, q_n-1 = 0 and q_n-2 = 0. [See here for proof]

(3) But q_n ≥ 1 for n ≥ 1. [See here]

(4) Futher, there are no successive 0's in a row since (see here for details on how these values are derived):
q_-2 = 1
q_-1=0
q₀=1

(5) Therefore #2 is impossible and we reject our assumption.

QED

Lemma 2: if γ_n = α_nq_n-1 + q_n-2, then γ_n(1,α) = (1,α_n)M_n

(1) From the definition of M_n (see here), we know that:


= (q_n-2+α_nq_n-1, p_n-2+α_np_n-1) [See here for review on matrix products]

(2) By applying the equation α = (p_n-2 + α_np_n-1)/(q_n-2 + α_nq_n-1) [See here], we get:

(q_n-2+α_nq_n-1 , p_n-2+α_np_n-1) = (q_n-2 + α_nq_n-1)(1,α)

(3) Adding back γ_n, this gives us:
(q_n-2 + α_nq_n-1)(1,α) = γ_n(1,α)

QED

Lemma 3: if δ = γ_n+j/γ_n, then δ(1,√d) = (1,√d)M_n^-1M_n+kj

(1) From Lemma 2, we know that;

γ_n(1 , α) = (1, α_n)M_n

and

γ_n+j(1, α) = (1, α_n+j)M_n+j

(2) By the definition of matrix inverses (see here), we know that:
(1,α_n)M_nM_n^-1 = (1,α_n)

(3) From #1, then we have:
[(1,α_n)M_n)] = γ_n(1,α)

(4) So, from #2, we have:
(1,α_n) = γ_n(1,α)M_n^-1

(5) Likewise since α_n = α_n+j (see here), we get:
(1,α_n+j)M_n+j = (1,α_n)M_n+j

(6) Applying #4, this gives us:
(1,α_n+j)M_n+j = γ_n(1,α)M_n^-1M_n+j

(7) Combining #1 with #6, gives us:
γ_n+j(1,α) = γ_n(1,α)M_n^-1M_n+j

(8) Now, δ = γ_n+j/γ_n [We can do this since γ_n ≠ 0 (see Lemma 1 above) ]

(9) δ(1,α) = [(γ_n+j)(1 , α)]/γ_n

(10) Applying #7 gives us;

δ(1,α) = [γ_n(1,α)M_n^-1M_n+j]/γ_n =
= (1,α)M_n^-1M_n+j

QED