2
$\begingroup$

Is there a straightforward approach for solving the Chinese Remainder Theorem with three congruences?

$$x \equiv a \bmod A$$

$$x \equiv b \bmod B$$

$$x \equiv c \bmod C$$

Assuming all values are positive integers, not necessarily prime, but sometimes solutions do exist.

$\endgroup$
1
  • $\begingroup$ You should show that you have made an attempt at the question. Especially because this looks like homework. It helps people understand your level and also what exactly you are asking $\endgroup$ Jul 28, 2015 at 5:14

3 Answers 3

2
$\begingroup$

You solve the first two, then take that result and the remaining equation and you solve those two.

$\endgroup$
0
1
$\begingroup$

For example, suppose you want $$ \eqalign{ x &\equiv 2 \mod 3 \cr x &\equiv 5 \mod 20\cr x &\equiv 1 \mod 7\cr} $$ From the first two, using the Euclidean algorithm, you get $x \equiv 5 \mod 60$. Then from this and the last equation, again using the Euclidean algorithm, $x \equiv 365 \mod 420$.

EDIT: For an example without a "clean inverse", by which I supppose you mean the moduli are not all coprime:

$$ \eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr x &\equiv 15 \mod 35\cr}$$ From the first two, the Euclidean algorithm gives you $x \equiv 50 \mod 105$. Now $105$ is already divisible by $35$, and $50 \equiv 15 \mod 35$, so they are compatible: the final result is $x \equiv 50 \mod 105$.

EDIT: What I mean by applying the Euclidean algorithm is this. Consider the first two equations of the last set: $x \equiv 5 \mod 15$, $x \equiv 8 \mod 21$. Write these as $$x = 5 + 15 y = 8 + 21 z$$ so that $$15 y = 3 + 21 z$$ Since $21 = 15 + 6$, this becomes $15 (y - z) = 3 + 6 z$, or (with $w = y - z$) $$15 w = 3 + 6 z$$ Then $15 = 2\times 6 + 3$, we get $$v = z - 2 w,\ 3 w = 3 + 6 v$$
Now $6$ is divisible by $3$, and we can write $$ w = 1 + 2 v $$ where $v$ is arbitrary. Now substitute back: $$ \eqalign{z &= v + 2 w = 2 + 5 v\cr x &= 8 + 21 z = 50 + 105 v\cr}$$ i.e. $x \equiv 50 \mod 105$.

$\endgroup$
2
  • $\begingroup$ Can you quickly mention what you mean by applying the egcd to the first two? As far as I know the egcd algorithm only takes two parameters and returns the gcd and a,b. $\endgroup$ Jul 29, 2015 at 1:01
  • $\begingroup$ Thanks for the update (although I admit I do not understand the updated answer still). I had actually made a new question about this answer here: math.stackexchange.com/questions/1377482/… $\endgroup$ Jul 29, 2015 at 2:09
0
$\begingroup$

For $x$ modulo A and modulo BC, solving $y_1 \times A + z_1 \times BC = 1$ by the extended Euclidean algorithm gives $ x_1 = z_1 \times BC$.

For $x$ modulo B and AC, solving $y_2 \times B + z_2 \times AC = 1$ gives $ x_2 = z_2 \times AC$ .

Finally, for $x$ modulo C and AB, solving $y_3 \times C + z_3 \times AB = 1$ gives $x_3 = z_3 \times AB$. A solution is therefore $x_1 + x_2 + x_3 = x$. All other solutions are congruent to $x$ modulo ABC.

$\endgroup$

You must log in to answer this question.

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