0
$\begingroup$

For example, if two given linear congruences have $m_1$ and $m_2$ not coprime, how to use CRT to show that there is no solution?

Should the solution start with assume there exists a solution then prove the contradiction?

$\endgroup$

2 Answers 2

1
$\begingroup$

Congruences also hold modulo any divisor of the modulus. Hence, given two linear congruences $$\begin{align*} x\equiv a_1 \mod m_1 \\ x\equiv a_2 \mod m_2 \end{align*}$$ it is also true that $$\begin{align*} x\equiv a_1 \mod (m_1,m_2) \\ x\equiv a_2 \mod (m_1,m_2) \end{align*}$$ It follows that, if $a_1\not\equiv a_2 \pmod{(m_1,m_2)}$, you have an obvious contradiction to the existence of any solution.

Remark: It is not difficult to prove that the converse holds, too. That is, if the above condition is satisfied, then there is a solution to this system.

$\endgroup$
0
$\begingroup$

Suppose you are given

\begin{align} x &\equiv a_1 \mod{m_1} \\ x &\equiv a_2 \mod{m_2} \end{align}

Let $g = \gcd(m_1,m_2)$ and suppose

\begin{align} m_1 &= g \ n_1 \\ m_2 &= g \ n_2 \end{align}

It follows that $a_1 \equiv a_2 \pmod g$

If this is true, then you can write

\begin{align} x &\equiv a_1 \mod{g} \\ x &\equiv a_1 \mod{n_1} \\ x &\equiv a_2 \mod{n_2} \end{align}

where $n_1, n_2,$ and $g$ are all pairwise prime. So a solution can be found.

If $a_1 \not \equiv a_2 \pmod g$, then there is no solution.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .