Integer Solutions of Equations

In one sentence

One equation in two unknowns has infinitely many real solutions, joined up into a curve. But if you only want integer solutions, everything changes: they are the lattice points the curve happens to pass through. They are few and far between, often only finitely many, sometimes none at all.

The whole art of finding integer solutions is to use the properties only integers have — divisibility, factorization, bounds, parity — to sift infinitely many candidates down to a few you can count.

Example: positive integer solutions of 3x + 5y = 47

Step 1 / 5

Find one first
Try a few values of $y$ : at $y = 7$ , $3 x = 47 - 35 = 12$ , so $x = 4$ . So $(4, 7)$ is an integer solution, and the line passes through this lattice point.

$3 \times 4 + 5 \times 7 = 47$
How to reach the next lattice point
Write down all the integer solutions
Add the condition “positive integers”
Count them

Stop 1 · Divisibility: does the line ever hit a lattice point?

$a x + b y = c$ need not have integer solutions. Whatever integers $x$ and $y$ are, the left side is a multiple of the greatest common divisor of $a$ and $b$ . If the right side is not, there is no hope.

Break it

Counterexample lab: remove one condition

Conclusion: $a x + b y = c$ has integer solutions

$6 x + 9 y = 21$ : the gcd of $6$ and $9$ is $3$ , and $21$ is a multiple of $3$ . The line has lattice points on it, one at regular intervals.

Stop 2 · Factorization: turn a sum into a product

The equation $x y - 2 x - 3 y = 0$ looks hard to get a grip on. But add $6$ to both sides and the left side factors:

x y - 2 x - 3 y + 6 = 6 ⟹ (x - 3) (y - 2) = 6

There are only finitely many ways for two integers to multiply to $6$ . Each way of splitting it gives one lattice point on the curve.

Predict first

How many integer solutions does $(x - 3) (y - 2) = 6$ have? (Count both positive and negative ones.)

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

Stop 3 · Bounds: fence in the range, then check one by one

$x^{2} + y^{2} = 50$ . A square is never negative, so $x^{2} \leq 50$ and $∣ x ∣ \leq 7$ . The candidates shrink at once from “every integer” to about a dozen, and you can just check them one at a time.

Drag

∣ x ∣

from

0

7

. At each column there is only one question: is

50 - x^{2}

a perfect square?

The key to this move is first proving that there are only finitely many candidates. Once the range is fenced in, even the slow way is sure to finish.

Stop 4 · Parity: sometimes there are no solutions at all

One problem, several solutions

Find the positive integer solutions of $x^{2} - y^{2} = 21$ .

Factor into a product

$(x - y) (x + y) = 21$ . Since $x$ and $y$ are positive integers, $x + y > x - y > 0$ , so there are only two ways to split it:

$x - y = 1$ , $x + y = 21$ : $x = 11$ , $y = 10$
$x - y = 3$ , $x + y = 7$ : $x = 5$ , $y = 2$

Two solutions: $(11, 10)$ and $(5, 2)$ .

CostFastest, but the equation itself must factor.

Bound the range, then list

$x > y$ , so $x \geq y + 1$ and $x^{2} - y^{2} \geq (y + 1)^{2} - y^{2} = 2 y + 1$ . So $2 y + 1 \leq 21$ , and $y \leq 10$ .

Substitute $y = 1, 2, \dots, 10$ one by one and see whether $21 + y^{2}$ is a perfect square: only $y = 2$ ( $25 = 5^{2}$ ) and $y = 10$ ( $121 = 1 1^{2}$ ).

CostDoes not need factoring, but takes more tries.

What happens to the same equation if we change $21$ to $30$ ?

x² − y² = 30 has no integer solutions

Step 1 / 4

Factor first, as before
$(x - y) (x + y) = 30$ .

$(x - y) (x + y) = 30$
The two factors have the same parity
Neither case works
Conclusion

Practice

Exercise 1Basic

How many positive integer solutions does $2 x + 3 y = 20$ have?

Exercise 2Basic

Among all integer solutions of $x y + 2 x - y = 7$ , what is the largest value of $x$ ?

Exercise 3Advanced

How many integer solutions does $x^{2} + y^{2} = 65$ have?

Exercise 4Challenge

How many positive integer solutions does $\frac{1}{x} + \frac{1}{y} = \frac{1}{6}$ have?

In one sentence

Example: positive integer solutions of 3x + 5y = 47

Stop 1 · Divisibility: does the line ever hit a lattice point?

Counterexample lab: remove one condition

Stop 2 · Factorization: turn a sum into a product

Stop 3 · Bounds: fence in the range, then check one by one

Stop 4 · Parity: sometimes there are no solutions at all

Factor into a product

Bound the range, then list

x² − y² = 30 has no integer solutions

Practice

Mistake Museum · Exhibits from this stop

Swapping the step sizes in the general solution

Thinking only of positive factors