(PDF) 4400 Pell Notes - DOKUMEN.TIPS (2024)

7/30/2019 4400 Pell Notes

1/10

THE PELL EQUATION

1. Introduction

Let d be a nonzero integer. We wish to find all integersolutions (x, y) to

(1) x2 dy2 = 1.1.1. History.

Leonhard Euler called (1) Pells Equation after the Englishmathematician JohnPell (1611-1685). This terminology has persistedto the present day, despite thefact that it is well known to bemistaken: Pells only contribution to the subjectwas the publicationof some partial results of Wallis and Brouncker. In fact thecorrectnames are the usual ones: the problem of solving the equation wasfirstconsidered by Fermat, and a complete solution was given byLagrange.

By any name, the equation is an important one for severalreasons only someof which will be touched upon here and itssolution furnishes an ideal introduc-tion to a whole branch ofnumber theory, Diophantine Approximation.

1.2. First remarks on Pells equation.

We call a solution (x, y) to (1) trivial if xy = 0. We alwayshave at least two

trivial solutions: (x, y) = (1, 0), which we shall call trivial.As for any planeconic curve, as soon as there is one solution thereare infinitely many rational solu-tions (x, y) Q2, and all arise asfollows: draw all lines through a single point, say(1, 0), withrational slope r, and calculate the second intersection point (xr,yr)of this line with the quadratic equation (1).

The above procedure generates all rational solutions and thuscontains all in-teger solutions, but figuring out which of therational solutions are integral is notstraightforward. This is acase where the question of integral solutions isessentiallydifferent, and more interesting, than the question ofrational solutions. Henceforthwhen we speak of solutions (x, y) to(1) we shall mean integral solutions.

Let us quickly dispose of some uninteresting cases.

Proposition 1. If the Pell equation x2

dy2

= 1 has nontrivial solutions, then dis a positive integer whichis not a perfect square.

Proof. (d = 1): The equation x2+y2 = 1 has four trivialsolutions: (1, 0), (0, 1). (d < 1): Then x = 0 = x2 dy2 2, so(1) has only the solutions (1, 0). (d = N2): Then x2 dy2 = (x +Ny)(x N y) = 1, and this necessitates either:

x + N y = x N y = 1in which case x = 1, y = 0; or

x + N y = x Ny = 1,1

7/30/2019 4400 Pell Notes

2/10

2 THE PELL EQUATION

in which case x = 1, y = 0: there are only trivial solutions.From now on we assume that d is a positive integer which is not asquare.

Any nontrivial solution must have xy = 0. Such solutions come inquadruples:if (x, y) is any one solution, so is (x, y), (x, y) and(x, y). Let us thereforeagree to restrict our attention to positivesolutions: x, y Z+.

2. Example: The equation x2 2y2 = 1Let us take d = 2. Theequation x2 2y2 = 1 can be rewritten as

y2 =x2 1

2.

In other words, we are looking for positive integers x for whichx21

2is an integer

square. First of all x2

1 must be even, so x must be odd. Trying x = 1 gives, of

course, the trivial solution (1, 0). Trying x = 3 we get

32 12

= 4 = 22,

so (3, 2) is a nontrivial solution. Trying successively x = 5,7, 9 and so forth we find

that it is rare for x21

2to be a square: the first few values are 12, 24, 40, 60, 69,112

and then finally with x = 17 we are in luck:

172 12

= 144 = 122,

so (17, 12) is another positive solution. Searching for furthersolutions is a task moresuitable for a computer. My laptop has notrouble finding some more solutions:the next few are (99, 70),(577, 408), and (3363, 2378). Further study suggests that

(i) the equation x2

2y2

has infinitely many integral solutions, and (ii) the size ofthesolutions is growing rapidly, perhaps even exponentially.

2.1. Return of abstract algebra. If weve been paying attention,there are someclues here that we should be considering things froman algebraic perspective.Namely, (i) we see that factorization ofthe left-hand side of the equation x2 dy2 =1 leads only to trivialsolutions; and (ii) when d < 0, we reduce to a problem thatwehave already solved: namely, finding all the units in the quadraticring

Z[

d] = {a + b

d | a, b Z}.We brought up the problem of determining the unitsin real quadratic rings Z[

d],

but we did not solve it. We are coming to grips with this sameproblem here.

Namely, let = r + sd Q(d). We put = r s

d,

and refer to as the conjugate of . We may view conjugation asgiving ahom*omorphism of fields from Q(

d) to itself, that is an automorphism ofQ(

d).

A consequence of this is that if P(t) is any polynomial withrational coefficients

and Q(d), then P() = P().We also define a norm map

N : Q(

d) Q, N() = ;

7/30/2019 4400 Pell Notes

3/10

THE PELL EQUATION 3

more explicitly, N(r + s

d) = (r +s

d)(rsd) = r2 ds2. From this descriptionit is immediate that thenorm maps elements of Z[

d] to integers.

Lemma 2. The norm map is multiplicative: for any , Q(d), wehaveN() = N()N().

Proof. This is a straightforward, familiar computation.Alternately, we get a moreconceptual proof by using thehom*omorphism property of conjugation (which isitself verified by asimple computation!):

N() = () = = ()() = N()N().

Thus Z-solutions (x, y) to (1) correspond to norm one elements x+ y

d Z[d]:N(x + y

d) = x2 dy2 = 1.

Moreover, every norm one element Z[d] is a unit: the equation =1 showsthat the inverse of is the integral element .

2.2. The solution for d = 2.

Recall that the units of any ring form a group undermultiplication. In our contextthis means that if (x1, y1) and (x2,y2) are two solutions to x

2 dy2 = 1, then wecan get another solution by multiplication inZ[

d]:

N((x1+y1

d)(x2+y2

d)) = N(x1+y1

d)N(x2+y2

d) = (x21dy21 )(x22dy22 ) = 11 = 1;multiplying out (x1 +y1

d)(x2 +y2

d) and collecting rational and irrational parts,

we get a new solution (x1x2 + dy1y2, x1y2 + x2y1).

Let us try out this formula in the case d = 2 for (x1, y1) =(x2, y2) = (3, 2).Our new solution is (3 3 + 2 2 2, 2 3 + 3 2) =(17, 12), nothing else than the sec-ond smallest positive solution!If we now apply the formula with (x1, y1) = (17, 12)and (x2, y2) =(3, 2), we get the next smallest solution (99, 70).

Indeed, for any positive integer n, we may write the nth power(3 + 2

2)n as

xn + yn

d and know that (xn, yn) is a solution to the Pell equation. Onecansee from the formula for the product that it is a positivesolution. Moreover, thesolutions are all different because the realnumbers (3 + 2

2)n are all distinct: the

only complex numbers z for which zn = zm for some m < n arethe roots of unity,and the only real roots of unity are 1. Indeed,we get the trivial solution (1, 0)by taking the 0th power of 3 +2

2. Moreover, (3 + 2

2)1 = 3

2

2 is a half-

positive solution, and taking negative integral powers of 3 + 22we get infinitelymany more such solutions.

In total, every solution to x2 dy2 = 1 that we have found is ofthe form (xn, yn)where xn + yn

d = (3 + 2

2)n for some n Z.

Let us try to prove that these are all the integral solutions.It is enough to showthat every positive solution is of the form(xn, yn) for some positive integer n, since

every norm one element x + y

d is obtained from an element with x, y Z+ bymultiplying by 1and/or taking the reciprocal.

7/30/2019 4400 Pell Notes

4/10

4 THE PELL EQUATION

Lemma 3. Let (x, y) be a nontrivial integral solution to x2 dy2= 1.a) x and y are both positive x + yd > 1.b) x > 0 and y< 0 0 < x + yd < 1.c) x < 0 and y > 0 1 < x + yd< 0.d) x and y are both negative x + yd < 1.Proof.Exercise.

We now observe that 3 + 2

2 is the smallest positive integral solution. Note thatfor anypositive integers x, y, x + y

d 1 + d. In fact, as x and y range over all

positive integers, we may view x + y

d as a double sequence of real numbers, andthis double sequencetends to in the sense that for any real number M thereare onlyfinitely many terms x + y

d M: indeed, since the inequality implies

x, y M there are at most M2 solutions. In the present case, onechecks thatamong the elements x + y

d < 3 + 2

2 < 6 with x, y Z+, only 2 + 32 satisfies

x2

dy2

= 1, so it is indeed the smallest positive solution.Now supposewe had a positive solution (x, y) which was not of the form (3+

2

2)n. Choose the largest n N such that x + yd > (3 + 22)n;then = (x + y

d) (3 + 2

2)n = (x + y

d) (3 2

2)n.

Write = x + y

d; then by multiplicativity (x, y) is an integral solution ofthePell equation. Moreover, by construction we have > 1, so by theLemmathis means that (x, y) is a positive solution. On the otherhand we have that < 3 + 2

2, since otherwise we would have x + y

2 > (3 + 2

2)n+1. But this

is a contradiction, since we noted above that 3 + 2

2 is the smallest solution withx, y > 0. This completes theproof.

Thus we have solved the Pell equation for d = 2. To add icing,we can giveexplicit formulas for the solutions. Namely, we knowthat every positive integralsolution (x, y) is of the form

xn + yn

d = (3 + 2

2)n

for n Z+. If we apply conjugation to this equation, then usingthe fact that it isa field hom*omorphism, we get

xn yn

d = (3 2

2)n.

Let us put u = 3 + 2

2 and u = u1 = 3 22. Then, adding the two equationsand dividingby 2 we get

xn =1

2(un + (u)n),

and similarly we can solve for yn

to get

yn =1

2

d(un (u)n).

In fact, we can do even better: u = 0.17157 . . ., so that forall n Z+, 12

(u)n

and 12d

(u)n are less than 12

. Since xn and yn are integers (even though the

formula does not make this apparent!), this means that we canneglect the (u)n

term entirely and just round to the nearest integer. For a realnumber such that 1

2is not an integer, there is a unique integer nearest to whichwe shall denote

by . We have proved:

7/30/2019 4400 Pell Notes

5/10

THE PELL EQUATION 5

Theorem 4. Every positive integer solution to x2 2y2 = 1 is ofthe form

xn = (3 + 2

2)n

2 ,yn = (3 + 2

2)n

2

2

for some positive integern.

Among other things, this explains why it was not so easy to findsolutions by hand:the size of both the x and y coordinates growexponentially! The reader is invitedto plug in a value of n forherself: for e.g. n = 17 it is remarkable how close theirrationalnumbers u17/2 and u17/(2

2) are to integers:

u17/2 = 5168247530882.999999999999949;

u17/(2

2) = 3654502875938.000000000000032.

A bit of reflection reveals that this has a lot to do with thefact thatxnyn is necessarily

very close to

2. Indeed, by turning this observation on its head we shallsolve thePell equation for general nonsquare d.

3. A result of Dirichlet

Lemma 5. (Dirichlet) For any irrational (real) number, there areinfinitely manyrational numbers x

y(with gcd(x, y) = 1) such that

|x/y | < 1y2

.

Proof. Since the lowest-term denominator of any rational numberxy

is unchanged

by subtracting any integer n, by subtracting the integer part []of we may

assume [0, 1). Now divide the half-open interval [0, 1) into nequal pieces:[0, 1n

) [ 1n

, 2n

) . . . [n1n

, 1). Consider the fractional parts of 0, , 2 , . . . , n .Sincewe have n +1 numbers in [0, 1) and only n subintervals, by thepigeonhole principlesome two of them must lie in the samesubinterval. That is, there exist 0 j 0, one has|L pN

qN| < A

qBN

for all sufficiently large N. On the other hand, Liouvilleproved the following:

Theorem 9. Suppose satisfies a polynomial equation adxd + . . .+ a1x + a0 with

Z-coefficients. Then there is A > 0 such that for allintegers p and 0 = q,

| pq| > A

qd.

7/30/2019 4400 Pell Notes

10/10

10 THE PELL EQUATION

That is, being algebraic of degree d imposes an upper limit onthe goodness ofthe approximation by rational numbers. An immediateand striking consequence is

that Liouvilles number L cannot satisfy an algebraic equation ofany degree: thatis, it is a transcendental number. In fact, by thisargument Liouville establishedthe existence of transcendentalnumbers for the first time!

Liouvilles theorem was improved by many mathematicians,including Thue andSiegel, and culminating in the following theoremof Klaus Roth:

Theorem 10. (Roth, 1955) Let be an algebraic real number (of anydegree),and let > 0 be given. Then there are at most finitelymany rational numbers p

q

satisfying

| pq| < 1

q2+.

For this result Roth won the Fields Medal in 1958.