Thursday, May 15, 2008

Proof of theorem 65 in lecture notes

I shall state the full glory of Theorem 65 here:

Suppose that d is a positive integer that is not a perfect square, and the continued fraction expansion of sqrt(d) has convergents p_n/q_n and is ultimately periodic with period m. Then the only positive solutions (x,y) are given by (x,y)=(p_n,q_n) where n = lm - 1 where l is some interger corresponding to n being odd.

Proof:

Consider the equation x^2 - d*y^2 = 1. This can be transformed to (x+sqrt(d)*y)*(x-sqrt(d)*y)=1 => (x-sqrt(d)*y)=1/[(x+sqrt(d)*y)=1] =>x>sqrt(d)*y.
Whence, this yields 0
Thus we deduce that |sqrt(d) - (x/y)|<1/2*y^2.

We claim that if $theta in R$ and x/y is a rational number with (x.y)=1 satisfying |$theta$ - (x/y)|<1/2*y^2. then x/y is necessary a convergent to the continued fraction expansion of $theta$.

consider the equations

u*p_n + v*p_(n+1) = x
u*q_n + v*q_(n+1) = y

This set of equations do have an integral solution for (u,v) since
p_n*q_(n+1) + q_n*p_(n+1) = (-1)^(n+1).

If u or v =0, we got (x/y) = (p_(n+1)/q_(n+1)) and the coprimailty of x and y yields that v = $+ or -$ 1. Then the claim holds.

So if u and v are both not equal to 0 and that q_n -> infinity as n-> infinity, so we can choose an n such that q_nBut since u*q_n + v*q_(n+1) = y, u and v are of opposite signs and thus

|y*$theta$-x|=|u(q_n*$theta$-p_n) + v(q_(n+1)*$theta$-p_(n+1)| > |(q_n*$theta$-p_n)|.

Since |$theta$ - (x/y)|<1/2*y^2, it follows that |(x/y)-(p_n/q_n)|
This proves our claim.

Now let p_n/q_n be the convergent to sqrt(d).
Then we got the following:

sqrt(d) = (p_n*$theta$_(n+1)+p_(n-1))/(q_n*$theta$_(n+1)+q_(n-1))

whence,
q_n*sqrt(d) = (-1)^n/(q_n*$theta$_(n+1)+q_(n-1))

This leaves that n must be odd in order to have that Pell's equation.
(Check if n is even then there will be a contradiction)

Continue the proof some other day...

No comments: