Code to solve simultaneous modular equations?

Here the symbol = is used to mean "is congruent to"

If

(1) n = a mod j
(2) n = b mod k

Then

(3) n = c mod l

Basically, given the first two 开发者_StackOverflowequations, find the third. For my purposes, I know in advance that a solution exists.

I would like some code in C or C++ to do this for me, or a link to a library or something that I can use in a C/C++ project. Thanks.

If a, b, j, and k are given, l = jk, and gcd(j,k) = 1, then c can be found using the Chinese Remainder Theorem. (If j and k have a nontrivial GCD, the solution c may or may not exist.)

A library to represent infinite arithmetic sequences would be useful here, but I don't personally know any. Regardless, here is a brute force solution that basically generates possibilities for n from each given modular equation and finds the intersection. It finds the lowest value of n by "leap-frogging" (pseudo-code):

value_left := a
value_right := b

while value_left != value_right:
    if value_left < value_right:
        value_left := value_left + j
    else:
        value_right := value_right + k
    end if
end while loop

return value_left % l // as in "leggo-mah-eggo!"

Let me know if you would like actual C code, although the translation should be fairly straightforward.