Common Factor Cancelling in Congruence

Theorem

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

Let:

$a x \equiv b y \left({\bmod\, m}\right)$ and $a \equiv b \left({\bmod\, m}\right)$

where $a \equiv b \left({\bmod\, m}\right)$ denotes that $a$ is congruent modulo $m$ to $b$.

Then:

$x \equiv y \left({\bmod\, \dfrac m d}\right)$

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

Corollary

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

$x \equiv y \left({\bmod\, m}\right)$

Proof

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

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

$\exists a' \in \Z: a a' \equiv d \left({\bmod\, m}\right)$

Hence:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle a \equiv b\)	\(\displaystyle \)	\(\displaystyle \pmod m\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle a a' \equiv b a' \equiv d\)	\(\displaystyle \)	\(\displaystyle \pmod m\)	\(\displaystyle \)	by definition of modulo multiplication

Then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle a x \equiv b y\)	\(\displaystyle \)	\(\displaystyle \pmod m\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle a a' x \equiv b a' y\)	\(\displaystyle \)	\(\displaystyle \pmod m\)	\(\displaystyle \)	by definition of modulo multiplication
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle d x \equiv d y\)	\(\displaystyle \)	\(\displaystyle \pmod m\)	\(\displaystyle \)	from above
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle x \equiv y\)	\(\displaystyle \)	\(\displaystyle \left({\bmod\, {\dfrac m d} }\right)\)	\(\displaystyle \)	Congruence by Product of Modulo

Hence the result.

$\blacksquare$

Proof of Corollary

If $a \perp m$ then $\gcd \left\{{a, m}\right\} = 1$ by definition.

The result is immediate.

$\blacksquare$

Sources

• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.4$: Law $\text{B}$, Exercises $20, \ 24$