Transcription
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesExploring Number Theory via DiophantineEquationsSunil ChettyDepartment of MathematicsColorado CollegeFall, 2009Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesOutlineSome HistoryFirst ExamplesLinear Diophantine EquationsPythagorean TriplesPell’s EquationIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremSunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesDiophantusDiophantine equations are named after the Greekmathematician Diophantus, c. 250, of Alexandria. In hisArithmetica, a treatise of several books, he studies some 200equations in two or more variables with the restriction that thesolutions be rational numbers.(1570) Bombelli included translated parts in his Algebra.(1575) Holzmann (a.k.a. Xylander) attempted a completedtranslation.(1593) Viète reproduced a large part in his Zetetica.(1621) Bachet published Diophantus’ text in Greek, as well as aLatin translation with commentary.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesFermat, Euler, and GaussWeil, in his book Number Theory, remarks that the birth ofmodern number theory happens on two occassions. by 1636, as we learn from his correspondence,[Fermat] had not only studied [Bachet] but was alreadydeveloping ideas of his own. In 1729. Euler reportsthat he has “just been reading Fermat” and that he hasbeen greatly impressed by Fermat’s assertion thatevery integer is a sum of four squares.In 1801, Gauss’ Disquisitiones Arithmeticae marked theculmination of the work of Fermat, Euler, and others. Gaussalso introduces fundamental concepts such as congruencesand generalized integers.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesHilbertIn 1900, with the long history of mathematicians working onvarious Diophatine equations, David Hilbert challenged themathematical community to find an algorithm which woulddetermine, given a Diophantine equation, whether or not thereis a solution in the integers.Theorem (Davis-Putnam-Robinson, Matijasevic̆)There is no such algorithm.This theorem, in some sense, forces us to attack Diophantineequations in a more reserved manner, but also ensures thatthere is still work to do.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesLinear Diophantine EquationsPythagorean TriplesAn ExampleSuppose there is a piggy bank which contains only quarters,dimes, and nickels, with a total value of 10. Can we determineexactly how many of each coin is inside?A model we could use for answering this question is a “linearDiophantine equation”25x 10y 5z 1000,with x representing the number of quarters, y the dimes, and zthe nickels.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesLinear Diophantine EquationsPythagorean TriplesTwo-Variable Linear Diophantine EquationsA linear Diophantine equation in two variables is of the formax by c 0orax by c,with a, b, and c integers, and for which the variables x and y canonly have integer values.QuestionCan we determine when such an equation has a solution?ExampleConsider 30x 14y 1.We can rewrite this as 2(15x 7y) 1, so the left side is alwayseven and the right side is never even.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesLinear Diophantine EquationsPythagorean TriplesGreatest Common DivisorThe greatest common divisor, or GCD, of two integers a andb is the largest positive integer which divides both a and b. Wedenote it by (a, b).ExampleLet a 30 and b 14. Since30 2 · 15 2 · 3 · 5and14 2 · 7,the common divisors are 1 and 2. So (30, 14) 2.We can express the GCD as a “linear combination”:2 30 28 30(1) 14( 2).Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesLinear Diophantine EquationsPythagorean TriplesExistence of a SolutionIn the example 30x 14y 1, the GCD of 30 and 14 does notdivide 1 and the equation has no solutions.Consider 30x 14y 6. With x 1 and y 2, we saw30(1) 14( 2) 2.Since 6 2 · 3, when we try x 3, and y 2 · 3 6:30(3) 14( 6) 3( 30(1) 14( 2) ) 3(2) 6.TheoremFor ax by c, there is a solution when c is divisible by (a, b),otherwise there are none.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesLinear Diophantine EquationsPythagorean TriplesAll SolutionsWe have explored when a solution exists, but in number theorywe would like to understand all solutions.We continue with 30x 14y 6, and the solution x 3, y 6above. Suppose u and v give another solution.30u 14v 30(3) 14( 6) 30(u 3) 14( 6 v) 15(u 3) 7( 6 v)This forces, for some integer k,u 3 7k and v 6 15k,so our one explicit solution tells us how to get all the others.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesLinear Diophantine EquationsPythagorean TriplesPythagorean TriplesA familiar non-linear Diophantine equation is x2 y2 z2 .We see (3, 4, 5), (6, 8, 10), and (5, 12, 13) all satisfy the equation.QuestionsAre we in a situation as above? Does one solution produceothers in a simple way? All others?If (x, y, z) is Pythagorean, then so is (kx, ky, kz) since(kx)2 (ky)2 k2 (x2 y2 ) k2 z2 (kz)2 .So, (3, 4, 5) produces (6, 8, 10), (9, 12, 15), . . . , (51, 68, 85), . . .Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesLinear Diophantine EquationsPythagorean TriplesPrimitive SolutionsLet (x, y, z) be Pythagorean, with (x, y) (x, z) (y, z) 1.(We may assume x, z are odd and y is even.)Factoring, we get y2 z2 x2 (z x)(z x), and since y iseven, y 2 z x z x .222Since (x, z) 1, the terms on the right have no common factors.With a little algebra we get, for some integers r and s,z x 2r2 , z x 2s2 , and y 2rs.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesLinear Diophantine EquationsPythagorean TriplesGaussian IntegersRecall all complex numbers can be written as a ib, where aand b are real numbers and i : 1. If we only allow integervalues for a and b we have the set Z[i] of “Gaussian integers.”FactZ[i] enjoys the property of unique factorization into “primes”.In Z[i], we can factor z2 x2 y2 (x iy)(x iy), and thenunique factorization leads tox iy (r si)2 (r2 s2 ) i(2rs).Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationPell’s EquationLet d be an integer. A Pell equation is one of the formx2 dy2 1.In 1657, Fermat challenged the English mathematicians of thetime to solve x2 dy2 1 for general d, and if failing that to atleast try x2 61y2 1 and x2 109y2 1, where he chose smallcoefficients “pour ne vous donner pas trop de peine” (so youdon’t have too much work).dxy6031461176631904922615398062638Sunil ophantine Equations110212
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationSimple CasesWith any Pell equation x2 dy2 1, there are the trivialsolutions x 1, y 0, and possibly x 0, y 1.Suppose d 1. Then there can be no non-trivial solutionssincex2 ( 1)y2 x2 y2 1.Now suppose d 4 (a perfect square). Thenx2 4y2 x2 (22 )y2 x2 (2y)2 (x 2y)(x 2y) 1.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationRemaining CasesFrom now on we assume d 0 and is not a perfect square.FactIf d 0 is not a perfect square then d is irrational.Notice that for x, y 0 21x d 2 d.x dy 1 yy is a rational number which approximates d.2So,xy2Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationApproximating Irrational NumbersLet x be an irrational number. We define a sequence of integers{a0 , a1 , a2 , . . .} as follows.ISet a0 to be the largest integer x, and x1 1/(x a0 ).Note that x1 is irrational and x1 1.ISet a1 to be the largest integer x1 , and x2 1/(x1 a1 ).ISet ai to be the largest integer xi , and xi 1 1/(xi ai ).This gives a sequence of rational approximations to xp11 p21p0 a0 , a0 , a0 q0q1a1 q2a1 Sunil ChettyDiophantine Equations1a2, .
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationAn ExampleConsider x I 2. First, 1 x 2, so a0 1 and x1 1/( 2 1) 2 1.INext, 2 x1 3, so a1 2 and then11 2 1 2 1.x2 ( 2 1) 2ISince x2 x1 , the process repeats and our sequence is{1, 2, 2, 2, . . .}.The sequence of rational approximations is thenp0p113 p21 1, 1 , 1 q0q122 q22 Sunil ChettyDiophantine Equations127 , .5
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationApplications to Pell’s EquationTheorem pqthen pq is one of the continued fraction rational approximations of 2.2 If 12q2What if we know x, y 0 is a solution to x2 2y2 1?Example: d 2Let x 17, y 12:I172 2 · 122 289 2 · 144 289 288 1. I2 1712 .002453 .003472 Sunil Chetty1.2·122Diophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationGenerating New Solutions If we allow ourselves to work with d, we have x2 dy2 (x y d)(x y d)and multiplication formula (x y d)(u v d) (xu dyv) (xv uy) d.With these, if x2 dy2 1 and u2 dv2 1 then1 (x2 dy2 )(u dv2 ) (x dy)(x dy)(u dv)(u dv)(x dy)(u dv)(x dy)(u dv)(xu dyv)2 d(xv uy)2 .Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationAn ExampleNow, from one solution with x 0 and y 0, we have infinitelymany solutions xn yn d (x y d)n , for n 1.Example: d 2We see that x 3, y 2 is a solution to x2 2y2 1. I (3 2 2)2 17 12 2. I (3 2 2)3 99 70 2. I (3 2 2)4 577 408 2. I (3 2 2)5 3363 2378 2.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationA Complete SolutionTheorem (Lagrange, 1768)There exists a positive integer solution x1 , y1 to the Pell equationx2 dy2 1 such that all other positive integer solutions xn , ynare derived from it via the power rule xn yn d (x1 y1 d)n , for n 1.Note: It not quite as simple to describe the solutions ofx2 dy2 1,but they will still come from the rational approximation processdescribed above.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationPolygonal NumbersThe d-gonal numbers are partial sums of the arithmeticprogression with initial term 1 and common difference d 2.Tn 1 2 · · · n n(n 1)2Sn 1 3 · · · (2n 1) n22Pn 1 4 · · · (3n 2) 3n 2 nSunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationTriangular-Square NumbersA triangular-square number: Tm Sn for some m and n.QuestionAre there any triangular-square numbers besides 1?By the formulae above 1 21m 2 4 (2m 1)2 1 Tmm2 m2m2 mSnn22n22n22(2n)2(2m 1)2 2(2n)2 1.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationTriangular-Square NumbersSo, the question is reduced to solving x2 2y2 1 with x, y 0and x odd, y even.It turns out that to satisfy this equation, x must be odd and ymust be even.xym (x 1)/2n y/2Tm 7816811189141372119601138609800693048024900Note T49 S35 1225 means 1 2 · · · 49 35 · 35.(These numbers are Sloane’s A001110.)Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationSquare-Pentagonal NumbersA square-pentagonal number: Sm Pn for some m and n.QuestionAre there any square-pentagonal numbers besides 1?By the formulae aboveSm Pn2m2 3n 2 n2m2 3n 2 n 22m2 3 n 61 6(2m)2 (6n 1)2 1(6n 1)2 6(2m)2 1.Sunil ChettyDiophantine Equations136
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationSquare-Pentagonal NumbersThis time the problem is reduced to solving x2 6y2 1, withx, y 0, x 6n 1, and y even.In x2 6y2 1, y is always even, x 6n 1, but not necessarilyx 6n 1.xymnSm 194109401(These numbers are Sloane’s A036353.)Sunil ChettyDiophantine Equations470449192060
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationPythagorean Triples againAre there other Pythagorean triples like (3, 4, 5), i.e. withconsecutive numbers in the first two variables?We want to solve m2 (m 1)2 n2 .Notice that here, n must be odd.2m2 2m 1 n222(m2 m) 1 n 22 m 21 14 1 n2(2m 1)2 1 2n2(2m 1)2 2n2 1Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationPythagorean Triples againm2 (m 1)2 n2 (2m 1)2 2n2 1.So, we need to understand solutions to x2 2y2 1. It turnsout x and y must be odd, so our condition on n is automatic.xym (x 1)/2n y32 42 52 ,1101753541292029202 212 292 ,Sunil 2 1202 1692 .Diophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesIntroduction to Pell’s EquationContinued FractionsElementary Problems and Pell’s EquationPythagorean Triples againAre there Pythagorean triples with consecutive numbers in thelast two variables?We want m2 n2 (n 1)2 , which is equivalent to m2 2n 1.So, m needs to be odd, i.e. m 2k 1. This makesn (m2 1)/2 2k2 2k.k2k 12k2 2k2k2 2k 113452512133724254940415116061This has nothing to do with Pell’s equation.Sunil ChettyDiophantine Equations6138485
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremAn ExampleIn the 17th century, Bachet and Fermat studied the equationy2 x3 2. We will see that this equation has a finite number ofsolutions in the integers.We can start by simple trial-and-error:Ix 1: 13 2 1 2 1, no possible (real) y.Ix 2: 23 2 8 2 6, no possible (integer) y.Ix 3: 33 2 27 2 25 52 , so y 5 works.So far, (3, 5) are two integral solution of the equation.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremIntegral Solutions of y2 x3 2Recall: Z[i] consists of complex numbers x iy, with x, yrestricted to the integers. If we denote α 2, we can define a set Z[α] of complexnumbers of the form x αy, again with x, y restricted to theintegers.FactZ[α] also has the property of unique factorization into “primes.”In Z[α], the equation y2 x3 2 can be factored(y α)(y α) x3 .Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremIntegral Solutions of y2 x3 2From (y α)(y α) x3 and unique factorization, one obtainsy α (u αv)3 , u, v integers.Expanding the right-hand side and collecting terms givesy u3 6uv2 and 1 3u2 2v3 v(3u2 2v2 ),so it must be that u v 1.Thus, the only integral solutions to y2 x3 2 are (3, 5).Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremElliptic CurvesThe equation y2 x3 2 is an example of an elliptic curve.More generally, an elliptic curve is the set of solutions to anequation of the formy2 x3 ax2 bx c.For integral solutions there is a nice theorem.Theorem (Siegel, 1926)If a, b, and c are integers, then there are only finitely manyintegral solutions to y2 x3 ax2 bx c.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremAdding SolutionsFor elliptic curves, understanding all of the solutions in therational numbers is a much more complicated problem.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremMordell-Weil TheoremIn 1922, Mordell used Fermat’s idea of “descent” to proveTheorem (Mordell, 1922)For y2 x3 ax2 bx c, with a, b, and c integers, there existsa finite set of rational solutions (x1 , y1 ), . . . , (xr , yr ) such that allother rational solutions can be obtained from these by repeatedapplication of the chord-tangent process.ProblemThis proof only gives existence. Currently, there is no method togenerate this finite set, nor a way to determine just how manypoints (the rank) are needed in this finite set.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremThe StatementIn his copy of Bachet, Fermat stated:Cubum autem in duos cubos,aut quadratoquadratum in duosquadratoquadratos, etgeneraliter nullam in infinitumultra quadratum potestatem induos eiusdem nominis fas estdividere cuius reidemonstrationem mirabilemsane detexi. Hanc marginisexiguitas non caperet.It is impossible to separate acube into two cubes, or a fourthpower into two fourth powers, orin general, any power higherthan the second into two likepowers. I have discovered atruly marvellous proof of this,which this margin is too narrowto contain.I.e., the equation xn yn zn has no integer solutions.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremFrey, Ribet, and WilesIn 1985, Frey suggested that one consider the elliptic curveEa,b,c : y2 x(x an )(x bn )where an bn cn . A conjecture of Taniyama and Shimurastates that such an elliptic curve should be “modular.”Theorem (Ribet)Theorem (Wiles-Taylor)Ea,b,c is not modular.Ea,b,c is modular.So, assuming there exist integers a, b, c with an bn cn leadsto a contradiction by way of a strange elliptic curve.Sunil ChettyDiophantine Equations
Some HistoryFirst ExamplesPell’s EquationElliptic CurvesEarly WorkFermat’s Last TheoremThe EndThank you for your attention.Sunil ChettyDiophantine Equations
Introduction to Pell's Equation Continued Fractions Elementary Problems and Pell's Equation Simple Cases With any Pell equation x2 dy2 1, there are the trivial solutions x 1, y 0, and possibly x 0, y 1. Suppose d 1. Then there can be no non-trivial solutions since x2 ( 1)y2 x2 y2 1: Now suppose d 4 (a perfect square). Then
