Congruence by Divisor of Modulus
Jump to navigation
Jump to search
Theorem
Let $z \in \R$ be a real number.
Let $a, b \in \R$ such that $a$ is congruent modulo $z$ to $b$, that is:
- $a \equiv b \pmod z$
Let $m \in \R$ such that $z$ is an integer multiple of $m$:
- $\exists k \in \Z: z = k m$
Then:
- $a \equiv b \pmod m$
Integer Modulus
When $z$ is an integer, and therefore a composite number such that $z = r s$, this result can be expressed as:
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
We are given that $\exists k \in \Z: z = k m$.
Thus:
\(\ds a\) | \(\equiv\) | \(\ds b\) | \(\ds \pmod z\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \exists k' \in \Z: \, \) | \(\ds a\) | \(=\) | \(\ds b + k' z\) | Definition of Congruence | |||||||||
\(\ds \leadsto \ \ \) | \(\ds a\) | \(=\) | \(\ds b + k' k m\) | |||||||||||
\(\ds a\) | \(\equiv\) | \(\ds b\) | \(\ds \pmod m\) | Definition of Congruence: $k' k$ is an integer |
$\blacksquare$
Sources
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): $\S 2.3$: Congruences: Theorem $1 \ \text{(iv)}$