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

\(\ds a\)

\(\equiv\)

\(\ds b\)

\(\ds \pmod {r s}\)

\(\ds \leadsto \ \ \)

\(\ds a - b\)

\(=\)

\(\ds q r s\)

Definition of Congruence Modulo Integer

\(\ds \leadsto \ \ \)

\(\ds a - b\)

\(=\)

\(\ds \paren {q r} s\)

\(\, \ds \land \, \)

\(\ds a - b\)

\(=\)

\(\ds \paren {q s} r\)

\(\ds a\)

\(\equiv\)

\(\ds b\)

\(\ds \pmod r\)

Definition of Congruence Modulo Integer: $q s$ is an integer

\(\, \ds \land \, \)

\(\ds a\)

\(\equiv\)

\(\ds b\)

\(\ds \pmod s\)

Definition of Congruence Modulo Integer: $q r$ is an integer

$\blacksquare$

Sources

• 1965: J.A. Green: Sets and Groups ... (previous) ... (next): $\S 2.5$. Congruence of integers: Example $38$
• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $17$