Chinese Remainder Theorem/Examples/n = 7 mod 12 so n = 3 mod 4

From ProofWiki
Jump to navigation Jump to search

Example of use of Chinese Remainder Theorem

Let $n \equiv 7 \pmod {12}$.

Then:

$x \equiv 3 \pmod 4$


Proof

By the Chinese Remainder Theorem:

$n \equiv 7 \pmod {12} \iff n \equiv 7 \pmod 3 \text { and } n \equiv 7 \pmod 4$

as $3$ and $4$ are coprime.


Thus given the hypothesis:

\(\displaystyle n\) \(\equiv\) \(\displaystyle 7\) \(\displaystyle \pmod {12}\)
\(\displaystyle \) \(\equiv\) \(\displaystyle 7\) \(\displaystyle \pmod 4\) Chinese Remainder Theorem
\(\displaystyle \) \(\equiv\) \(\displaystyle 3\) \(\displaystyle \pmod 4\)

$\blacksquare$


Sources