Congruence by Divisor of Modulus

From ProofWiki
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:

\(\displaystyle a\) \(\equiv\) \(\displaystyle b\) \(\displaystyle \pmod z\)
\(\displaystyle \implies \ \ \) \(\displaystyle \exists k' \in \Z: a\) \(=\) \(\displaystyle b + k' z\) Definition of Congruence
\(\displaystyle \implies \ \ \) \(\displaystyle a\) \(=\) \(\displaystyle b + k' k m\)
\(\displaystyle a\) \(\equiv\) \(\displaystyle b\) \(\displaystyle \pmod m\) Definition of congruence: $k' k$ is an integer

$\blacksquare$


Sources