---
tag: 09RDZZGJZ9
kind: statement
role: proposition
name: Cancellation in congruences
msc: [11A07]
uses: [0TPW25CBN6, 02WF878BH1, 03BAREW1Z5]
sources:
  - url: https://en.wikipedia.org/wiki/Modular_arithmetic
    locator: Basic properties
---

## Statement

Let $n$ be a positive integer, and let $a$, $b$ and $c$ be integers. Let $d = \gcd(c, n)$.
If $c a \equiv c b \pmod n$, then $a \equiv b \pmod{n / d}$.

## Remarks

In particular, if $c$ and $n$ are [[coprime|0GFKP8F8AG]], then $c a \equiv c b \pmod n$ implies $a \equiv b \pmod n$.
The modulus can become smaller. For example, $2 \cdot 1 \equiv 2 \cdot 4 \pmod 6$, but $1 \not\equiv 4 \pmod 6$. Here $d = 2$, and indeed $1 \equiv 4 \pmod 3$.
The proof: $n \mid c (a - b)$ gives $\frac{n}{d} \mid \frac{c}{d} (a - b)$. Since $n / d$ and $c / d$ are coprime, the [[generalized Euclid's lemma|03BAREW1Z5]] gives $\frac{n}{d} \mid a - b$.

## Explanations

### L1 human

You can divide both sides of a congruence by a number that has no common factor with the modulus.
If the number shares a factor with the modulus, you must also divide the modulus by that common factor.