HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Diophantine Equations and Pythagorean Triples
  1. 1Linear Diophantine equations
  2. 2Pythagorean triples
  3. 3Factoring, bounding and Pell's equation
  1. Mathematics
  2. /Diophantine Equations and Pythagorean Triples
  3. /Factoring, bounding and Pell's equation

Course 28.3·Lesson 3 of 3

Factoring, bounding and Pell's equation

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=1x^2 - dy^2 = 1x2−dy2=1

Lesson 3 of 3Show all lessonsHide
Diophantine Equations and Pythagorean Triples
  1. 1Linear Diophantine equations
  2. 2Pythagorean triples
  3. 3Factoring, bounding and Pell's equation

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=45x^2 - y^2 = 45x2−y2=45 in positive integers. Write (x−y)(x+y)=45(x - y)(x + y) = 45(x−y)(x+y)=45. The factors are positive, have the same parity, and the first is smaller. The pairs are 1×451 \times 451×45, 3×153 \times 153×15 and 5×95 \times 95×9. They give (x,y)=(23,22)(x, y) = (23, 22)(x,y)=(23,22), (9,6)(9, 6)(9,6) and (7,2)(7, 2)(7,2).

A number nnn is a difference of two squares exactly when nnn is odd or a multiple of 444. If n≡2(mod4)n \equiv 2 \pmod 4n≡2(mod4), the two factors would have to be one even and one odd, but x−yx - yx−y and x+yx + yx+y have the same parity.

Simon's trick. Solve xy=2x+3yxy = 2x + 3yxy=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.\displaystyle xy - 2x - 3y + 6 = 6, \qquad (x - 3)(y - 2) = 6.xy−2x−3y+6=6,(x−3)(y−2)=6.

Now x−3x - 3x−3 and y−2y - 2y−2 are a pair of divisors of 666. Both cannot be negative: then x−3≥−2x - 3 \ge -2x−3≥−2 and y−2≥−1y - 2 \ge -1y−2≥−1 give a product of at most 222. So both are positive, and the four pairs give (4,8)(4, 8)(4,8), (5,5)(5, 5)(5,5), (6,4)(6, 4)(6,4), (9,3)(9, 3)(9,3).

Unit fractions. 1x+1y=1n\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}x1​+y1​=n1​ becomes (x−n)(y−n)=n2(x - n)(y - n) = n^2(x−n)(y−n)=n2. So the positive solutions match the divisors of n2n^2n2. For n=6n = 6n=6 there are 999, since 363636 has 999 divisors.

Method 2: bounding

Solve 1a+1b+1c=1\dfrac{1}{a} + \dfrac{1}{b} + \dfrac{1}{c} = 1a1​+b1​+c1​=1 in positive integers. Order them: a≤b≤ca \le b \le ca≤b≤c.

  1. Bound aaa. The largest fraction is 1a\dfrac{1}{a}a1​, so 1≤3a1 \le \dfrac{3}{a}1≤a3​, and a≤3a \le 3a≤3. Also a≥2a \ge 2a≥2.
  2. a=3a = 3a=3. Then 1b+1c=23\dfrac{1}{b} + \dfrac{1}{c} = \dfrac{2}{3}b1​+c1​=32​ with b≥3b \ge 3b≥3, so b=c=3b = c = 3b=c=3.
  3. a=2a = 2a=2. Then 1b+1c=12\dfrac{1}{b} + \dfrac{1}{c} = \dfrac{1}{2}b1​+c1​=21​, so (b−2)(c−2)=4(b - 2)(c - 2) = 4(b−2)(c−2)=4, giving (b,c)=(3,6)(b, c) = (3, 6)(b,c)=(3,6) or (4,4)(4, 4)(4,4).

So the solutions are (3,3,3)(3, 3, 3)(3,3,3), (2,4,4)(2, 4, 4)(2,4,4) and (2,3,6)(2, 3, 6)(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!x! + y! = z!x!+y!=z! with x≤y<zx \le y < zx≤y<z, then z!≥(y+1)⋅y!z! \ge (y + 1) \cdot y!z!≥(y+1)⋅y!, which is more than 2⋅y!2 \cdot y!2⋅y! unless y=1y = 1y=1.

Method 3: remainders

Pick a modulus where the two sides cannot agree.

  • Squares modulo 4: x2+y2=4k+3x^2 + y^2 = 4k + 3x2+y2=4k+3 has no solution.
  • Squares modulo 3: x2−3y2=2x^2 - 3y^2 = 2x2−3y2=2 has no solution, since x2≡2(mod3)x^2 \equiv 2 \pmod 3x2≡2(mod3) is impossible.
  • Cubes modulo 9: a cube is 000, 111 or 888 modulo 999. So x3+y3+z3x^3 + y^3 + z^3x3+y3+z3 is never 444 or 555 modulo 999.

A good modulus makes the powers take few values: modulo 444 or 888 for squares, modulo 777 or 999 for cubes, and modulo 555 or 161616 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\sqrt 22​ is irrational is the simplest example: a2=2b2a^2 = 2b^2a2=2b2 forces aaa even, a=2a′a = 2a'a=2a′, then b2=2a′2b^2 = 2a'^2b2=2a′2, a smaller solution.

Pell's equation in outline

Let ddd be a positive integer that is not a square. The equation

x2−dy2=1\displaystyle x^2 - dy^2 = 1x2−dy2=1

is called Pell's equation. It has the trivial solution (1,0)(1, 0)(1,0), and always infinitely many others. The smallest one with y>0y > 0y>0 is the fundamental solution (x1,y1)(x_1, y_1)(x1​,y1​).

All solutions from one. Write the solutions as x+ydx + y\sqrt dx+yd​. Then

xk+ykd=(x1+y1d)k.\displaystyle x_k + y_k\sqrt d = (x_1 + y_1\sqrt d)^k.xk​+yk​d​=(x1​+y1​d​)k.

Why does a power stay a solution? If x2−dy2=1x^2 - dy^2 = 1x2−dy2=1 and u2−dv2=1u^2 - dv^2 = 1u2−dv2=1, then (xu+dyv)2−d(xv+yu)2=(x2−dy2)(u2−dv2)=1(xu + dyv)^2 - d(xv + yu)^2 = (x^2 - dy^2)(u^2 - dv^2) = 1(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.\displaystyle x_{k+1} = x_1 x_k + d y_1 y_k, \qquad y_{k+1} = x_1 y_k + y_1 x_k.xk+1​=x1​xk​+dy1​yk​,yk+1​=x1​yk​+y1​xk​.

For d=2d = 2d=2 the fundamental solution is (3,2)(3, 2)(3,2). Then come (17,12)(17, 12)(17,12), (99,70)(99, 70)(99,70) and (577,408)(577, 408)(577,408). The ratios 32,1712,9970\tfrac{3}{2}, \tfrac{17}{12}, \tfrac{99}{70}23​,1217​,7099​ are better and better fractions for 2\sqrt 22​.

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 ddd, 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=1x^2 - 2y^2 = 1x2−2y2=1 with the step rule.

Read it first. Then run it. Does every Pell line check to 111?

1. Change n = 6 to n = 10. How many solutions? Compare with the number of divisors of 100100100.

2. Change the step to x, y = 2 * x + 3 * y, x + 2 * y and start from x, y = 2, 1. Which equation do the new pairs solve?

Common mistakes

  • Forgetting negative factor pairs. For integer solutions, (x−3)(y−2)=6(x - 3)(y - 2) = 6(x−3)(y−2)=6 also has (−1)(−6)(-1)(-6)(−1)(−6) and others. Check each one.
  • Bounding without ordering. Assume a≤b≤ca \le b \le ca≤b≤c first, then put the order back at the end.
  • Choosing a modulus where every remainder occurs. Squares modulo 555 take three values, but modulo 222 they take both. Pick a modulus that rules something out.
  • Taking (1,0)(1, 0)(1,0) as the fundamental solution of Pell's equation. The fundamental solution has y>0y > 0y>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=1x^2 - dy^2 = 1x2−dy2=1 come from the powers of x1+y1dx_1 + y_1\sqrt dx1​+y1​d​.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Find all positive solutions of x2−y2=21x^2 - y^2 = 21x2−y2=21.
  1. Is 202620262026 a difference of two squares?
  1. Why has x2+y2=1003x^2 + y^2 = 1003x2+y2=1003 no integer solution?
  1. The fundamental solution of x2−3y2=1x^2 - 3y^2 = 1x2−3y2=1 is (2,1)(2, 1)(2,1). Find the next one.
  1. Find all positive solutions of xy=x+yxy = x + yxy=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.
No payment. You can leave at any time.

Problems (4)

Find all pairs of positive integers (x, y) with x² - y² = 945…Hard · High School (11–12) · by StemPy Lab
Find every triple of positive integers a ≤ b ≤ c with 1/a + 1/b + 1/c = 1, and prove that there are…Advanced · High School (11–12) · by StemPy Lab
Prove that the equation x³ + y³ + z³ = n has no solution in integers when n leaves remainder 4 or 5…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← Diophantine Equations and Pythagorean Triples
← Pythagorean triplesNext →

Discussion (0)

Log in to join the discussion.

Loading…

has infinitely many solutions, all built from the smallest one.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

The triangular numbers are 1, 3, 6, 10, …, where the nth one is (n(n + 1))/2…Advanced · High School (11–12) · by StemPy Lab

Question Sets (1)

Diophantine Equations: Concept Check10 questions · by StemPy Lab

Notes (1)

Diophantine Equations and Pythagorean Triples: Quick RevisionNote · by StemPy Lab