In algebra, if 2x = 2y, you divide both sides by 2 and conclude x = y. The move is so automatic you stop thinking about it. So when you see a congruence like

6 \equiv 10 \pmod{4},

you reach for the same move — divide both sides by 2 — and write

3 \equiv 5 \pmod{4}.

Check: 3 - 5 = -2, and 4 \nmid 2. The "simplified" statement is false, even though the original one (6 - 10 = -4, and 4 \mid 4) is correct. You lost a true statement by dividing, and you will lose marks on exams the same way. The fix is to understand why division sometimes works in modular arithmetic and sometimes does not.

The rule, stated cleanly

Cancellation in a congruence

From ac \equiv bc \pmod{n}, you can conclude a \equiv b \pmod{n} only when \gcd(c, n) = 1.

If \gcd(c, n) = d > 1, you can only conclude a \equiv b \pmod{n / d}.

So "divide by c" is really "divide by c, and also divide the modulus by \gcd(c, n)." The extra step is easy to forget, which is where the errors come from.

Back to the broken example

6 \equiv 10 \pmod{4}. You want to divide by c = 2. Compute \gcd(2, 4) = 2. The rule says you can cancel, but the modulus shrinks:

3 \equiv 5 \pmod{4 / 2} \;=\; 3 \equiv 5 \pmod{2}.

Check: 3 - 5 = -2, and 2 \mid 2. ✓

The correct division ends in mod 2, not mod 4. The statement "3 \equiv 5 \pmod 4" was wrong because it kept the old modulus after shrinking the sides.

Why: n \mid c(a - b) does not imply n \mid (a - b). It only forces n / \gcd(c, n) to divide a - b, because the factors c shares with n get absorbed into the product. Those shared factors are the ones that fall out of the modulus when you cancel.

When division works without any adjustment

When \gcd(c, n) = 1 — the number you are dividing by is coprime to the modulus — the shrinking factor is 1, so the modulus stays the same. You can divide by c and keep the same modulus, exactly like ordinary algebra.

Example: 15 \equiv 9 \pmod{6}? Check: 15 - 9 = 6, and 6 \mid 6. ✓ Divide by 3. Compute \gcd(3, 6) = 3 \neq 1, so the modulus should shrink to 6/3 = 2. Give the right result: 5 \equiv 3 \pmod{2}, i.e. 5 - 3 = 2 is divisible by 2. ✓

Contrast with dividing 10 \equiv 4 \pmod{6} by 2. \gcd(2, 6) = 2, modulus shrinks to 3: 5 \equiv 2 \pmod{3}, i.e. 5 - 2 = 3 is divisible by 3. ✓ If you forgot the shrinking and wrote 5 \equiv 2 \pmod{6}, you would get the wrong answer (5 - 2 = 3, and 6 \nmid 3).

Why the rule makes sense

Unpack the hypothesis ac \equiv bc \pmod{n}. By definition, n \mid (ac - bc) = c(a - b).

So n divides the product c(a - b). You want to conclude n divides (a - b) alone. That is a jump — n might "distribute its divisors" between c and (a - b).

Which factors cancel versus which stayTwo boxes side by side. The left box shows the hypothesis n divides c times a minus b, with n equal to six and c equal to two. The right box shows a bar for six split into a factor of two that matches c and can be absorbed, and a remaining factor of three that must be absorbed by a minus b. An arrow pulls the shared factor of two out of the modulus, leaving modulus three. hypothesis 6 | 2(a − b) n = 6, c = 2 share gcd = 2 conclusion 3 | (a − b) modulus = 6 / 2 = 3 shared factor moved out the gcd is absorbed into c and leaves the modulus
Cancelling $c = 2$ from a congruence mod $6$. The shared factor $\gcd(2, 6) = 2$ leaves the modulus and is absorbed by $c$, so the new modulus is $6 / 2 = 3$. Only coprime cancellations preserve the modulus.

The way out: modular inverses

When \gcd(c, n) = 1, there is a cleaner way to "divide": multiply by the modular inverse c^{-1} \pmod{n}. From ac \equiv bc \pmod{n}, multiplying both sides by c^{-1} gives a \equiv b \pmod{n}. This is exactly what the cancellation rule above says in different language — the inverse exists precisely when \gcd(c, n) = 1, which is the same condition.

When the gcd is not 1, the inverse does not exist and the "multiply by inverse" rescue fails. That is the mathematical reason the cancellation trick breaks: there is no number to multiply by.

The drill

Any time you see yourself about to divide both sides of a congruence, run this three-step check.

  1. What is the modulus n?
  2. What is \gcd(c, n) where c is the number you are dividing by?
  3. If \gcd(c, n) = 1, divide safely; modulus stays the same. If \gcd(c, n) = d > 1, divide both sides and shrink the modulus to n / d.

Forgetting step 3 is the single most common mistake in modular arithmetic exam questions. The shrinking happens even when the division looks obviously fine numerically — as in the 6 \equiv 10 \pmod{4} example, where "divide by 2" is arithmetically painless but modularly illegal without the shrink.

Solve $6x \equiv 9 \pmod{15}$

Naive move: divide both sides by 3. \gcd(3, 15) = 3, so the modulus shrinks to 15 / 3 = 5:

2x \equiv 3 \pmod{5}.

Now \gcd(2, 5) = 1, so you can cancel 2 cleanly by multiplying by 2^{-1} \equiv 3 \pmod{5}:

x \equiv 3 \cdot 3 = 9 \equiv 4 \pmod{5}.

So the solution set modulo 15 is \{4, 9, 14\} — three residues, one for each lift of x \equiv 4 \pmod 5 back to mod 15.

Check x = 4: 6 \cdot 4 = 24 \equiv 9 \pmod{15}. ✓

If you had kept the modulus at 15 after the first division, you would have solved 2x \equiv 3 \pmod{15}, which is a different equation and gives only one residue instead of three. The modulus shrinkage is doing real work here: it is the reason the original equation has three solutions rather than one.

The short version

"Divide both sides" in modular arithmetic is really "divide both sides, and simultaneously shrink the modulus by the gcd." Only when the gcd is 1 do the two halves of that rule simplify to plain cancellation. Any other time, you are changing the modulus — and forgetting that is why your answer disagrees with the answer key.

Related: Modular Arithmetic · Modular Inverse Finder · Congruence Mod mn: Only When gcd = 1 · Number Theory Basics