# System of congruences with non-pairwise coprime moduli

JoseKilo 04/29/2018. 0 answers, 17 views

I have a set of congruences

x ≡ a1 (mod n)
...
x ≡ ak (mod nk)

And I want to find x, this can be solved by the Chinese remainder theorem and related algorithms: https://en.wikipedia.org/wiki/Chinese_remainder_theorem

Some examples: https://rosettacode.org/wiki/Chinese_remainder_theorem

For this particular example:

x ≡ 1031 (mod 1473)
x ≡ 1141 (mod 1234)
x ≡ 50   (mod 1827)

All the algorithms that I have tried won't work, since the moduli are not pairwise coprime. However, 1024360583 is a valid solution:

1024360583 % 1473 == 1031
1024360583 % 1234 == 1141
1024360583 % 1827 == 50

What algorithm could find such a solution ?

I have also implemented Garner's Algorithm from the Handbook of Cryptography: it didn't solve that example.