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.

  • 1
    $\begingroup$ 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. $\endgroup$ – fretty Sep 25 '13 at 22:37

$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.

  • $\begingroup$ 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. $\endgroup$ – Dennis Meng Sep 25 '13 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.