Chinese Remainder Theorem Haskell

Question

I need to write a function or functions in Haskell that can solve the Chinese Remainder Theorem. It needs to be created with the following definition:

crt :: [(Integer, Integer)] -> (Integer, Integer)

That the answer looks like

>crt [(2,7), (0,3), (1,5)]
(51, 105)

I think I have the overall idea, I just don't have the knowledge to write it. I know that the crt function must be recursive. I have created a helper function to split the list of tuples into a tuple of two lists:

crtSplit xs = (map fst xs, product(map snd xs))

Which, in this example, gives me:

([2,0,1],105)

I think what I need to do know is create a list for each of the elements in the first list. How would I begin to do this?

Answer 1

Chinese remainder theorem has an algebraic solution, based on the fact that x = r1 % m1 and x = r2 % m2 can be reduced to one modular equation if m1 and m2 are coprime.

To do so you need to know what modular inverse is and how it can efficiently be calculated using extended Euclidean algorithm.

If you put these pieces together, you can solve Chinese remainder theorem with a right fold:

crt :: (Integral a, Foldable t) => t (a, a) -> (a, a)
crt = foldr go (0, 1)
    where
    go (r1, m1) (r2, m2) = (r `mod` m, m)
        where
        r = r2 + m2 * (r1 - r2) * (m2 `inv` m1)
        m = m2 * m1

    -- Modular Inverse
    a `inv` m = let (_, i, _) = gcd a m in i `mod` m

    -- Extended Euclidean Algorithm
    gcd 0 b = (b, 0, 1)
    gcd a b = (g, t - (b `div` a) * s, s)
        where (g, s, t) = gcd (b `mod` a) a

then:

\> crt [(2,7), (0,3), (1,5)]
(51,105)
\> crt [(2,3), (3,4), (1,5)]  -- wiki example
(11,60)

Answer 2

Without going into algebra, you can also solve this with brute force. Perhaps that's what you've been asked to do.

For your example, create a list for each mod independent of the other two (upper bound will be least common multiple of the mod, assuming they are co-prime as a precondition, product, i.e. 105). These three list should have one common element which will satisfy all constraints.

m3 = [3,6,9,12,15,...,105]
m5 = [6,11,16,21,...,101]
m7 = [9,16,23,30,...,100]

you can use Data.Set to find the intersection of these lists. Now, extend this logic to n number of terms using recursion or fold.

Update Perhaps an easier approach is defining a filter to create a sequence with a fixed remainder for a modulus and repeatedly apply for the given pairs

Prelude> let rm (r,m) = filter (\x -> x `mod` m == r)       

verify that it works,

Prelude> take 10 $ rm (1,5) [1..]                                               
[1,6,11,16,21,26,31,36,41,46]

now, for the given example use it repeatedly,

Prelude> take 3 $ rm (1,5) $ rm (0,3) $ rm (2,7) [1..]        
[51,156,261]

of course we just need the first element, change to head instead

Prelude> head $ rm (1,5) $ rm (0,3) $ rm (2,7) [1..]       
51

which we can generalize with fold

Prelude> head $ foldr rm [1..] [(1,5),(0,3),(2,7)]                            
51