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

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!

• Chinese Remainder
• Chinese Remainder Theorem (non-relatively prime moduli)
• Disgruntled Judge
• Astro
• Heliocentric
• Remainder Reminder
• DVD Screensaver