Given ac congruent to bc modulo n, when may you cancel c and conclude that a is congruent to b modulo n?

## 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.