Competitive Programming in Haskell: modular arithmetic, part 2

In my last post I wrote about modular exponentiation and egcd. In this post, I consider the problem of solving modular equivalences, building on code from the previous post.

Solving linear congruences

A linear congruence is a modular equivalence of the form

ax \equiv b \pmod m.

Let’s write a function to solve such equivalences for x. We want a pair of integers y and k such that x is a solution to ax \equiv b \pmod m if and only if x \equiv y \pmod k. This isn’t hard to write in the end, but takes a little bit of thought to do it properly.

First of all, if a and m are relatively prime (that is, \gcd(a,m) = 1) then we know from the last post that a has an inverse modulo m; multiplying both sides by a^{-1} yields the solution x \equiv a^{-1} b \pmod m.

OK, but what if \gcd(a,m) > 1? In this case there might not even be any solutions. For example, 2x \equiv 3 \pmod 4 has no solutions: any even number will be equivalent to 0 or 2 modulo 4, so there is no value of x such that double it will be equivalent to 3. On the other hand, 2x \equiv 2 \pmod 4 is OK: this will be true for any odd value of x, that is, x \equiv 1 \pmod 2. In fact, it is easy to see that any common divisor of a and m must also divide b in order to have any solutions. In case the GCD of a and m does divide b, we can simply divide through by the GCD (including dividing the modulus m!) and then solve the resulting equivalence.

-- solveMod a b m solves ax = b (mod m), returning a pair (y,k) (with
-- 0 <= y < k) such that x is a solution iff x = y (mod k).
solveMod :: Integer -> Integer -> Integer -> Maybe (Integer, Integer)
solveMod a b m
  | g == 1         = Just ((b * inverse m a) `mod` m, m)
  | b `mod` g == 0 = solveMod (a `div` g) (b `div` g) (m `div` g)
  | otherwise      = Nothing
  where
    g = gcd a m

Solving systems of congruences with CRT

In its most basic form, the Chinese remainder theorem (CRT) says that if we have a system of two modular equations

\begin{array}{rcl}x &\equiv& a \pmod m \\ x &\equiv& b \pmod n\end{array}

then as long as m and n are relatively prime, there is a unique solution for x modulo the product mn; that is, the system of two equations is equivalent to a single equation of the form

x \equiv c \pmod {mn}.

We first compute the Bézout coefficients u and v such that mu + nv = 1 using egcd, and then compute the solution as c = anv + bmu. Indeed,

c = anv + bmu = a(1 - mu) + bmu = a - amu + bmu = a + (b-a)mu

and hence c \equiv a \pmod m; similarly c \equiv b \pmod n.

However, this is not quite general enough: we want to still be able to say something useful even if \gcd(m,n) > 1. I won’t go through the whole proof, but it turns out that there is a solution if and only if a \equiv b \pmod {\gcd(m,n)}, and we can just divide everything through by g = \gcd(m,n), as we did for solving linear congruences. Here’s the code:

-- gcrt2 (a,n) (b,m) solves the pair of modular equations
--
--   x = a (mod n)
--   x = b (mod m)
--
-- It returns a pair (c, k) such that all solutions for x satisfy x =
-- c (mod k), that is, solutions are of the form x = kt + c for
-- integer t.
gcrt2 :: (Integer, Integer) -> (Integer, Integer) -> Maybe (Integer, Integer)
gcrt2 (a,n) (b,m)
  | a `mod` g == b `mod` g = Just (((a*v*m + b*u*n) `div` g) `mod` k, k)
  | otherwise              = Nothing
  where
    (g,u,v) = egcd n m
    k = (m*n) `div` g

From here we can bootstrap ourselves into solving systems of more than two equations, by iteratively combining two equations into one.

-- gcrt solves a system of modular equations.  Each equation x = a
-- (mod n) is given as a pair (a,n).  Returns a pair (z, k) such that
-- solutions for x satisfy x = z (mod k), that is, solutions are of
-- the form x = kt + z for integer t.
gcrt :: [(Integer, Integer)] -> Maybe (Integer, Integer)
gcrt []         = Nothing
gcrt [e]        = Just e
gcrt (e1:e2:es) = gcrt2 e1 e2 >>= \e -> gcrt (e:es)

Practice problems

And here are a bunch of problems for you to practice!

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in haskell and tagged , , , , . Bookmark the permalink.

1 Response to Competitive Programming in Haskell: modular arithmetic, part 2

  1. Pingback: Resumen de lecturas compartidas del 1 al 7 de marzo de 2020 | Vestigium

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.