Given ac congruent to bc modulo n, when may you cancel c and conclude that a is congruent to b modulo n?
answer
- the shared factor is the trap
- a product can vanish without either factor
- gcd of factor and modulus
- coprime means cancel freely
- otherwise the modulus shrinks too
basics
~20 sOnly when c and n share no common factor, that is when their greatest common divisor is 1. Otherwise the honest conclusion is a congruent to b modulo n divided by that greatest common divisor, which is weaker.
solid answer
~50 sCancellation is the one schoolbook move that does not transfer. From `ac = bc (mod n)` all you know is that `n` divides `c(a - b)`, and `n` can be satisfied by the factor `c` rather than by `a - b`. If `gcd(c, n) = 1`, then `n` must divide `a - b` and cancelling is legitimate. If `g = gcd(c, n)` is bigger than 1, the correct statement is `a = b (mod n/g)` - the same congruence on a **shrunken modulus**. The standard counterexample: `2 * 3 = 6` and `2 * 8 = 16` are congruent modulo `10`, yet `3` and `8` are not congruent modulo `10`; with `g = 2` they are congruent modulo `5`, and indeed both leave remainder `3`. A prime modulus removes the trap entirely for any factor it does not divide.
go deeper
Remember the rule as a checkable condition: you may cancel a factor from both sides of a congruence only when that factor shares no divisor with the modulus.
Explain the mechanism - the modulus divides a product, and a composite modulus can be satisfied by the factor instead of by the difference, which is why coprimality is what repairs it.
Spot the move in review when it is disguised as a simplification, and say what it costs: the surviving claim lives on a smaller modulus and therefore accepts more values than the original check did.
Treat modulus choice as a design decision - a prime modulus buys cancellation for every non-vanishing factor and removes a whole class of subtle validation bugs before anyone can write one.
## Why the step is unsafe at all Addition, subtraction and multiplication are well defined on residue classes, so people reasonably assume the inverse moves are too. They are not. Unwinding `ac = bc (mod n)` gives exactly one fact: `n` divides `c(a - b)`. Divisibility of a **product** does not force divisibility of a chosen **factor**. The modulus can be satisfied by `c` alone, leaving `a - b` free to be anything. That is the whole failure in one sentence, and it is why the condition that repairs it is a statement about `c` and `n` rather than about `a` and `b`. ## The condition, stated in the direction it is used - **Safe:** if `gcd(c, n) = 1` then `ac = bc (mod n)` implies `a = b (mod n)`. Because `c` contributes none of the factors of `n`, every one of them must come from `a - b`. - **General:** let `g = gcd(c, n)`. Then `ac = bc (mod n)` implies `a = b (mod n/g)` - true always, and the strongest thing you may say. - **Not implied:** `a = b (mod n)` itself, whenever `g > 1`. Asserting it is over-claiming, not a rounding error. The general form follows in three steps. Write `n = g * n'` and `c = g * c'`, where `gcd(c', n') = 1` by construction. From `n | c(a - b)` we get `g n' | g c' (a - b)`, so `n' | c'(a - b)`, and since `c'` shares nothing with `n'`, `n' | (a - b)`. That is `a = b (mod n/g)`. ## A worked case to carry Take `n = 10` and `c = 2`: 1. `2 * 3 = 6` and `2 * 8 = 16`; both leave remainder `6` modulo `10`, so `2*3 = 2*8 (mod 10)`. 2. Naive cancellation would claim `3 = 8 (mod 10)`. False - the remainders are `3` and `8`. 3. The correct conclusion uses `g = gcd(2, 10) = 2`: `3 = 8 (mod 5)`. True - both leave remainder `3`. The modulus lost a factor of `2` in the cancellation, and that factor is exactly the information the shared divisor absorbed. ## Which moduli make the trap disappear | modulus | cancellable factors | what can still hide | |---|---|---| | a prime `p` | every `c` not divisible by `p` | only the degenerate case `c = 0 (mod p)` | | a prime power `p^k` | every `c` not divisible by `p` | factors carrying `p`, which shrink the modulus | | a general composite `n` | only `c` with `gcd(c, n) = 1` | every factor sharing a divisor with `n` | This is the structural reason prime moduli are preferred whenever residue arithmetic has to behave like ordinary arithmetic: modulo a prime there are **no zero divisors**, meaning no pair of non-zero classes multiplies to zero, so a product that vanishes forces one of its factors to vanish. Modulo a composite there are zero divisors - `2` and `5` modulo `10` are the smallest example, since `2 * 5 = 10` is congruent to `0` - and a vanishing product proves nothing about either factor. ## How the mistake shows up in practice It rarely appears as a literal division. It appears as a simplification: a validation rule that divides a weighted total and its target by a shared factor before comparing, a derivation that strikes the same coefficient from both sides of a congruence, a reduction of a scale factor to make two totals comparable. Each is the same move, and each silently widens the set of values accepted, because a congruence on the shrunken modulus `n/g` holds for `g` times as many residues as one on `n`. The practical discipline is short. Before cancelling anything from a congruence, compute the greatest common divisor of the factor and the modulus. If it is `1`, cancel freely. If it is not, either keep the factor in place or divide the modulus by the same amount and remember that you now have a weaker claim than the one you started with. Note that the weaker claim is still a genuine claim - the mistake is asserting the original modulus, not supposing that nothing at all survives.
- Why does a prime modulus make cancellation safe for every factor it does not divide?Modulo a prime `p`, any `c` that `p` does not divide has `gcd(c, p) = 1`, so the coprimality condition is automatic. Equivalently there are no zero divisors: a product congruent to zero forces one factor to be congruent to zero, so a vanishing difference must come from `a - b`.
- In 2*3 congruent to 2*8 modulo 10, what is the correct conclusion once the factor 2 is removed?`gcd(2, 10) = 2`, so the conclusion is `3 = 8 (mod 5)`, which is true because both leave remainder `3`. The stronger claim `3 = 8 (mod 10)` is false, and the gap between the two is exactly the factor absorbed by the shared divisor.
- Does a failed cancellation mean nothing at all can be said about a and b?No, and treating it that way discards a real fact. The congruence on the reduced modulus `n/g` always holds; it simply admits `g` times as many residues as a congruence on `n` would. It is a weaker constraint, not an absent one.
saying these in an interview costs you the question
- Cancelling a shared factor as if the congruence were ordinary integer equality
- Believing cancellation always works whenever the modulus is odd
- Keeping the original modulus after dividing both sides by a shared factor
- Blaming the mismatch on overflow or remainder sign rather than structure
- Claiming nothing follows at all once the factor shares a divisor with the modulus