Three methods solve most olympiad Diophantine equations. Factoring turns the equation into a product equal to a fixed number, so the factors are divisors. Bounding uses inequalities to leave only a few cases. A modular argument shows that no solution can exist, or limits the remainders. Pell's equation x2−dy2=1
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
solve an equation by factoring it into a product equal to a known number;
use inequalities to cut an equation down to a few cases;
prove that an equation has no solution by looking at remainders;
generate the solutions of a Pell equation from the smallest one.
Method 1: factoring
Differences of squares. Solve x2−y2=45 in positive integers. Write (x−y)(x+y)=45. The factors are positive, have the same parity, and the first is smaller. The pairs are 1×45, 3×15 and 5×9. They give (x,y)=(23,22), (9,6) and (7,2).
A number n is a difference of two squares exactly when n is odd or a multiple of 4. If n≡2(mod4), the two factors would have to be one even and one odd, but x−y and x+y have the same parity.
Simon's trick. Solve xy=2x+3y in positive integers. Move everything to one side and add a constant to complete a product:
xy−2x−3y+6=6,(x−3)(y−2)=6.
Now x−3 and y−2 are a pair of divisors of 6. Both cannot be negative: then x−3≥−2 and y−2≥−1 give a product of at most 2. So both are positive, and the four pairs give (4,8), (5,5), (6,4), (9,3).
Unit fractions.x1+y1=n1 becomes (x−n)(y−n)=n2. So the positive solutions match the divisors of n2. For n=6 there are 9, since 36 has 9 divisors.
Method 2: bounding
Solve a1+b1+c1=1 in positive integers. Order them: a≤b≤c.
Bound a. The largest fraction is a1, so 1≤a3, and a≤3. Also a≥2.
a=3. Then b1+c1=32 with b≥3, so b=c=3.
a=2. Then b1+c1=21, so (b−2)(c−2)=4, giving (b,c)=(3,6) or (4,4).
So the solutions are (3,3,3), (2,4,4) and (2,3,6), up to order. The idea: order the unknowns, then the smallest one is trapped.
Factorials and powers grow so fast that they are often bounded in the same way. If x!+y!=z! with x≤y<z, then z!≥(y+1)⋅y!, which is more than 2⋅y! unless y=1.
Method 3: remainders
Pick a modulus where the two sides cannot agree.
Squares modulo 4:x2+y2=4k+3 has no solution.
Squares modulo 3:x2−3y2=2 has no solution, since x2≡2(mod3) is impossible.
Cubes modulo 9: a cube is 0, 1 or 8 modulo 9. So x3+y3+z3 is never 4 or 5 modulo 9.
A good modulus makes the powers take few values: modulo 4 or 8 for squares, modulo 7 or 9 for cubes, and modulo 5 or 16 for fourth powers.
Infinite descent. Fermat's own method: from one solution, build a smaller one, again and again. Positive integers cannot decrease forever, so there was no solution. The proof that 2 is irrational is the simplest example: a2=2b2 forces a even, a=2a′, then b2=2a′2, a smaller solution.
Pell's equation in outline
Let d be a positive integer that is not a square. The equation
x2−dy2=1
is called Pell's equation. It has the trivial solution (1,0), and always infinitely many others. The smallest one with y>0 is the fundamental solution(x1,y1).
All solutions from one. Write the solutions as x+yd. Then
xk+ykd=(x1+y1d)k.
Why does a power stay a solution? If x2−dy2=1 and u2−dv2=1, then (xu+dyv)2−d(xv+yu)2=(x2−dy2)(u2−dv2)=1. So each solution gives the next by
xk+1=x1xk+dy1yk,yk+1=x1yk+y1xk.
For d=2 the fundamental solution is (3,2). Then come (17,12), (99,70) and (577,408). The ratios 23,1217,7099 are better and better fractions for 2.
The right branch of the hyperbola x squared minus 2 y squared = 1 in the first quadrant, for x from 1 to 110. Red dots mark its whole-number points (3, 2), (17, 12) and (99, 70). The dashed line y = x divided by the square root of 2 is the asymptote, and the dots lie closer and closer to it.
That every solution is a power of the fundamental one, and that a solution exists for every non-square d, are proved with continued fractions in a first university course. Olympiads usually give or ask for the fundamental solution by a short search.
Practise with new numbers
Try it in Python
The program counts the solutions of a unit-fraction equation by factoring, then prints the first solutions of x2−2y2=1 with the step rule.
Common mistakes
Forgetting negative factor pairs. For integer solutions, (x−3)(y−2)=6 also has (−1)(−6) and others. Check each one.
Bounding without ordering. Assume a≤b≤c first, then put the order back at the end.
Choosing a modulus where every remainder occurs. Squares modulo 5 take three values, but modulo 2 they take both. Pick a modulus that rules something out.
Taking (1,0) as the fundamental solution of Pell's equation. The fundamental solution has y>0.
Remember these
Factoring: turn the equation into a product equal to a known number.
Bounding: order the unknowns and trap the smallest.
Remainders: squares, cubes and fourth powers take few values modulo small numbers.
Pell: all solutions of x2−dy2=1 come from the powers of x1+y1d.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Find all positive solutions of x2−y2=21.
Is 2026 a difference of two squares?
Why has x2+y2=1003 no integer solution?
The fundamental solution of x2−3y2=1 is (2,1). Find the next one.
Find all positive solutions of xy=x+y.
References
David M. Burton, Elementary Number Theory, Chapter 12, Certain Nonlinear Diophantine Equations, and Chapter 15, Continued Fractions, the section on Pell's equation.
Enroll free in Diophantine Equations and Pythagorean Triples
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.