**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_{2}(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^{94} 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^{64} mod(17)) * (3^{16} mod(17)) * (3^{8} mod(17)) * (3^{4} mod(17)) * (3^{2} mod(17))

=> Now, we know the split of powers.

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

=> 3^{2} mod(17) = 9, ans = (1 * 9) % 17, ans = 9

=> 3^{4} mod(17) = 13, ans = (9 * 13) % 17, ans = 15

=> 3^{8} mod(17) = 16, ans = (15 * 16) % 17, ans = 2

=> 3^{16} mod(17) = 1, ans = (2 * 1) % 17, ans = 2

=> 3^{64} mod(17) = 1, ans = (2 * 1) % 17, ans = 2

Finally, ans = 2 is returned as 3^{94} 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_{2}(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!