Modular Arithmetic For Competitive Programming

Hello guys, welcome back to “code with asharam”. I will continue with my mathematics series in this post. So, in this post I will discuss one of the most frequent topics in competitive programming – Modular Arithmetic. Finding modulo is really simple but finding inverse modulo is little tricky. That’s why I will tell you about some most popular algorithms used to find inverse modulo. Before that we will discuss basics of modular arithmetic. So, gear up to dive into deep and insightful oceans of mathematics.

Modular Arithmetic – Basics

As you know that modulo operator ($\%$) computes the remainder obtained on dividing an integer $a$ by a positive integer $c$. For example, $9\%8 = 1$, $5\%3 = 2$ and $-1\%5 = 4$. If you didn’t understand the last example, then, please refresh you knowledge of negative integers by positive integers.
If we write $a = c*q + r$, then, $a/c = q$ and $a\%c = r$. Now, let’s consider two integer $a$ and $b$ and there modulo with respect to another $c$. Let’s represent $a$ as $c*q_1 + r_1$ and $b$ as $c*q_2+r_2$ and analyze some important operations.

  1. $a+b = c*q_1 + r_1 + c*q_2+r_2 = c*(q_1+q_2) + (r_1+r_2)$
    Now, you write $(r_1+r_2)$ as $c*q_3 + r_3$
    and hence, $a+b = c*(q_1+q_2+q_3) + r_3$
    Clearly, $(a+b)\%c = r_3 = (r_1 + r_2)\%c = ((a\%c) + (b\%c))\%c$
  2. Similarly, You can obtain following results:
    \[
    \begin{array}{c}
    (a-b)\%c = ((a\%c) – (b\%c))\%c \\
    (a*b)\%c = ((a\%c) * (b\%c))\%c \\
    (a/b)\%c = ((a\%c) * ((1/b)\%c))\%c
    \end{array}\]
    You might be wondering how to compute $(1/b)\%c$. Value of $(1/b)\%c$ is known as modular inverse of $b$ with respect to $c$. In next section, I will discuss various methods to compute modular inverse.

From now on, $expression1 \equiv expression2 \mod m$ is equivalent to $expression1\%m = expression2\%m$. There is one more definition of modular inverse as follows:
\[
\begin{array}{c}
a*x \equiv 1 \mod m \\
x \equiv (1/a) \mod m
\end{array}
\]
Clearly, modular inverse of a positive integer $a$ with respect to $m$ is another non-negative integer $x < m$ such that $(a*x)\%m = 1$. Some of you will ask why $x < m$? It is because of the fact that $x\%m$ can take only values in the range $[0, m)$ and if we take $x>=m$, then, we will just repeat already checked values of $x\%m$.

Condition for Existence of Modular Inverse

Modular inverse of $a\%m$ exists only if $gcd(a, m) = 1$. If you don’t know much about gcd, then, I will advice you to read my article on gcd before moving forward as it will be used very frequently.

Proof of the statement:

\[
\begin{array}{c}
ax \equiv 1 \mod m \\
\implies ax = km + 1 \\
\implies ax – km = 1 \\
\implies gcd(a, m) | (ax – km), gcd(a, m) | 1 \\
\implies gcd(a, m) = 1
\end{array}
\]

Finding Modular Inverse using Extended Euclidean Algorithm

Extended Euclid Algorithm involves finding 2 integers $x$, $y$ satisfying following equation: $$ax + by = gcd(a, b) \text{ —->equation 1}$$. Let’s see how we can use $x$, $y$ for our advantage.
If we replace $b$ with $m$ and $gcd(a, b)$ with $1$ (because $gcd(a, m) = 1$), we will obtain following equation:
\[
\begin{array}{c}
ax + my = 1 \\
\text{After performing mod on both sides, } ax + my \equiv 1 \mod m \\
\implies ax \equiv 1 \mod m
\end{array}
\]
Clearly, you can see that the value of $x$ in Extended Euclid algorithm is equal to the modular inverse of $a\%m$. Now, our task is to solve the equation efficiently. We will do so by using the Euclid algorithm I discussed in gcd article. Let’s see how?
We know that, $gcd(a, b) = gcd(b\%a, a)$ and also, we can solve this recursive relation in logarithmic time. Let’s form an another equation using this relation as follows:
$$(b\%a)x_1 + ay_1 = gcd(a, b) \text{ —->equation 2}$$
Things become interesting when we substitute $b\%a = b – [b/a]*a$
\[
\begin{array}{c}
(b – [b/a]*a)x_1 + ay_1 = gcd(a, b) \\
a(y_1 – [b/a]*x_1) + bx_1 = gcd(a, b) \text{ —->equation 3}
\end{array}
\]
Now, if you compare equation 1 and equation 3, you will get following results:
$$x = y_1 – [b/a]*x_1,\text{ } y = x_1$$
Hence, we saw that we can solve equation 1 by recursively solving equation 2. This relation is exactly similar to the one in Euclid algorithm except for the fact that it involves different operations and that’s why it is named Extended Euclid Algorithm. The time complexity of this algorithm is $min(a, b)$.

Finding Modular Inverse using Fermat’s Theorem

Main condition for Fermat’s theorem is “$m$ should be a prime number“. I will not discuss its proof as it is a little complex and is not really required to understand the algorithm. According to Fermat theorem, for any positive integer $a$ and prime number $m$, following relation holds:
\[
\begin{array}{c}
a^{m-1} \equiv 1 \mod m \\
\text{Clearly, } a^{m-2} \equiv (1/a) \mod m
\end{array}
\]
Hence, we can say that modular inverse of $a\%m$ is equal to $a^{m-2}\%m$ which we can easily calculate in $log(m)$ by using binary exponentiation.

Finding Modular inverse for all i < m, m is prime

Problem is taken from https://cp-algorithms.com/algebra/module-inverse.html
We can use any of the above 2 algorithms but both of them runs in $O(m*log(m))$ time and we can do it in $O(m)$ time. Let’s see how
\[
\begin{array}{c}
m\%i = m – [m/i]*i \\
\text{take modulo on both side, }m\%i \equiv m – [m/i]*i \mod m \\
\text{multiply both side by } i^{-1}*(m\%i)^{-1},\text{ } i^{-1} \equiv -[m/i]*(m\%i)^{-1} \mod m
\end{array}
\]
Note that while calculating $i^{-1}$ using above relation, we don’t need to calculate $(m\%i)^{-1}$ again because we would have already computed $(m\%i)^{-1}$ and stored it for future reference. Fancy name for this technique is Dynamic Programming.
Enough of theory, let’s write code for all the algorithms we have discussed so far:

Code

#include <bits/stdc++.h>

using namespace std;

int a = 3, m = 19;


struct euclid{
    int gcd = 0, x=0, y=0;
};

euclid extendedGcd(int a, int b) {
    if (a==0) return {b, 0, 1};
    euclid e = extendedGcd(b%a, a);
    return {e.gcd, e.y - (b/a)*e.x, e.x};
}

int fastModPow(int x, int n) {
    if (n==0) return 1;
    int y = fastModPow(x, n/2)%m;
    y = (y*y)%m;
    if (n%2) return (y*x)%m;
    return y;
}

void modInvForAllI(int a[], int m) {
    a[1] = 1;
    for (int i=2; i<m; i++) {
        a[i] = (m - (m/i) * a[m%i])%m;
        if (a[i] < 0) a[i] += m;
    }
}

int main() {
    
    /* Since c++ gives as negative integers for mod operations
       performed on negative integers, we have to add m to make
       them positive. */
    cout << (extendedGcd(a, m).x + m)%m << "\n";
    cout << fastModPow(a, m-2) << "\n";
    int a[m];
    modInvForAllI(a, m);
    for (int i=1; i<m; i++) cout << a[i] << " \n"[i==m-1];

}

 
So, I have finished my work. Now, it is your turn to go to codechef or codeforces and search for problems with modulus tag and start solving them. Thank you guys for reading so far.
You can subscribe to my YouTube channel for video tutorials on competitive programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: