Choosing a Good Modulus

In one sentence

If two integers are equal, they leave the same remainder when divided by any number $m$ .

Use it the other way round: if you can find an $m$ such that the left side, whatever values it takes, can never leave the right side’s remainder, then the equation has no integer solutions. Infinitely many possibilities, all checked with one small table of remainders.

There is only one hard part: which $m$ to choose. A few common “wanted posters”:

Squares: mod $3$ they leave only $0, 1$ ; mod $4$ only $0, 1$ ; mod $8$ only $0, 1, 4$ .
Cubes: mod $7$ they leave only $0, 1, 6$ ; mod $9$ only $0, 1, 8$ .
Fourth powers: mod $5$ they leave only $0, 1$ ; mod $16$ only $0, 1$ .

Predict first

How many different remainders can a perfect square leave on division by $4$ ?

4

0, 1, 2, 3

3

0, 1, 2

2

0, 1

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

Stop 1 · Congruences (Vol. 6)

You do not need to memorize remainder tables: just make one on the spot.

Example: is there a perfect square among 11, 111, 1111, …?

Step 1 / 4

Too big: look only at remainders
These numbers keep growing, so you cannot take square roots one by one. Ask a different question: what do they leave on division by $4$ ?

$11, 111, 1111, 11111, \dots$
Mod 4, only the last two digits matter
Look up the squares in the table
No match

Stop 2 · Residue systems (Vol. 6)

For squares, look mod $4$ or mod $8$ . What about cubes? Try them one at a time.

Example: does x³ + y³ = 2020 have integer solutions?

Step 1 / 5

Try mod 2 first
Cubing does not change parity: $x^{3}$ can leave $0$ or $1$ . The left side can make any remainder, so there is no contradiction.
Mod 3 does not work either
Find a modulus where cubes are “picky”
The right side leaves 4
Mod 7 works too

Why $7$ and $9$ of all numbers? No need to memorize it. Open the power table in the “Modular Arithmetic Lab”: try a few moduli, see which one gives the fewest remainders in the $n^{3}$ column, and choose that one.

Stop 3 · Perfect squares (Vol. 6)

The coefficient itself is often the best modulus.

The sum of the squares of three consecutive integers $n - 1, n, n + 1$ is

(n - 1)^{2} + n^{2} + (n + 1)^{2} = 3 n^{2} + 2.

Can this be a perfect square? Setting it equal to $m^{2}$ , the question is whether $m^{2} - 3 n^{2} = 2$ has integer solutions.

Example: does m² − 3n² = 2 have integer solutions?

Step 1 / 4

Try mod 4 out of habit
Mod $4$ , the old friend of squares: the left side can leave $0, 1, 2$ , and the right side leaves $2$ . They match, so no contradiction. Careful: this does not mean there is a solution.
Look at the coefficient 3
Squares mod 3
Conclusion

Stop 4 · Diophantine equations (Vol. 6)

When both coefficients stand out, try each of them.

Example: does 15x² − 7y² = 9 have integer solutions?

Step 1 / 5

Mod 7: get rid of 7y²
Divide by $7$ : $7 y^{2}$ vanishes and $15 x^{2}$ is congruent to $x^{2}$ . The right side, $9$ , leaves $2$ . And $3^{2} = 9$ leaves exactly $2$ : no contradiction.

$x^{2} \equiv 2 (mod 7) (e.g. x = 3)$
Mod 3: no good either
Mod 5: get rid of 15x²
Look up the remainders of 3y²
Conclusion

A good order for choosing a modulus: first try the coefficients (to make a term vanish), then the old friends of the exponent (for squares try $3, 4, 8$ ; for cubes $7, 9$ ; for fourth powers $5, 16$ ).

Practice

Exercise 1Basic

How many different remainders can a perfect square leave on division by $8$ ?

Exercise 2Advanced

The equation $x^{2} - 5 y^{2} = 3$ has no integer solutions. Of the four moduli $3, 4, 5, 8$ , only one gives a contradiction. Which one?

Exercise 3Challenge

How many different remainders can a fourth power $n^{4}$ leave on division by $16$ ? Once you know, use it to show that $x^{4} + y^{4} + z^{4} = 2024$ has no integer solutions.

In one sentence

Stop 1 · Congruences (Vol. 6)

Example: is there a perfect square among 11, 111, 1111, …?

Stop 2 · Residue systems (Vol. 6)

Example: does x³ + y³ = 2020 have integer solutions?

Stop 3 · Perfect squares (Vol. 6)

Example: does m² − 3n² = 2 have integer solutions?

Stop 4 · Diophantine equations (Vol. 6)

Example: does 15x² − 7y² = 9 have integer solutions?

Practice

Mistake Museum · Exhibits from this stop

No contradiction, so it must have a solution

Cancelling in a congruence without thinking

Stops on this line