1

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)

Thomas Andrews
  • 177,126
user1510863
  • 361
  • 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. – Thomas Andrews Jul 16 '14 at 00:36

1 Answers1

1

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.

Conifold
  • 11,756