Chinese remainder theorem unique solution

891 Views Asked by At

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)

1

There are 1 best solutions below

0
On

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.