Maths Extra Credit Homework Assignment - Number Theory

EXTRA CREDIT HOMEWORK 1

1. In this assignment, try to solve Pell's equation for n = 2: x2 − 2y2 = 1.

(1) First, nd a smallest non-trivial solution in the following way: start from

y = 1, nd the smallest positive integer y0 such that 2y2

0 + 1 is a complete square.

Then, easy to see that (

»

2y2

0 + 1; y0) is a solution. (You can think of (1; 0); (−1; 0)

as trivial solutions.)

(2.1) Dene an operation X: (x1; y1) X (x2; y2) = (x1x2 + 2y1y2; x1y2 + x2y1). Ex-

plain why this is a natural denition. (Hint: what is the product of x1 +

º

2y1 and

x2 +

º

2y2, under usual multiplication of real numbers?)

Hereafter, we denote (x; y)m = (x; y) X ::: X (x; y)

´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

m copies

for m > 0. When m < 0, and

(x; y) is an integer solution to the equation, we denote (x; y)m = (x; y)−1 X ::: X (x; y)−1

´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

m copies

,

where (x; y)−1 = (x;−y). Dene (x; y)0 = (1; 0).

(2.2) Explain why (x; y)−1 = (x;−y) is a natural denition. (Hint: If (x; y) is a

solution, what is 1

x+

º

2y

?)

(3)Show that if (x; y) is an integer solution to the equation, so are ±(x; y)m, for

any m, where −(a; b) is just the pair (−a;−b). (Hint: if (x +

º

2y)(x −

º

2y) = 1,

then (x +

º

2y)m(x −

º

2y)m = 1.) Similarly, if (x; y) and (x.; y.) are solutions, so

is (x; y) X (x.; y.).

Now, let (x0; y0) be the solution you found in part (1), show that all solutions are

of the form ±(x0; y0)m in the following way:

(4.1) Show that if there is a solution not of the given form, then there is a pair of

positive integers (x.; y.) which is a solution, such that (x0 +

º

2y0)M < x. +

º

2y. <

(x0 +

º

2y0)M+1, for some M C 0.

(4.2) Show that if (x; y) and (x.; y.) are both solutions, and x; x.; y; y. are all posi-

tive, then y x y.. In particular, either x > x.; y > y., or x < x.; y < y.

1

2 EXTRA CREDIT HOMEWORK 1

(4.3) Eventually, denote (x..; y..) = (x.; y.) X (x0; y0)−M. Show that x.. +

º

2y.. <

x0 +

º

2y0. Argue that this contradicts part (1).

5. Eventually, consider Pell's equation in general: x2 − ny2 = 1 (n is not a per-

fect square). Guess a general pattern for solutions of the equation.