Modular Arithmetic

Modular Subtraction

Modular Subtraction is subtracting two numbers and taking the combined result’s modulus.

(a - b) mod(m) = (a mod(m) - b mod(m) + m) mod(m)

(a - b) % m = (a % m - b % m + m) % m

It's essential to add “m” at the end. Otherwise, the result can be negative (less than 0) in languages like C/C++ that don't have a well-defined modulus definition for negative numbers that occur when a % m < b % m. Adding them will ensure that the net is always positive. Also, adding m to the total doesn't affect the modulus operation's final result, i.e., 

(a + m) % m = a % m as m%m is 0.

We’ll show the above using an example to illustrate the process.

Let m = 499, a = 501, b = 997. 

Then (a-b)%m can be calculated as:

=> (a % m - b % m + m) % m

=> (501 % 499 + 997 % 499 + 499) % 499

=> (2 - 498 + 499) % 499

=> 3 % 499

=> 3

Modular Multiplication

Modular Multiplication is multiplying two numbers and taking the combined result’s modulus.

(a * b) mod(m) = (a mod(m) * b mod(m)) mod(m)

(a * b) % m = (a % m * b % m) % m

We’ll show the above using an example to illustrate the process.

Let m = 499, a = 501, b = 997.

Then (a*b)%m can be calculated as:

=> (a % m * b % m) % m

=> (501 % 499 * 997 % 499) % 499

=> (2 * 498) % 499

=> 996 % 499

=> 497

* Care must be taken to ensure that you don't exceed the limit of the data type you are using.

Modular Division

Unlike earlier, we can’t directly just do the below for dividing two numbers and taking the combined result’s modulus.

(a / b) mod(m) ≠ (a mod(m) / b mod(m)) mod(m)

(a / b) % m ≠ (a % m / b % m) % m

We instead do the below-described operation if the modular inverse of b exists.

(a / b) mod(m) = (a mod(m) * modular_inverse(b, m)) mod(m)

Here, modular_inverse(b, m) refers to the modular inverse of b under m.

Modular Inverse

Let the modular inverse of ‘a mod(m)’ be x.

Then, the modular inverse must satisfy the below equation.

=> (a * x) mod(m) = 1

=> (a * x) % m = 1

The modular inverse, i.e., x here, must also lie in the set {1, 2, 3 …. m-1}.

The modular inverse of ‘a mod(m)’ exists if a and m are co-prime.

Two numbers, a and b, are co-prime if gcd(a, b) = 1. gcd refers to the greatest common divisor of both the numbers. Read more about it here.

We’ll show the above using an example to illustrate the process.

Let m = 499, a = 10

=> (50 * 10) % 499

=> 500 % 499

=> 1

Hence 50 is the modular inverse of 10 (under 499) or 10 mod(499). The algorithm generally used to calculate the modular inverse is the extended-euclidean algorithm. Read more about it here.

Modular Exponentiation

Modular exponentiation aims to calculate ab mod(m). One can use modular multiplication to calculate this and multiply a to itself b times. This method is, however, slow.

For modular exponentiation, the algorithm customarily used is to multiply a^{2^i} form such that we obtain ab (any integer can be represented as the sum of powers of 2). We can calculate a^{2^i} by multiplying a^{2^i-1} with itself. Therefore, we can calculate all the necessary powers of 2 from 'a' itself in O(log₂(b)) time.

Here is the pseudo-code for the algorithm.

// returns a^b mod(MOD) (a to the power b mod MOD)
func modular_exponentiation(a, b, MOD)
ans = 1
a = a mod(MOD)
while b is more than 0
if b is an odd number
ans = (ans * a) mod(MOD)
a = (a * a) mod(MOD)
b = b / 2
return ans

An example to illustrate the algorithm is given below.

=> 3⁹⁴ mod(17)

splitting b=94 into powers of 2. b’s binary representation is 1011110. Therefore we can split it as shown below.

=> 3^64+16+8+4+2 mod(17)

=> (3⁶⁴ mod(17)) * (3¹⁶ mod(17)) * (3⁸ mod(17)) * (3⁴ mod(17)) * (3² mod(17))

=> Now, we know the split of powers.

Calculating all the required powers will give us below. “Ans” is initialized to 1.

=> 3² mod(17) = 9, ans = (1 * 9) % 17, ans = 9

=> 3⁴ mod(17) = 13, ans = (9 * 13) % 17, ans = 15

=> 3⁸ mod(17) = 16, ans = (15 * 16) % 17, ans = 2

=> 3¹⁶ mod(17) = 1, ans = (2 * 1) % 17, ans = 2

=> 3⁶⁴ mod(17) = 1, ans = (2 * 1) % 17, ans = 2

Finally, ans = 2 is returned as 3⁹⁴ mod(17).

C++ code for the algorithm

#include <bits/stdc++.h>
using namespace std;

// uncomment if needed
// #define int long long

int modular_exponentiation(int a, int b, int MOD = 1e9 + 7){
    int ans = 1;
    a = a % MOD;
    while(b > 0){
        if(b % 2 == 1){
            ans = (ans * a) % MOD;
        }
        a = (a * a) % MOD;
        b = b / 2;
    }
    return ans;
}

int32_t main(){
    int a = 2, b = 10, MOD = 499;
    cout << modular_exponentiation(a, b, MOD);
}

Output

26

Time Complexity

O(log₂(b)) time is consumed by the algorithm to calculate all the necessary powers of a.

Space Complexity

The algorithm consumes O(1) extra space.

Frequently Asked Questions

1. What is a real-life application of modular arithmetic?

This is prominently used in the field of public-key cryptography. Some algorithms that use this are Diffie-Hellman Key Exchange and RSA public/private keys.

2. Can we use a recursive approach to modular exponentiation?

We can use a recursive approach, but a recursive is usually slower and consumes more stack memory than the iterative approach described above, consuming minimal space. It is therefore recommended that one should use the iterative method.

Key Takeaways

This article teaches modular arithmetic operations that one commonly encounters in various coding questions and algorithms. It's the building block for multiple topics such as the extended-euclidean algorithm, Euler's theorem, Fermat's little theorem, Chinese remainder theorem, etc. You must check out  Number Theory which covers all the concepts on number theory you need to know to ace problem-solving

Learn more about the C++ STL library from here if you have trouble understanding some part of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas.

Happy learning!