Today's blog rests on a proof offered by Jody Esmonde and M. Ram Murty in Problems in Algebraic Number Theory.

To understand the details of today's proof, you will need to be familiar with Continued Fractions.

Lemma 1: if d = a

^{2}+ 1 and a ≥ 1, then the continued fraction expansion of √d is [a , 2a, ... ]

(1) a

_{0}= a since a is less than √a

^{2}+ 1 which is less than a + 1 since:

a =√a

^{2}

a + 1 = √a

^{2}+ 2a + 1

a

^{2}is less than a

^{2}+ 1 is less than a

^{2}+ 2a + 1.

(2) a

_{2}= 2a since 2a is less than 1/(√a

^{2}+ 1 - a) which is less than 2a + 1.

(a) 1/(√a

^{2}+ 1 - a) = (√a

^{2}+ 1 + a)/(a

^{2}+ 1 - a

^{2}) = √a

^{2}+ 1 + a.

(b) From (a), we see that 2a is less than a + √a

^{2}+ 1 since a

^{2}+ 1 is greater than a

^{2}.

(c) Since a

^{2}+ 1 is less than a

^{2}+ 2a + 1, we see that:

√a

^{2}+ 1 + a is less than a + (a + 1) = a + √a

^{2}+ 2a + 1

(d) Finally, we see that all other items from this point a

_{i}are = 2a.

1/(√a

^{2}+ 1 + a - 2a) = 1/(√a

^{2}+ 1 - a) =

= (√a

^{2}+ 1 + a)/(a

^{2}+ 1 - a

^{2}) = √a

^{2}+ 1 + a.

QED

Lemma 2: if p

_{k}/q

_{k}is a convergent for the continued fraction expansion of α, then gcd(p

_{k},q

_{k}) = 1.

(1) Let f be a factor that divides both p

_{k}and q

_{k}.

(2) We know that p

_{k}q

_{k-1}- p

_{k-1}q

_{k}= (-1)

^{k-1}(see Lemma 2 here)

(3) From (1), we know that f divides p

_{k}q

_{k-1}- p

_{k-1}q

_{k}which means that f divides (-1)

^{k-1}

(4) But the only way that f divides (-1)

^{k-1}is if f = 1 since all values are integers.

QED

Lemma 3:

If:

(a) α is an irrational number

(b) r,s are integers

(c) s is greater than 0

(d) absolute(sα - r) is less than absolute(q

_{k}α - p

_{k}) where p

_{k},q

_{k}are the convergents of the continued fraction expansion of α

Then:

s ≥ q

_{k+1}

Proof:

(1) Assume that 1 ≤ s which is less than q

_{k+1}

(2) Then, there exist x,y such that:

p

_{k}x + p

_{k+1}y = r

q

_{k}x + q

_{k+1}y = s

(3) Multiplying q

_{k}to the first equation and p

_{k}to the second gives us:

p

_{k}q

_{k}x + p

_{k+1}q

_{k}y = rq

_{k}

p

_{k}q

_{k}x + p

_{k}q

_{k+1}y = sp

_{k}

(4) Now, subtracting the second from the first gives us:

y(p

_{k+1}qk - p

_{k}qk+1) = rq

_{k}- sp

_{k}

(5) Multiplying q

_{k+1}to the first equation in #2 and p

_{k+1}to the second equation and then subtracting gives us:

x(p

_{k}q

_{k+1}- p

_{k+1}q

_{k}) = rq

_{k+1}- sp

_{k+1}

(6) Applying a previous result (see Lemma 2 here), we get:

x = (-1)

^{k}(sp

_{k+1}- rq

_{k+1})

y = (-1)

^{k}(rq

_{k}- sp

_{k})

(7) We know that x ≠ 0

(a) Assume x = 0

(b) r/s = pk

_{k+1}/q

_{k+1}from #2.

(c) We know that gcd(p

_{k+1},q

_{k+1})=1 from Lemma 2 above.

(d) So from (b), r(q

_{k+1}) = s(p

_{k+1}) and from (c), we know that:

q

_{k+1}must divide s.

(e) But since s is greater than 0, this means that q

_{k+1}≤ s which contradicts our assumption at #1 so we can reject (7a).

(8) We know that y ≠ 0

(a) Assume that y = 0

(b) Then r = p

_{k}x

(c) Then s = q

_{k}x

(d) So that absolute(sα - r) = absolute(x) * absolute(q

_{k}α - p

_{k})

(e) Because x ≠ 0, we then have absolute(x) * absolute(q

_{k}α-p

_{k}) ≥ absolute(q

_{k}α - p

_{k})

(f) But combining (d) with (e) gives us:

absolute(sα - r) ≥ absolute(q

_{k}α - p

_{k}) which contradicts our original assumption (d) in the lemma statement.

(g) Therefore, we reject (8a).

(9) x,y have opposite signs (one is positive and one is negative)

(a) Assume y is negative then q

_{k}x = s - q

_{k+1}y. Since q

_{i}≥ 0 (see Corollary 4.1 here) and since s ≥ 1, x is positive.

(b) Assume that y is positive, then q

_{k+1}y ≥ q

_{k+1}which is greater than s (by assumption #1) so q

_{k}x = s - q

_{k+1}y is less than 0.

(10) We know that α lies in between consecutive convergents since:

(a) By a previous result (see Corollary 5.2 here), we know that if k is even:

p

_{k}/q

_{k}is less than α which is less (p

_{k+1})/q

_{k+1}

Which means that p

_{k}is less than αq

_{k}and that αq

_{k+1}is less than p

_{k+1}.

This then gives us that:

q

_{k}α - p

_{k}is positive and q

_{k+1}α - p

_{k+1}is negative.

(b) We also know that if k is odd,

(p

_{k+1})/q

_{k+1}is less than α which is less than p

_{k}/q

_{k}

Which means that p

_{k+1}is less than αq

_{k+1}and q

_{k+1}α is less than p

_{k}.

This then gives us that:

q

_{k+1}α - p

_{k+1}is positive and q

_{k}α - p

_{k}is negative.

(11) By 10(a) and 10(b), we know that regardless of whether k is odd or even, q

_{k}α - p

_{k}and q

_{k+1}α - p

_{k+1}have opposite signs.

(12) This means that x(q

_{k}α - p

_{k}) and y(q

_{k+1}α - p

_{k+1}) have the same sign.

(13) Finally, this gives us that:

absolute(sα - r) =

= absolute( [q

_{k}x + q

_{k+1}y]α - [p

_{k}x + p

_{k+1}y]) =

= absolute( x[q

_{k}α - p

_{k}] + y[q

_{k+1}α - p

_{k+1}] )

(14) This then gives us:

absolute(sα - r) ≥ absolute(x)*absolute(q

_{k}α - p

_{k}) + absolute(y)*absolute(q

_{k+1}α - p

_{k+1}) ==>

absolute(sα - r) ≥ absolute(x)*absolute(q

_{k}α - p

_{k}) ==>

absolute(sα - r) ≥ absolute(q

_{k}α - p

_{k})

(15) But this contradicts #1 so we are done.

QED

Lemma 4: 1 ≤ s is less than q

_{k+1}, then absolute(q

_{k}α - p

_{k}) ≤ absolute(sα - r).

(1) Assume that absolute(sα - r) is less than absolute(q

_{k}α - p

_{k})

(2) Then s ≥ q

_{k+1}

(3) But s is less than q

_{k+1}

(4) So we have a contradiction and we reject our assumption.

QED

Lemma 5: if absolute(α - r/s) is less than 1/(2s

^{2}) and s is greater than 0, then r/s is a convergent of the continued fraction of α

(1) Assume that r/s is not a convergent of α

(2) Then, r/s ≠ p

_{n}/q

_{n}for all n.

(3) Since q

_{0}= 1 and q

_{k}≥ k (see Corollary 4.1 here), we may define a value k such that:

q

_{k}≤ s which is less than q

_{k+1}

(4) So we also have q

_{k}≤ s is less than q

_{k+1}

(5) absolute(α - r/s) is less than 1/(2s

^{2}) implies that:

absolute(sα - r) is less than 1/2s.

(6) From a result in Lemma 4 above, absolute(q

_{k}α - p

_{k}) ≤ absolute(sα - r).

Which then gives us:

absolute(q

_{k}α - p

_{k}) is less than 1/2s.

(7) Dividing all sides by q

_{k}gives:

absolute(α - p

_{k}/q

_{k}) is less than 1/(2sq

_{k})

(8) Since r/s ≠ p

_{k}/q

_{k}, absolute(sp

_{k}- rq

_{k}) ≥ 1.

(9) This means that:

1/(sq

_{k}) ≤ absolute(sp

_{k}- rq

_{k})/sq

_{k}=

= absolute(p

_{k}/q

_{k}- r/s) =

= absolute(p

_{k}/q

_{k}- r/s + α - α )

which is:

≤ absolute(α - p

_{k}/q

_{k}) + absolute(α - r/s)

which is less than:

1/(2sq

_{k}) + 1/2s

^{2}

(10) Putting it all together gives us:

1/sq

_{k}is less than 1/(2sq

_{k}) + 1/(2s

^{2})

(11) Subtracting 1/2q

_{k}from both sides gives us:

1/(2sq

_{k}) is less than 1/(2s

^{2}).

(12) But this means that:

q

_{k}is greater than s.

(13) This is a contradiction so we reject our assumption #1.

QED

Lemma 6: if x

^{2}- dy

^{2}is positive and is less than √d, then x,y is a convergent to the continued fraction expansion of √d.

(1) By our assumption above:

x

^{2}- dy

^{2}= (x + y√d)(x - y√d) is greater than 0.

(2) This means that x > y√d (otherwise, the value in #1 would be negative since x,y are positive numbers)

(3) So x/y is greater than √d

(4) So absolute(x/y - √d) = (x - y√d)/y =

= (x

^{2}- dy

^{2})/[y(x + y√d)]

(5) This is less than:

(x

^{2}- dy

^{2})/[y(2y√d)] since x is greater than y√d and y(x + y√d) is greater than y(y√d + y√d) = y(2y√d)

(6) And (x

^{2}- dy

^{2})/y(2y√d) is less than √d/y(2y√d) [By the assumption of this lemma]

(7) Dividing both sides by √d gives us:

x/y - √d is less than 1/(2y

^{2})

(8) Which by Lemma 5 above gives us our conclusion.

QED

Lemma 7: if x

^{2}- dy

^{2}is a negative number greater than -√d, then x,y are convergents in the continued fraction expansion of √d.

(1) y

^{2}- (1/d)x

^{2}is a positive number less than 1/√d since:

(a) √d is greater than dy

^{2}- x

^{2}(By multiplying by -1 to the assumption)

(b) √d/d is greater than y

^{2}- (x

^{2})/d which is greater than 0.

(c) 1/√d is greater than y

^{2}-(x

^{2})/d which is greater than 0.

(2) y is greater than x/√d since:

(a) (y - x/√d)(y + x/√d) is greater than 0.

(b) if y were less than this same value would be negative.

(c) if y = x/√d then (2a) would = 0 which it does not.

(3) From #2, y/x is greater than 1/√d.

(4) y/x - 1/√d = (y -x/√d)/x =

= [y

^{2}- x

^{2}/d]/[x(y + x/√d)]

which is less than:

[y

^{2}- x

^{2}/d]/(2x

^{2}/√d) since:

(a) y is greater than x/√d (from #2 above) so xy is greater than x

^{2}/√d.

(b) And xy + x

^{2}/√d is greater than 2x

^{2}/√d.

(5) Now:

y

^{2}- (x

^{2}/d) is less than 1/√d (from #1) so:

(y

^{2}- x

^{2}/√d)/(2x

^{2}/√d) is less than: (1/√d)/(2x

^{2}/√d)

(6) Since:

(1/√d)/(2x

^{2}/√d) = 1/2x

^{2}, we have the following:

y/x - 1/√d is less than 1/2x

^{2}.

(7) By the lemma above, y/x is a convergent.

Lemma 8: if d = a

^{2}+ 1 and absolute(u

^{2}- dv

^{2}) ≠ 0,1, then absolute(u

^{2}- dv

^{2}) is greater than √d

(1) The continued fraction for √a

^{2}+ 1 is [ a, 2a ... ] (see Lemma 1 above)

(2) This means that the period = 1 starting at 1.

(3) From a previous result, this means that for all convergents:

p

_{k}

^{2}- dq

^{2}= (-1)

^{k}

(4) Now if absolute(u

^{2}- dv

^{2}) is less than √d, then u,v are convergents since:

(a) If u

^{2}- dv

^{2}is less than √d, then from Lemma 6 above, u,v are convergents.

(b) If -(u

^{2}- dv

^{2}) is less than √d, then from Lemma 7 above, u,v are convergents.

(5) From #4, since we are assuming that absolute(u

^{2}- dv

^{2}) ≠ 1 or 0, then we can conclude that:

absolute(u

^{2}- dv

^{2}) is greater than √d.

QED

Lemma 9: 2 is a prime in Z[(1 + √5)/2]

(1) Norm(2) = [(4 + 0)/2]*[(4 + 0)/2] = 16/4 = 4

(2) Let's assume that 2 is not a prime.

(3) Then there exists two values a,b that are not units Norm(a) * Norm(b) = Norm(2) = ±4.

(4) Since a,b are not units, we can assume that there norm(a), norm(b) ≠ ± 1.

(5) This limits us to consider Norm(a) = ± 2 and Norm(b) = ± 2.

(6) If Norm(a) = ± 2, then

Norm(a) = [(a + b√5)/2][(a - b√5)/2] = (a

^{2}- 5b

^{2})/4

(7) This means that:

(a

^{2}- 5b

^{2})/4 = ± 2 which implies that a

^{2}- 5b

^{2}= ± 8.

(8) We know from properties of Z[(a + b√5)/2] that a,b have the same parity (see here)

(9) First, we note that they cannot be both even.

(a) Assume that u,v are both even

(b) Then there exists u,v such that:

a = 2u

b = 2v

(c) (2u)

^{2}- 5(2v)

^{2}= ± 8

So:

4u

^{2}-20v

^{2}= 4(u

^{2}- 5v

^{2}) = ± 8

And:

u

^{2}- 5v

^{2}= ± 2.

(d) But absolute(u

^{2}- 5v

^{2}) ≠ ± 2 from Lemma 8 above since 5 = 2

^{2}+ 1.

(e) So we reject our assumption and conclude that a,b are both odd.

(10) But they cannot both be odd since:

(a) Assume they are both odd.

(b) Then, there exist u,v such that:

a = 2u + 1

b = 2v + 1

(c) (2u+1)

^{2}- 5(2v+1)

^{2}= 4u

^{2}+ 4u + 1 - 5(4v

^{2}+ 4v + 1) =

= 4u

^{2}+ 4u + 1 - 20v

^{2}-20v - 5 =

= 4u

^{2}- 4u - 4 - 20v

^{2}- 20v =

= 4(u

^{2}+ u - 1 - 5v

^{2}- 5v) = ± 8

(d) So we can conclude that:

u

^{2}+ u - 1 -5v

^{2}- 5v = ± 2

And:

u(u+1) - 5v(v+1) - 1 = ± 2

(e) But we know that u(u+1) is even and 5v(v+1) is even.

We know they are even since either x or x+1 is even and even * odd = even.

(f) But this means that #10d is impossible since

even - even - odd = odd

(g) So we have again found a contradiction.

(11) But it is impossible that a,b are neither odd nor even so we again have an impossibility and we reject our assumption.

QED

## 8 comments:

In step (10a) of

Lemmathere is an incorrect link.Rob

In step (10) of

Lemma 5:Should

1/sqk is less than 1/(2qk)+1/(2s^2)

be

1/sqk is less than 1/(2

sqk)+1/(2s^2)And in step (11) of

Lemma 5:Should

Subtracting 1/2qk from both sides gives us:

1/(sqk) is less than 1/(2s^2).

be

Subtracting 1/2

sqk from both sides gives us:1/(

2sqk) is less than 1/(2s^2).In step (3) of

Lemma 8:Should

pk^2+dq^2=(-1)^k

be

pk^2-dqk^2=(-1)^k

Rob

Hi Scouse Rob,

Thanks very much for the corrections! I've fixed all the typos that you mentioned on this page. :-)

Cheers,

-Larry

Larry

Please help, I am stuck.

In step (3) of

Lemma 8:From a previous result, this means that for all convergents:pk^2-dqk^2=(-1)^k

I cannot find the previous result that shows this fact.

Rob

Hi Scouse Rob,

This looks like a bad link. I'm also having trouble finding the previous result.

I'll add the correct result over the next few days.

It comes from page 265-266 (Ex. 8.2.8) of Jody Esmonde and M. Ram Murty's Problems in Algebraic Theory.

-Larry

I found the Esmonde proof, thanks.

In

Lemma 9step (9a):Assume thatu,vare both evenshould be

Assume thata,bare both evenRob

In

Lemma 9step (9a)Assume thatu,vare both evenshould be:

Assume thata,bare both evenRob

Post a Comment