Which modulus? The real trick in competition number theory

Every list of modular arithmetic tricks for competition number theory is really a list of one trick, applied nine times. Reduce both sides modulo something. If the two sides can never agree, the equation has no solutions and you are done in three lines.

The part nobody writes down is the something. A student who knows what a congruence is will still stare at a problem for ten minutes, try mod 2, get nothing, and move on. The technique was never the obstacle. Choosing the modulus was.

So this is about that choice, and it turns out to be almost mechanical.

The one decision

Pick the modulus that makes the thing you are staring at scarce.

A congruence argument works only when one side of the equation is forced into a small set of residues and the other side misses it. So the question is never "what should I reduce by", it is "what is the least flexible object here, and which modulus pins it down hardest".

Squares are the least flexible object in competition number theory, which is why they set the whole table.

The residue table worth memorising

There are six lines here and they will carry most of what you meet on an AMC or an olympiad paper.

• Squares mod 4 land in $\{0, 1\}$. Half the residues gone, from one line of work.
• Squares mod 8 land in $\{0, 1, 4\}$. Sharper still: five of the eight residues are impossible, which is why mod 8 is the standard escalation when mod 4 nearly worked.
• Squares mod 3 land in $\{0, 1\}$, and squares mod 5 land in $\{0, 1, 4\}$.
• Cubes mod 9 land in $\{0, 1, 8\}$. Cubes are wide open mod 4, so a cube problem that resists everything is usually a mod 9 problem.
• Fourth powers mod 16 land in $\{0, 1\}$, which is as narrow as this gets.
• Everything is flexible mod 2 except parity itself. Mod 2 answers parity questions and almost nothing else, and reaching for it first is the single most common reason a student concludes "modular arithmetic does not work here".

Read the modulus off the conclusion

Often you do not have to search at all, because the problem tells you which modulus it wants.

Prove that in any Pythagorean triple, $3$ divides one of the legs. The conclusion says three. So work mod 3. If $3$ divides neither $a$ nor $b$, then $a^2 \equiv b^2 \equiv 1$, so $a^2 + b^2 \equiv 2 \pmod 3$. But $c^2$ is a square, and squares mod $3$ are only $0$ or $1$. Contradiction, and the proof is finished before it started.

This generalises further than it looks. When a specific integer appears in the statement you are asked to prove, try that integer as the modulus first. It costs thirty seconds and it is right more often than any cleverer heuristic.

A modulus that says nothing is not a verdict

Take $x^2 - 5y^2 = 2$, which has no integer solutions.

Try mod 3: since $5 \equiv -1$, the left side is $x^2 + y^2$, and that can be $2$ mod 3, for instance at $x = y = 1$. Mod 3 permits the equation. It has told you nothing whatsoever.

Now try mod 4. Squares are $0$ or $1$, and $5y^2 \equiv y^2$, so the left side runs over $\{0, 1, 3\}$ and simply cannot be $2$. One line, done.

The mod 3 attempt was not a failure of the method and it was not evidence that no obstruction exists. It was one modulus out of the handful worth trying. Beginners treat a silent modulus as a verdict on the technique; the correct response is to walk down the table.

Split the modulus instead of hunting for a big one

If $p$ is a prime greater than $3$, then $24$ divides $p^2 - 1$. Nobody should try to reason mod 24 directly. Factor it: $24 = 8 \times 3$.

Mod 8: $p$ is odd, and the square of any odd number is $1 \bmod 8$. Mod 3: $p$ is not divisible by $3$, so $p^2 \equiv 1 \bmod 3$. Two easy statements about small moduli, then the Chinese remainder step, which here is just the observation that $8$ and $3$ are coprime and both divide $p^2 - 1$.

A composite modulus is always a conjunction of prime-power moduli. Never carry one around whole.

Digit facts are modular facts in disguise

The divisibility rules you learned at twelve are the base-10 expansion read mod something.

$10 \equiv 1 \pmod 9$, so $10^k \equiv 1$ for every $k$, so a number is congruent to its digit sum mod 9. That single line is the whole content of the rule for 9, and it is why the rule also works for 3.

$10 \equiv -1 \pmod{11}$, so $10^k \equiv (-1)^k$, and a number is congruent to its alternating digit sum mod 11. Same derivation, one sign different.

Any time a contest problem talks about digits, you have a base-10 expansion, and a base-10 expansion is a polynomial in $10$. Reducing that polynomial mod a small number is usually the first move.

Big exponents want the cycle, not the exponent

Powers repeat. That is the entire idea, and it converts "compute $7^{2026}$" into "compute $2026$ mod something small".

The last digit of $7^n$ cycles $7, 9, 3, 1$ with period $4$. Since $2026 \equiv 2 \pmod 4$, the last digit of $7^{2026}$ is $9$. No large arithmetic happened anywhere.

The same fact used negatively is more powerful. Powers of $2$ mod $7$ cycle $1, 2, 4$ and never take any other value, so an equation demanding $2^n \equiv 3 \pmod 7$ has no solutions at all, however large you let $n$ grow.

Fermat's little theorem is the industrial version: for prime $p$ not dividing $a$, $a^{p-1} \equiv 1 \pmod p$. It is why $n^5 - n$ is divisible by 30 falls apart so cleanly. Here $30 = 2 \times 3 \times 5$, and those are exactly the primes $p$ for which $p - 1$ divides $4$, so $n^5 \equiv n$ modulo each of them separately. Split the modulus, apply Fermat three times, recombine.

Where a congruence stops and descent begins

Prove that $x^2 + y^2 = 3z^2$ has no solutions in positive integers. Work mod 4. The right side is $0$ or $3$, the left is $0$, $1$ or $2$, so both sides must be $0$, which forces $x$, $y$ and $z$ to be even, every time.

That is not a contradiction. Nothing is impossible yet. But you have proved that any solution can be halved into a smaller solution, and a set of positive integers cannot descend forever, so no solution exists.

Keep the distinction. The congruence supplied the descent step; it did not supply the proof. When mod-something tells you "all the variables share a factor" rather than "these two sides disagree", you are not finished, you are one sentence into an infinite descent.

What modular arithmetic cannot do

Two limits, and both cost people marks.

1. A congruence proves impossibility, never existence. Showing that a solution is consistent mod 7, mod 11 and mod 13 is not the beginning of a construction. If the problem wants a solution, go and build one.
2. Exhausting your favourite moduli is not a proof that no obstruction exists. "I tried mod 4 and mod 9 and nothing happened" is a note in your margin, not a line in your write-up.

The second one matters under time pressure. Give the table two minutes. If nothing bites, the problem is probably not a congruence problem, and factoring, bounding or descent is where the answer lives.

What to practise

Not proofs. Take twenty number theory statements and, for each, write one line only: which modulus, and what becomes scarce under it. You will get through twenty in the time one full solution takes, and modulus-selection is the part you are actually short of.

Lemma teaches this as a named technique rather than as a bag of tricks. The modular thinking page has the residue facts, the rule for choosing a modulus, and where it sits in the levels. The problem archive carries the number theory problems above in full, with difficulty and expected time on each. And the daily problem posts a new one every morning in three tiers, no account needed, which is a cheap way to keep the table warm between sessions.