Solve system of congruences

106 Views Asked by At

I see that using CRT one can solve systems of the form:

\begin{cases} x \equiv a \pmod b\\ cx \equiv q \pmod w \end{cases}

but how would you solve a system of the form:

\begin{cases} x \equiv a \pmod b\\ x \equiv q \pmod c\\ x \equiv w \pmod d \end{cases}

where 'x' is always the same, and all other variables change? The idea is to send b, c, d, a, q, w over the wire and recover x.

1

There are 1 best solutions below

2
On BEST ANSWER

Use the CRT repeatedly. First solve the system for the first two equations and that should yield another congruence relation. Then solve the system of the new congruence relation and the third one.

It's obvious that no solutions are lost in the process, as CRT gives us all the solution that satisfy the first two equations and obviously the solutions of the initial system of 3 congruence relations is a subset of this set.