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

  • 7/30/2019 4400 Pell Notes



    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


    = 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



    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


    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


    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


    d] = {a + b

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


    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


    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(


    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



    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) = (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 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



    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



    = 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)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


    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


    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


    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


    d(un (u)n).

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


    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



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

    xn = (3 + 2


    2 ,yn = (3 + 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;


    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


    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


  • 7/30/2019 4400 Pell Notes



    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



    | pq| < 1


    For this result Roth won the Fields Medal in 1958.

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


Which IRS publication would a volunteer use to determine if a topic is out of scope for Vita tce? ›

Scope refers to VITA/TCE tax law topics applied to a volunteer prepared tax return. Scope does not refer to income levels. A Scope of Service Chart is in Publication 4012, VITA/TCE Volunteer Resource Guide.

What is IRS pub 4491? ›

Publication 4491 Adjustments to Income

Taxpayers can subtract certain expenses, payments, contributions, fees, etc. from their total income. The adjustments, subtracted from total income on Form 1040, establish the adjusted gross income (AGI).

What is the IRS volunteer deduction? ›

The out-of-pocket expenses a volunteer incurs in service to a member of a charitable class may be deductible, but only if the recipient is chosen by the organization the volunteer serves. If the volunteer chooses to help someone he or she knows, the out-of-pocket expenses to that person are not deductible.

What is out of scope for AARP? ›

Some of the items that are out of scope include rental property income (except land only), farm income, certain income items on Schedule K-1, moving expenses, casualty and theft losses, the Alternative Minimum Tax and loss from a self-employment business.


Top Articles
Latest Posts
Article information

Author: Duncan Muller

Last Updated:

Views: 6383

Rating: 4.9 / 5 (59 voted)

Reviews: 82% of readers found this page helpful

Author information

Name: Duncan Muller

Birthday: 1997-01-13

Address: Apt. 505 914 Phillip Crossroad, O'Konborough, NV 62411

Phone: +8555305800947

Job: Construction Agent

Hobby: Shopping, Table tennis, Snowboarding, Rafting, Motor sports, Homebrewing, Taxidermy

Introduction: My name is Duncan Muller, I am a enchanting, good, gentle, modern, tasty, nice, elegant person who loves writing and wants to share my knowledge and understanding with you.