Fermat's Theorem

Using Fermat's Little Theorem

Fermat's Little Theorem is commonly used in the Fermat's Primality Test (refer here for information about primality test and how Fermat's Little Theorem can be used in them) and can also be used as a method to find the Modular Multiplicative Inverse.

This article will cover finding the Modular Multiplicative Inverse with Fermat's Little Theorem. We can rearrange the equation for Fermat's Little Theorem to obtain the below,

Here a^-1 is the modular multiplicative inverse, and by dividing both sides with it, we obtain 

a^p-2 ≡ a^-1 (mod p).

Hence we use modular exponentiation and find a^p-2 % p to find the multiplicative inverse.

Pseudocode 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
// it’s assumed that input m is a prime number
print(modular_exponentiation(a, m-2, m))

Code in C++

#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;
}

int modular_multiplicative_inverse(int a, int m){
    return modular_exponentiation(a, m-2, m);
}

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

Output

50

Time Complexity

This algorithm takes O(log₂(p)) time. This method can be easily used with modular exponentiation and is easy and fast to code iteratively in various circumstances (such as an interview or a contest).

Space Complexity

The algorithm consumes O(1) extra space.

Frequently Asked Questions

1. What are real-life applications of Fermat's Little Theorem?

Fermat's Little Theorem forms the basis for primality tests such as the Miller-Rabin primality test that can predict if a number is prime where the prediction error can be made very low.

These tests are much faster than the currently available deterministic primality tests and are needed for various uses in algorithms such as RSA to generate large random primes.

2. What is Modular Multiplicative Inverse?

The modular multiplicative inverse of a (mod m) is the number x, where ax ≡ 1 mod(p). The modular inverse only exists if a and m are co-prime, i.e., they don't have any common factor other than 1. x is an integer that must also lie in the range [1, p-1] (1 and p-1 inclusive).

3. Can we find the modular multiplicative inverse of quantities of the form a^k (mod p), instead of just a (mod p)?

Yes, you can, a general formula for the above would a^p-k-1 ≡ a^-k mod(p) (here a^-k refer to the modular multiplicative inverse of a^k). This can be derived similarly from the above and can help you find the result easily.

4. What is the value passed to the variable MOD in the function definition of modular exponentiation?

We can pass default arguments to various variables like that and when we don’t supply any value to that variable, the default value is instead assigned to it. This helps make the code more modular.

5. I have observed values such as 1000000007 and 998244353 being used in problems commonly, why?

These values are large prime numbers. Their use can be attributed to the fact that performing any of the basic modular arithmetic operations with them doesn’t cause overflow in a 64-bit integer, and them being large primes ensures that one can find the modular multiplicative inverse and other quantities without restrictions for most problems constraints. Choosing them to be large also provides a large range for output.

Key Takeaways

This article teaches about Fermat's Theorem and familiarizes you with the idea. We covered some background, its application and the associated code. To understand and apply number theory concepts better, check out Number Theory related blogs here that covers all the essential concepts on number theory.

Also, check out the article Modular Multiplicative Inverse to understand this concept and its uses.

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!