Congruence of Quotient

From ProofWiki
Jump to navigation Jump to search


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

Let $a$ be congruent to $b$ modulo $n$, i.e. $a \equiv b \pmod n$.

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


$\dfrac a d \equiv \dfrac b d \pmod {n / d}$

Proof 1

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:

$\dfrac a d = \dfrac b d + k \dfrac n d$

from which the result follows directly.


Proof 2

From Congruence by Product of Moduli, we have that:

$\dfrac a d \equiv \dfrac b d \pmod {n / d} \iff d \dfrac a d \equiv d \dfrac b d \pmod {n / d} \iff a \equiv b \pmod n$