Welcome to the modulo world

Modulo (aka mod) is an important operation in number theory. Given a positive integer $m$ as modulo, an arbitrary integer is mapped into a number in $\mathcal{M} = \{0,1,...m-1\}$ via modulo operation, a -> a % m $\in \mathcal{M}$. More importantly, common arithmetic operations like addition, subtraction, multiplication and division on integer numbers are all well-defined with results in $\mathcal{M}$, e.g.,

$(a \pm b) \% m = a \% m + b \% m$
$(a \times b) \% m = (a \% m) \times (b \% m)$
$(a \div b) \% m = (a \times b^{-1}) \% m$ (when $b^{-1}$ modulo $m$ exists. More on this below.)

Two integer $a, b$ are said equivalent in modulo $m$, $a \equiv b \pmod m$ iff a-b % m = 0, i.e., $m$ divides $a-b$.

Built on the basic operations, we can consider more interesting problems such as solving linear equations in modulo world, find $x \in \mathbb{Z}$ such that $ax \equiv b \pmod m$ for given $a, b \in \mathbb{Z}$.

A little GCD digression

Greatest common divisor (aka, GCD) is another fundamental thing in number theory. As its name clearly says, $\gcd(a, b)$ is the greatest integer divides both two integers $a, b$. A simple version of the Euclidean algorithm to find $\gcd(a, b)$ is as follow:

# Assume a, b > 0.
def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a%b)

While simple, this algorithm is very efficient O(log max(a,b)). Can you see why?

An extended version of the algorithm above can also find two integers $x, y$ such that $ax + by = gcd(a,b)$ along with the gcd itself.

def extgcd(a, b):
  # Returns gcd(a,b), x and y in that order.
  if b == 0:
    return a, 1, 0
  d, u, v = extgcd(b, a%b)
  # bu + (a%b)v = d
  # bu + (a-(a/b)b)v = d
  # av + b(u-(a/b)v) = d
  return d, v, u-(a//b)*v

Hope the inline comments make it clear how extgcd works. In short, extgcd(a,b) returns d = gcd(a,b) and x,y such that d = ax + by with the same time complexity O(log max(a,b)).

Mod inverse

As alluded above, there is one more thing we need, particularly for division in modulo world. An integer $x$ is the inverse of an integer $a$ modulo $m$ (denoted $a^{-1}$) iff $ax \equiv 1 \pmod m$. Does the inverse always exist and if so how to find it? Let's start with some quick observation:

ax - 1 = mt for some $t \in \mathbb{Z}$, ax - mt = 1
d = gcd(a,m) then d divides 1, i.e., d = 1

It's now clear that $a^{-1}$ only exists when gcd(a,m) = 1. And the problem is to find $x$ such that: ax - mt = 1 = gcd(a,m). Looks familiar? Yes, it's exactly what extgcd can find for us, like this:

def inverse(a, m):
  d, x, y = extgcd(a,m)
  if d == 1:
    return (m+x%m)%m
  # Else, report no inverse...

What is (m+x%m)%m doing? It's a little trick to make sure the inverse is in $\{0,1,...m-1\}$.

Modulo Linear Equation

We're now ready to solve our very first linear equation in mod world, given two integers $a, b$ and modulo $m$, find an integer $x$ such that

$$ax \equiv b \pmod{m}$$

Let's start with quick observations:

ax - b = mt (1) for some integer t
d = gcd(a,m) then d should divide b; otherwise $x$ doesn't exist and the equation has no solution!

Assume d divides b, then divide both sides of (1) by d,

$a'x-b'=m't$, where $a'=a/d,b'=b/d,m'=m/d$ and $\gcd(a',m') = 1$ by the definition of $\gcd(a,m)$.

From above, we know how to find $x$ such that $a'x-m't = 1 = \gcd(a,m)$, i.e., $x$ is the inverse of a' modulo m', $a'x \equiv 1 \pmod{m'}$. So the solution to the original linear equation is:

$$x = a'^{-1} \times b' + m'k \pmod{m}$$

, where $0 \leq k < \gcd(a,m)$.

A simple C++ implementation for reference.

Modulo Linear Equation System

A next natural challenge is to solve a system of linear equations of the form $a_i x \equiv b_i \pmod{m_i}$ for $i=1,...,n$. A special case is when $a_i = 1$ for all $i=1,...n$ and $\{m_i\}_{i=1}^n$ are (pairwise) coprime, which is related to the popular Chinese remainder theorem.

As usual, let's start small by considering a system of 2 linear equations. As seen above, an equation of the form $ax \equiv b \pmod{m}$ can always be transformed into the form $x \equiv c \pmod{n}$ (when a solution exists). In practice, we can always add a trivia equation $x \equiv 0 \pmod{1}$. WLOG, consider the following system of 2 equations:

$$ \begin{cases} &x &\equiv b_1 \pmod{m_1} & (1)\\ &a_2 x &\equiv b_2 \pmod{m_2} & (2) \end{cases} $$

From (1), $x = b_1 + tm_1$ for a integer $t$. Substitute into (2), $a_2(b_1+tm_1) \equiv b_2 \pmod{m_2} \Rightarrow a_2 m_1 t \equiv b_2 - a_2 b_1 \pmod{m_2}~(3)$. (3) is a single linear equation for which we already know how to solve from above. Thus, we can solve a system of $n$ equations by iteratively reducing 2 equations to a single equation at a time and eventually solve the last remaining equation!

See this heavily commented C++ implementation for reference.

Practice Problems

https://atcoder.jp/contests/abc193/tasks/abc193_e
More to be added in the future...

Random Notes

Solving linear equations in modulo world