Common Methods for Diophantine Equations

In one sentence

What makes integer solutions hard is that there are “infinitely many possibilities”. The three common methods all do the same thing: turn infinitely many into finitely many.

Factoring: rewrite the equation as $(\dots) (\dots) =$ a constant. An integer has only finitely many divisors.
Estimation (bounding): use inequalities to lock the unknowns into a finite range, then check each case.
Congruences: pick a modulus for which the two sides can never leave the same remainder, and the possibilities drop straight to zero.

Each of the three methods in action

Step 1 / 6

Factoring: first build a product
$x y - 2 x - 3 y = 1$ . The left side looks like the first three terms of $(x - 3) (y - 2)$ expanded; it is only missing the constant $6$ . Add $6$ to both sides.

$x y - 2 x - 3 y + 6 (x - 3) (y - 2) = 1 + 6 = 7$
Finitely many splits
Don't forget the negative ones
Estimation: lock the solutions in a box
Check the box cell by cell
Congruences: no cell survives

Stop 1 · Factoring

Spot it: an $x y$ term together with linear terms in $x$ and $y$ , or a difference of squares. Do it: add a constant to build a product, then list the divisors: each split gives a small system of equations to solve.

Predict first

$x^{2} - y^{2} = 12$ becomes $(x - y) (x + y) = 12$ . There are $12$ ways to split $12$ into two integer factors (counting negative factors and order). For how many of them do you get integer $x$ and $y$ ?

Choose an answer first; then you can see the result.

Stop 2 · Estimation

Spot it: sums of squares, sums of reciprocals, or one side that clearly “grows faster” than the other. Do it: put the unknowns in order of size or complete the square to get an inequality, which limits the smallest (or largest) unknown to just a few values.

One problem, several solutions

Find positive integers $x \leq y$ with $\frac{1}{x} + \frac{1}{y} = \frac{1}{4}$ .

Estimation

$\frac{1}{x} < \frac{1}{4}$ , so $x > 4$ . Also $x \leq y$ , so $\frac{1}{x} \geq \frac{1}{y}$ , which gives $\frac{2}{x} \geq \frac{1}{4}$ , that is, $x \leq 8$ .

You only need to check $x = 5, 6, 7, 8$ , working out $\frac{1}{y} = \frac{1}{4} - \frac{1}{x}$ :

$x = 5$ : $\frac{1}{20}$ , $y = 20$ ✓
$x = 6$ : $\frac{1}{12}$ , $y = 12$ ✓
$x = 7$ : $\frac{3}{28}$ , $y$ is not an integer ✗
$x = 8$ : $\frac{1}{8}$ , $y = 8$ ✓

CostNo clever rewriting needed, but you must check 4 candidates.

Factoring

Clear the denominators: $4 x + 4 y = x y$ , that is, $x y - 4 x - 4 y = 0$ . Add $16$ to both sides:

(x - 4) (y - 4) = 16

$x \leq y$ and both are greater than $4$ , so $x - 4 \leq y - 4$ are positive divisors: $1 \times 16$ , $2 \times 8$ , $4 \times 4$ .

This gives $(x, y) = (5, 20), (6, 12), (8, 8)$ .

CostYou must think of adding 16 after clearing denominators; after that it is one step.

Both methods find the same three solutions. When factoring is possible it is usually faster; when it is not (for example, a sum of reciprocals of three unknowns), estimation still works.

Stop 3 · Congruences

Spot it: the problem asks you to “prove there are no integer solutions”, or the equation has squares or cubes. Do it: choose a modulus that makes some terms vanish and leaves the powers as few remainders as possible.

x^{2} - 3 y^{2} = 2

. Drag the modulus from

2

9

: which moduli leave no cell at all? Which ones get you nowhere?

Mod $3$ and mod $8$ each settle it in one blow (and so, of course, do the multiples $6$ and $9$ ); mod $2, 4, 5, 7$ all leave surviving cells. Good first choices:

If the equation has	Try the modulus	Because
squares	$3$ , $4$ , $8$	$x^{2}$ leaves only $0, 1$ (mod $3$ , $4$ ) or $0, 1, 4$ (mod $8$ )
cubes	$7$ , $9$	$x^{3}$ leaves only $0, \pm 1$
a coefficient that is a multiple of $k$	$k$	that term simply vanishes

How to choose

There is no method that always works. Try every one of the four equations with each of the three methods on the workbench above and you get this table:

	Factoring	Estimation	Congruences
$x y - 2 x - 3 y = 1$	✓ four solutions	can't fence it in	only narrows it down
$x^{2} - y^{2} = 12$	✓ four solutions	can't fence it in	only narrows it down
$x^{2} + x y + y^{2} = 19$	doesn't factor	✓ check 121 cells	only narrows it down
$x^{2} - 3 y^{2} = 2$	doesn't factor	can't fence it in	✓ no solutions

Practice

Exercise 1Basic

How many positive integer solutions $(x, y)$ does $x y + x + y = 20$ have?

Exercise 2Basic

Find all positive integers $x$ for which there is a positive integer $y$ with $x^{2} - y^{2} = 45$ .

Exercise 3Advanced

Positive integers $x \leq y \leq z$ satisfy $\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1$ . How many such triples $(x, y, z)$ are there?

Exercise 4Challenge

Prove that $x^{3} + y^{3} = 2020$ has no integer solutions.

In one sentence

Each of the three methods in action

Stop 1 · Factoring

Stop 2 · Estimation

Estimation

Factoring

Stop 3 · Congruences

How to choose

Practice

Mistake Museum · Exhibits from this stop

Forgetting negative divisors when splitting

No contradiction mod m, so the equation has a solution

Finding the range, then not checking each case