How can I get the smallest possible answer with the Chinese Remainder Theorem?

Question

I've written some code that takes two integer arrays (one of moduli and one of remainders) and returns a number that solves this set of congruences. It's working, but it's not giving me the smallest possible answer, and I'm not quite sure how to achieve this.

I followed what was written here to write my code. The code looks like this:

def crt(m: Array[Int], r: Array[Int]): Int = {
    assert(m.length == r.length)
    for (a <- m; b <- m if b != a) assert(coprime(a, b))
    for (a <- m) assert(coprime(m.product / a, a))
    val parts = for (i <- 0 until m.length) yield {
        r(i) * modinv(m.product / m(i), m(i)) * (m.product / m(i))
    }
    parts.sum
}

For example, crt([3,5,7], [1,3,5]) returns 157, which isn't incorrect, but the lowest possible (and thus the "best" answer) is 52. I don't know what I'm doing wrong or what I could do to change this, and whether or not it's the algorithm over at MathWorld or a fault in my implementation.

Answer 1

If $M$ is the least common multiple of the moduli (which, if they are coprime, is their product), then the solution $x$ is unique mod $M$. So computing $x \bmod M$ will give you the smallest positive solution.