1
$\begingroup$

If we have two linear congruence and we want to use CRT to combine them, we have to find the intersection of the solution sets of these two linear congruence, right? For example, if I want to combine $n$ congruent to $a_1 (\text{mod} \ m_1)$ and $n$ congruent to $a_2 (\text{mod} \ m_2)$, then I have to first find the intersection of $[a_1]$ and $[a_2]$, right?

$\endgroup$
5
  • 1
    $\begingroup$ We do have to find the intersection, sort of. But not first. Use the CRT machinery. $\endgroup$ Nov 12, 2013 at 4:24
  • $\begingroup$ I get it, thanks. BTW, how to close this question? $\endgroup$
    – Slavica
    Nov 12, 2013 at 4:28
  • 1
    $\begingroup$ I don't know. Do know that people do delete, sometimes when I am writing an answer. $\endgroup$ Nov 12, 2013 at 4:30
  • $\begingroup$ I will just leave this here. Anyway, thank you very much. $\endgroup$
    – Slavica
    Nov 12, 2013 at 4:32
  • $\begingroup$ You are welcome. $\endgroup$ Nov 12, 2013 at 4:33

1 Answer 1

0
$\begingroup$

If you set up each congruence as linear equations equal to each other, you'll get $a_1 + m_1 x = a_2 + m_2 y \implies m_1 x - m_2 y = a_2 - a _1$

And then you'll only have to solve the linear diophantine equation. So you'll have to show that $gcd(m_1, m_2) | (a_2 - a_1)$ for there to be a solution set.

In calculating the greatest common divisor with the Euclidean algorithm, we can walk back the calculation to find a solution to $m_1 x' - m_2 y' = gcd(m_1, m_2)$

If we let $ k ={a_2 - a_1 \over gcd(m_1, m_2)}$ then $(x, y) = (kx', ky')$

And then we can use $n = a_1 + m_1 x = a_2 + m_2 y$ to represent the resultant intersection

${n \over gcd(m_1, m_2)} (mod$ $lcm(m_1, m_2))$

$\endgroup$

You must log in to answer this question.

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