Common Factor Cancelling in Congruence

Theorem

Let $a, b, x, y, m \in \Z$.

Let:

$a x \equiv b y \pmod m$ and $a \equiv b \pmod m$

where $a \equiv b \pmod m$ denotes that $a$ is congruent modulo $m$ to $b$.

Then:

$x \equiv y \pmod {m / d}$

where $d = \gcd \set {a, m}$.

Corollary 1

If $a$ is coprime to $m$, then:

$x \equiv y \pmod m$

Corollary 2

Let:

$a x \equiv a y \pmod m$

where $a \equiv b \pmod m$ denotes that $a$ is congruent modulo $m$ to $b$.

If $a$ is coprime to $m$, then:

$x \equiv y \pmod m$

Proof

We have that $d = \gcd \set {a, m}$.

From Law of Inverses (Modulo Arithmetic), we have:

$\exists a' \in \Z: a a' \equiv d \pmod m$

Hence:

 $\ds a$ $\equiv$ $\ds b$ $\ds \pmod m$ $\ds \leadsto \ \$ $\ds a a'$ $\equiv$ $\ds b a'$ $\ds \pmod m$ Definition of Modulo Multiplication $\ds$ $\equiv$ $\ds d$ $\ds \pmod m$

Then:

 $\ds a x$ $\equiv$ $\ds b y$ $\ds \pmod m$ $\ds \leadsto \ \$ $\ds a a' x$ $\equiv$ $\ds b a' y$ $\ds \pmod m$ Definition of Modulo Multiplication $\ds \leadsto \ \$ $\ds d x$ $\equiv$ $\ds d y$ $\ds \pmod m$ from above $\ds \leadsto \ \$ $\ds x$ $\equiv$ $\ds y$ $\ds \paren {\bmod {\dfrac m d} }$ Congruence by Product of Moduli

Hence the result.

$\blacksquare$

Examples

Congruence Cancelling: $6 \equiv 12 \pmod 2 \leadsto 2 \equiv 4 \pmod 2$

We have that:

$6 \equiv 12 \pmod 2$

and so:

$2 \equiv 4 \pmod 2$