1.
Introduction
2.
Proof of Validity of Fermat's Little Theorem
3.
Using Fermat's Little Theorem
3.1.
Pseudocode for the algorithm
3.2.
Code in C++
3.3.
Output
3.4.
Time Complexity
3.5.
Space Complexity
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

Fermat's Theorem

SHIKHAR SONI
0 upvote

Introduction

Fermat's Theorem, more popularly known as Fermat's Little Theorem, is a special case of Euler's Theorem. Euler's Theorem states that aphi(p) ≡ 1 (mod(p)) (read as 'a to the power phi of p is congruent to 1 mod p', it essentially means aphi(p) % p = 1), here phi(m) refers to the Euler's totient function, this function phi(n) essentially finds the count of all numbers from 1 to n who have no common factor with n other than 1.

When n is a prime number, we have phi(n)=n -1. This fact is apparent from defining a prime number (a number that has no factors other than 1 and itself).

Hence, we obtain the form for Fermat's Little Theorem, i.e., ap-1 ≡ 1 (mod p) (it's equivalent to the more popular version, i.e., ap ≡ a (mod p)), where p is a prime number and a must be co-prime with p.

For example,

a = 2, p = 23

=> (223-1) % 23

=> (222) % 23

The value of the above quantity must be 1 according to Fermat's Little Theorem

=> 4194304 % 23

=> 1

Proof of Validity of Fermat's Little Theorem

We will give a short inductive proof for Fermat's Little Theorem here.

Fermat's Theorem can be written as ap ≡ a (mod p) (this is the same as saying p | (ap - a), `read as p divides ap - a`).

We’ll use the above statement, assume it’s true and prove the same for p | ((a+1)p - (a+1)). The base case when a = 1 holds for the induction proof.

=> (a+1)p

=> pC0a0pC1a1pC2a2 ….. + pCp-1ap-1pCpap    (Performing binomial expansion)

=> 1 + pC1a1 + …. + pCp-1ap-1 + ap, here {pC1a1 + …. + pCp-1ap-1 is divisible by p}

We can therefore write it as below,

=> p | (pC1a1 + …. + pCp-1ap-1)

=> p | ((a + 1)p - (ap + 1)), because p | ap - a, the statement can be written as

=> p | ((a + 1)p - (ap + 1) + ap - a)

=> p | ((a + 1)p - (a + 1))

Hence, we proved the Fermat's Little Theorem by induction.

Also see, Euclid GCD Algorithm

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

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

Hence we use modular exponentiation and find ap-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(log2(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.

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(mod p), instead of just a (mod p)?

Yes, you can, a general formula for the above would ap-k-1 ≡ a-k mod(p) (here a-k refer to the modular multiplicative inverse of ak). 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!

Live masterclass