Congruence by Divisor of Modulus/Integer Modulus

From ProofWiki
Jump to navigation Jump to search

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$


Sources