1

How come $$4x \equiv 4 \pmod 8 \Longrightarrow x \equiv 1 \pmod 2$$

Also, is there more than one solution to the Chinese Remainder Theorem? I keep getting different answers on e-calculators.

Michael Hardy
  • 1
Don Larynx
  • 4,703
  • 1
    I'm sure the CRT has more than one solution...however if you mean "are there $2$ or more solutions to simultaneous congruences with coprime moduli" then the answer is no. – fretty Sep 25 '13 at 22:37

1 Answers1

3

$4x \equiv 4 \pmod{8} \Leftrightarrow \frac{4x-4}{8} \in \mathbb{Z}$

and since $\frac{4x-4}{8} = \frac{x-1}{2}$, we have

$\frac{4x-4}{8} \in \mathbb{Z} \Leftrightarrow \frac{x-1}{2} \in \mathbb{Z} \Leftrightarrow x \equiv 1 \pmod{2}$

For the second part of your question, make sure that your moduli are coprime.

Dennis Meng
  • 1,397
  • If there are $m_i, m_j$ not coprime, I think you're still okay if $a_i \equiv a_j \pmod{gcd(m_i, m_j)}$, but I'm not 100% sure. – Dennis Meng Sep 25 '13 at 22:44