# Congruence by Divisor of Modulus/Integer Modulus

## Theorem

Let $r, s \in \Z$ be integers.

Let $a, b \in \Z$ such that $a$ is congruent modulo $r s$ to $b$, that is:

$a \equiv b \pmod {r s}$

Then:

$a \equiv b \pmod r$

and:

$a \equiv b \pmod s$

## Proof

 $\displaystyle a$ $\equiv$ $\displaystyle b$ $\displaystyle \pmod {r s}$ $\displaystyle \implies \ \$ $\displaystyle a - b$ $=$ $\displaystyle q r s$ Definition of Congruence Modulo Integer $\displaystyle \implies \ \$ $\displaystyle a - b$ $=$ $\displaystyle \paren {q r} s$ $\, \displaystyle \land \,$ $\displaystyle a - b$ $=$ $\displaystyle \paren {q s} r$ $\displaystyle a$ $\equiv$ $\displaystyle b$ $\displaystyle \pmod r$ Definition of Congruence Modulo Integer: $q s$ is an integer $\, \displaystyle \land \,$ $\displaystyle a$ $\equiv$ $\displaystyle b$ $\displaystyle \pmod s$ Definition of Congruence Modulo Integer: $q r$ is an integer

$\blacksquare$