1.
Introduction
2.
3.
Modular Subtraction
4.
Modular Multiplication
5.
Modular Division
6.
Modular Inverse
7.
Modular Exponentiation
7.1.
C++ code for the algorithm
7.1.1.
Output
7.1.2.
Time Complexity
7.1.3.
Space Complexity
8.
9.
Key Takeaways
Last Updated: Mar 27, 2024

# Modular Arithmetic

SHIKHAR SONI

## Introduction

The article aims to introduce you to modular arithmetic. Modular Arithmetic deals with the computation of mod of the result after certain operations such as addition, subtraction, etc. that we will cover in this article.

It's essential to understand modular arithmetic. Many interview questions and coding tests involve finding a huge number that can't fit into even a 64-bit integer and require you to print the large number mod 109 + 7 or such large primes. It can show up in various other math-related problems and algorithms.

Finding a mod(m) is the same as finding the remainder when we divide a by m, i.e., a % m.

% (modulus symbol) is used to find the remainder of two numbers in most programming languages.

Modular addition is adding 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

=> 500 % 499

=> 1

And (a+b)%m = (501+997)%499 = 1498%499 = 1.

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

Also see, Euclid GCD Algorithm

## 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 a2^i form such that we obtain ab (any integer can be represented as the sum of powers of 2). We can calculate a2^i by multiplying a2^i-1 with itself. Therefore, we can calculate all the necessary powers of 2 from 'a' itself in O(log2(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.

=> 394 mod(17)

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

=> 364+16+8+4+2 mod(17)

=> (364 mod(17)) * (316 mod(17)) * (38 mod(17)) * (34 mod(17)) * (32 mod(17))

=> Now, we know the split of powers.

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

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

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

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

=> 316 mod(17) = 1, ans = (2 * 1) % 17, ans = 2

=> 364 mod(17) = 1, ans = (2 * 1) % 17, ans = 2

Finally, ans = 2 is returned as 394 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(log2(b)) time is consumed by the algorithm to calculate all the necessary powers of a.

#### Space Complexity

The algorithm consumes O(1) extra space.

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!

Live masterclass