You are halfway through a problem. Both sides of your congruence happen to share a factor — say, a 2 or a 5 or a 6 — and the instinct that has served you since primary school kicks in: cancel it. Your pen is already moving.
Stop. Just for two seconds.
Before you cancel a factor a from both sides of a congruence mod n, the only question that matters is: what is \gcd(a, n)? If it is 1, you are free to cancel. If it is anything greater than 1, naive cancellation will produce a false statement — or worse, a statement that sometimes happens to be true and trains the habit that eventually costs you a problem on a JEE paper or a step in a proof.
This article is not about the theorem — the rule and its proof are here. This article is about building the mental reflex: before you cancel, check.
The two-second reflex
Whenever you see both sides of a congruence sharing a factor a, say
run this silent checklist before your pen moves:
- What is \gcd(a, n)? Compute it — Euclidean algorithm in your head, or just stare.
- If the gcd is 1: cancel. The modulus n stays the same.
- If the gcd is g > 1: do not cancel at the original modulus. You may still cancel a, but the modulus shrinks to n / g.
That is the whole ritual. It costs you two seconds and it prevents the single most common bug in modular arithmetic.
Watch the reflex in action
Case A — cancellation is safe. You are staring at
True? 20 - 6 = 14, divisible by 7. Yes. Both sides share a factor of 2. Before cancelling, you check: \gcd(2, 7) = 1. The gcd is 1, so cancellation is legal at mod 7:
and indeed 10 - 3 = 7. ✓ The reflex said "go", and the answer held up.
Case B — cancellation is a trap. Now look at
True? 10 - 6 = 4, divisible by 4. Yes. Both sides share a factor of 2. Your fingers want to write 3 \equiv 5 \pmod 4. But the reflex fires first: \gcd(2, 4) = 2, not 1. Alarm bell. Cancellation at mod 4 is illegal. If you had gone ahead, you would have written 3 \equiv 5 \pmod 4, which demands 4 \mid 2. That is false. You would have carried a false statement forward into the rest of the problem.
What do you do instead? You cancel the 2, but you also divide the modulus by g = 2:
and 5 - 3 = 2, which 2 divides. ✓ The modulus shrank. That is the correct simplification.
Same-looking move, totally different verdict, and the only thing that distinguished them was the two-second gcd check.
The decision flowchart
Commit this picture to memory. Every time your pen wants to strike out a common factor, the picture should flash up. Two branches, one gate.
Why this reflex saves you
Three real failure modes it blocks:
1. Off-by-residue errors in linear congruences. Consider 6x \equiv 12 \pmod{18}. Without the reflex, you "cancel the 6" and write x \equiv 2 \pmod{18} — one solution. Wrong: there are actually six (x = 2, 5, 8, 11, 14, 17). The reflex catches this before the exam does: \gcd(6, 18) = 6 \ne 1, so the modulus must shrink to 18/6 = 3, giving x \equiv 2 \pmod 3 — which correctly describes all six residues.
2. False claims in proofs. In a proof you write ka \equiv kb \pmod n and then — to tidy up — "cancel the k" and write a \equiv b \pmod n. If \gcd(k, n) > 1, this is simply not a valid step; the next line of your proof sits on sand. Marker bugs of this shape are especially nasty because the conclusion sometimes happens to be true, so the proof looks fine until a counterexample surfaces.
3. Losing solutions. Because naive cancellation often collapses a congruence with multiple solutions into one with fewer, you silently drop the extras. In RMO and olympiad number theory, "find all x such that …" problems punish this — full marks require the full solution set.
The smaller habit behind the habit
There is a deeper version of this reflex that applies beyond cancellation: before you do any algebraic move in modular arithmetic, ask whether the move depends on invertibility. Multiplication, addition, subtraction — all fine. They are defined for every residue. Division, cancellation, "taking a reciprocal", "dividing both sides by a" — these all depend on a being invertible mod n, and that happens exactly when \gcd(a, n) = 1.
The gcd check is the low-cost way to verify invertibility in your head, right at the moment your pen is about to commit the move. Build it into your hand the way you built in "check the sign of the discriminant" before applying the quadratic formula. Two seconds, every time.
The one sentence to carry
Before cancelling a from both sides of \;\cdot\; \equiv \;\cdot\; \pmod n, glance at \gcd(a, n). If it is 1, go. If it is g > 1, cancel but shrink the modulus to n/g.
That is the habit. Drill it until it fires before your pen does, and an entire family of modular-arithmetic bugs disappears from your work.
Related: Modular Arithmetic · To Divide Both Sides of a Congruence, the Divisor Must Be Coprime to the Modulus · When Does a Multiplicative Inverse Exist Mod n?