Maths Extra Credit Homework Assignment - Number Theory

EXTRA CREDIT HOMEWORK 1

(Due July 1, Tuesday)

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 2y20 + 1 is a complete square. Then, easy to see that (

√ 2y20 + 1,y0) is a solution. (You can think of (1,0),(−1,0)

as trivial solutions.)

(2.1) De�ne an operation �○�: (x1,y1)○(x2,y2) = (x1x2 + 2y1y2,x1y2 + x2y1). Ex- plain why this is a natural de�nition. (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,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,y)−1 ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

m copies

,

where (x,y)−1 = (x,−y). De�ne (x,y)0 = (1,0).

(2.2) Explain why (x,y)−1 = (x,−y) is a natural de�nition. (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′,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 ≥ 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 ≠ 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′) ○ (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.