Congruence of Quotient

Theorem

Let $a, b \in \Z$ and $n \in \N$.

Let $a$ be congruent to $b$ modulo $n$, i.e. $a \equiv b \left({\bmod n}\right)$.

Let $d \in \Z: d > 0$ such that $d$ is a common divisor of $a, b$ and $n$.

Then:

$\displaystyle \frac a d \equiv \frac b d \left({\bmod \frac n d}\right)$

Proof

By definition of congruence modulo $n$:

$a = b + k n$

Dividing through by $d$ (which you can do because $d$ divides all three terms), we get:

$\displaystyle \frac a d = \frac b d + k \frac n d$

from where the result follows directly.

$\blacksquare$

Alternative Proof

From Congruence by Product of Modulo, we have that:

$\displaystyle \frac a d \equiv \frac b d \left({\bmod \frac n d}\right) \iff d \frac a d \equiv d \frac b d \left({\bmod d \frac n d}\right) \iff a \equiv b \left({\bmod n}\right)$

$\blacksquare$