Discrete Mathematics - Congruence

Question

Prove that there does not exist $n \in \Bbb N$; such that $n \equiv 2 \pmod 4$ and $n \equiv 4 \pmod 8$.

Answer 1

Write out what it means that $n\equiv 4\pmod 8$, and then try to divide that by $4$

Answer 2

$$n \equiv 4 \pmod 8$$

$$\implies n \equiv 0 \pmod 4$$

However:

$$n \equiv 2 \pmod 4$$

There are no solutions to:

$$n \equiv 0 \equiv 2 \pmod 4$$

Answer 3

If $n \equiv 4$ (mod 8) then we can express $n$ as $n = 8k + 4$. This means $n = 4(2k +1)$ which shows that $4 | n$. This means $n \equiv 0$ (mod 4) so it is impossible for a number to satisfy the two conguence equations you gave.

Answer 4

If such an $n$ exists, what would its prime factorization be? If $n \equiv 2 \pmod 4$, then $n = 2 \times p^\alpha q^\beta \ldots$, where $p, q,$ etc. are odd primes and $\alpha, \beta$, etc. are nonnegative integers. The prime $2$ must have the exponent $1$ (implicitly or explicitly), for any higher exponent would mean that $n \equiv 0$, not $2 \pmod 4$.

If $n \equiv 4 \pmod 8$, then $n = 2^2 \times p^\alpha q^\beta \ldots$

And if $n \equiv 8 \pmod{16}$, then $n = 2^3 \times p^\alpha q^\beta \ldots$

To generalize, if $n \equiv 2^k \pmod{2^{k + 1}}$, then the prime factorization of $n$ is $2^k \times p^\alpha q^\beta \ldots$

Thus, for $n$ to satisfy both $n \equiv 2^k \pmod{2^{k + 1}}$ and $n \equiv 2^{k + 1} \pmod{2^{k + 2}}$ would require $k = k + 1$, which is impossible in $\mathbb{N}$.