0

The following system is given

$X \equiv a_1$ $mod$ $m_1$

$X \equiv a_2$ $mod$ $m_2$ such that $m_1, m_2 \in \mathbb{N} _{>1}$ and $m_1, m_2$ are not coprime.

For which $a_1, a_2 \in \mathbb{Z} $ exists a solution for the system?

I tried like this but I'm not sure how to solve it:

$k \cdot m_1+a_1=X= l \cdot m_2+a_2$ $\Rightarrow a_1=l \cdot m_2+a_2-k \cdot m_1$

Could you please help?

Thanks

John
  • 39

1 Answers1

1

Hint:

The condition is that $a_1\equiv a_2\mod \gcd(m_1,m_2)$.

Indeed, it is necessary: let's denote $d=\gcd(m_1, m_2)$ so that $m_1=dn_1$ and $m_2=dn_2$ for some coprime $n_1$ and $n_2$.

If you find an $x$ such that $x=a_1+km_1$ and $x=a_2+\ell m_2$, we have $a_1+km_1=a_2+\ell m_2$, so that $$a_1=a_2+\ell m_2-k m_1=a_2+ (\ell n_2-k n_1)d ,$$ which shows the congruence modulo $d$.

Conversely,one can show that if $a_1\equiv a_2\mod d$, the system of congruences has a solution.

Bernard
  • 175,478
  • So it means it's either $a_1 = a_2 \cdot gcd(m_1, m_2)$ Or $a_2 = a_1 \cdot gcd(m_1, m_2)$

    How could I proceed now? And where do I know from that it's $a_1 \equiv a_2$ $mod$ $gcd(m_1,m_2) $?

     – John Apr 24 '18 at 22:24
  • It doesn't mean that. It means that $a_1-a_2$ is divisible by $\gcd(m_1,m_2)$. I've added the reason why, necessarily $a_1\equiv a_2\mod\gcd(m_1,m_2)$. – Bernard Apr 24 '18 at 22:44