1
$\begingroup$

If I have two equations such that

$$X\equiv a \pmod b\\ X\equiv c \pmod d$$

I can use linear Diophantine Equations to find multiple solutions to X. Can I find multiple solutions using CRT.

what if I have a third equation
$$X\equiv e \pmod g$$

How do I find multiple possible solutions (note: I can find one solution using CRT)

$\endgroup$
1
  • $\begingroup$ Assuming $(b,d)=1$, you get a solution $X\pmod{bd}$ which is already an infinite set of solutions, and it includes all of the solutions. $\endgroup$ Jul 16, 2014 at 0:36

1 Answer 1

1
$\begingroup$

Assuming $b,d$ are coprime you can find all solutions using CRT, because according to it they are all congruent to each other modulo the product $bd$. In other words, if $s$ is one solution you know how to find every other one is of the form $s+t\,bd$ for some integer $t$. The same works for three or any number of coprime moduli.

If they are not coprime there may be no solutions at all, but if one $s$ exists then every other one is of the form $s+t\,\text{lcm}[b,d]$, where $\text{lcm}$ is the least common multiple, see Wikipedia.

$\endgroup$

You must log in to answer this question.

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