To Divide Both Sides of a Congruence, the Divisor Must Be Coprime to the Modulus

Here is a congruence that looks harmless:

14 \equiv 8 \pmod 6

Check: 14 - 8 = 6, and 6 \mid 6. True. Now try the move you would make on an ordinary equation — divide both sides by 2:

\text{"}\,7 \equiv 4 \pmod 6\,\text{"}

Check: 7 - 4 = 3, and 6 \nmid 3. False. You divided a true congruence by 2 and got a false one. This is the single most common error in modular arithmetic, and it happens because students carry over a rule from ordinary algebra that no longer holds.

The rule you were missing:

When dividing both sides of a \equiv b \pmod n by d, you must have \gcd(d, n) = 1.

If \gcd(d, n) \ne 1, the division is illegal — and your "simplified" congruence may be false. Worse, it may sometimes happen to be true, which trains bad habits. The only safe path is to always check the coprimality condition before dividing.

The exact rule

Theorem. If a \cdot d \equiv b \cdot d \pmod n and \gcd(d, n) = 1, then a \equiv b \pmod n.

Counter-theorem (the trap). If \gcd(d, n) = g > 1, the conclusion a \equiv b \pmod n may fail. The best you can say is a \equiv b \pmod{n/g}.

Watch the repair work on our broken example. We had 14 \equiv 8 \pmod 6, and we tried to divide by d = 2. Here \gcd(2, 6) = 2 = g, so the division is illegal mod 6. But you are allowed to divide if you also divide the modulus by g = 2: the correct conclusion is

7 \equiv 4 \pmod 3

And 7 - 4 = 3, which is divisible by 3. ✓ The modulus got smaller, not larger.

Why the coprime condition is necessary

Start from a \cdot d \equiv b \cdot d \pmod n, which means n \mid (a - b) \cdot d. You want to conclude n \mid (a - b).

If \gcd(d, n) = 1, then n and d share no prime factors. Whatever primes divide n must all appear in (a - b) to make n \mid (a - b) d work — so n \mid (a - b). The conclusion follows.

If \gcd(d, n) = g > 1, then some of the prime factors of n appear in d and may not appear in (a - b). The product (a - b) \cdot d is still divisible by n because d is "helping" — contributing some of the prime factors. Once you strip off d, the remaining (a - b) may no longer be divisible by the full n. You can only guarantee it is divisible by n / g — the part of n that d did not help with.

Why the "only by n/g" result: write d = g \cdot d' and n = g \cdot n' where \gcd(d', n') = 1. Then n \mid (a - b) d becomes g n' \mid (a - b) g d', which simplifies to n' \mid (a - b) d'. Since \gcd(d', n') = 1, now the coprime argument gives n' \mid (a - b), i.e. a \equiv b \pmod{n'} = \pmod{n/g}. The factor g that d contributed is lost from the modulus.

A gallery of traps

Trap 1. "Divide by 2 to simplify."

Statement: 4 \equiv 10 \pmod 6. True: 6 \mid -6. \gcd(2, 6) = 2 \ne 1. Dividing by 2 gives "2 \equiv 5 \pmod 6," which is false (6 \nmid -3). Correct: divide modulus too — 2 \equiv 5 \pmod 3, which is true (3 \mid -3).

Trap 2. "I multiplied by 3, let me divide by 3."

Statement: 3 \cdot 2 \equiv 3 \cdot 5 \pmod 9, i.e. 6 \equiv 15 \pmod 9. True: 9 \mid -9. \gcd(3, 9) = 3. Dividing by 3 gives "2 \equiv 5 \pmod 9," which is false (9 \nmid -3). Correct: divide modulus — 2 \equiv 5 \pmod 3, which is true.

Trap 3. Solving 6x \equiv 12 \pmod{18} by "dividing by 6."

Students write x \equiv 2 \pmod{18}. Wrong: x = 2 works, but so does x = 5 (check 6 \cdot 5 = 30 \equiv 12 \pmod{18} since 30 - 12 = 18), and x = 8, and x = 11, and x = 14, and x = 17. Six solutions mod 18, not one. The correct move is to divide through the whole equation including the modulus: \gcd(6, 18) = 6, so x \equiv 2 \pmod 3, which correctly gives six residues mod 18.

The safe workflow

Every time you want to divide both sides of a congruence by some factor d, run this three-step check.

Compute g = \gcd(d, n).
If g = 1: division is legal. The new congruence has the same modulus n.
If g > 1: division is still possible, but you must also divide the modulus: the new congruence lives mod n / g, not mod n.

If you skip step 1, you will occasionally get the right answer by luck and occasionally get a false statement. Over a three-hour JEE paper, that "occasionally false" will cost you marks.

Why equations do not have this problem

In ordinary equations over \mathbb{Z} or \mathbb{R}, dividing by a nonzero number is always legal because \mathbb{Z} and \mathbb{R} have no nontrivial "modulus" — there is no cyclic structure to break. Every nonzero real number has a multiplicative inverse in \mathbb{R}, so the cancellation law works unconditionally.

In modular arithmetic mod n, not every nonzero residue has a multiplicative inverse. Only those residues with \gcd(d, n) = 1 are invertible. When d is invertible, division is just multiplication by d^{-1}, which is fine. When d is not invertible (because \gcd(d, n) > 1), there is no number d^{-1} in \mathbb{Z}/n\mathbb{Z} to multiply by, so "dividing by d" is meaningless at that modulus — hence the need to shift to a smaller modulus where d becomes invertible.

One worked fix

Given $10x \equiv 6 \pmod{14}$, find all $x$ mod $14$.

Step 1. Compute g = \gcd(10, 14) = 2.

Step 2. Check that 2 \mid 6. Yes, so solutions exist. (If g \nmid b, there would be no solution at all.)

Step 3. Divide everything — left side, right side, AND modulus — by g = 2:

5x \equiv 3 \pmod 7

Now \gcd(5, 7) = 1, so we can divide this one by 5 (or equivalently, multiply by 5^{-1}). The inverse of 5 mod 7 is 3 (since 5 \times 3 = 15 \equiv 1 \pmod 7). Multiplying both sides by 3:

x \equiv 3 \cdot 3 = 9 \equiv 2 \pmod 7

Step 4. Lift back to mod 14. The original modulus was 14, and solutions mod 7 correspond to g = 2 residues mod 14. So x \equiv 2 \pmod 7 means x \in \{2, 9\} \pmod {14}.

Check:

10 \cdot 2 = 20 \equiv 6 \pmod{14}? 20 - 6 = 14. ✓
10 \cdot 9 = 90 \equiv 6 \pmod{14}? 90 - 6 = 84 = 14 \times 6. ✓

Both solutions work. If you had "divided by 10" in one step without shifting the modulus, you would have found only one solution and missed the other.

The one-line diagnostic

Before dividing a congruence by d, check \gcd(d, n). If it is 1, divide. If it is g > 1, divide both sides AND the modulus by g. Skipping this step is the single most common source of wrong answers in modular arithmetic problems on JEE, NTSE, and RMO.