General Solution of the Chinese Remainder Problem by Daniel Reeves

The Chinese Remainder Problem:  When an unknown quantity is divided by m1, the remainder is r1; when divided by m2, the remainder is r2; etc, for n m's and r's.  Find the smallest positive value for the unknown quantity.
 
Given is the following information about x (the unknown quantity):
 By determining any of the q's (for quotient) we can calculate x, so we rewrite the above equations without x as follows:
Next, rewrite each of these equations in the usual diophantine form (s a + t b = n):
We now seek a function that, for the ith equation above, gives a value for q1 in terms of m1, m2, r1, r2.
By adapting the Euclidean Algorithm for GCD (gcd(a,b)= {a if b=0 and gcd(b,a mod b) otherwise}), we can express gcd(a,b) as a linear combination of a and b.  (In fact, only multiples of the gcd can be expressed as such a linear combination.)  So by applying that algorithm with m1 and mi we can multiply the resulting linear combination by (ri-r1)/gcd(m1,mi) to yield the appropriate solution to the ith diophantine equation above.  Note that (ri-r1)/gcd(m1,mi) is indeed an integer since ri-r1 = x-miqi-x+m1q1 = m1q1-miqi.
Following is a function that does this and returns the coefficient for the first parameter:
Using this function, we can write n-1 equations for q1 as follows:
where si = dio(m1, -mi, ri-r1) for i from 2 to n and the ki's are integers.
But notice that finding q1 from these equations is precisely the original problem with 1 fewer equation.  So we can apply the same procedure recursively until the problem is reduced to a single equation of the form b k + s = x.  For this equation, the simplest solution can be obtained by letting k=0, yielding x=s.  Thus a base case is established.
Following is a function that implements the recursive procedure above:
This may not yield a positive result; however, note that any value that satisfies the initial constraints can be increased or decreased by the least common multiple of the mi's without violating the constraints.  This fact enables us to convert the result of the above function to the least positive value.  So the smallest positive value for the unknown quantity is:
and all possible solutions are of the form
 
For example...