Fermat’s little theorem states that if p is a prime number, then for any integer a, the number a p – a is an integer multiple of p.
Here p is a prime number
ap ≡ a (mod p).
Special Case: If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that a p-1-1 is an integer multiple of p.
ap-1 ≡ 1 (mod p)
OR
ap-1 % p = 1
Here a is not divisible by p.
Take an Example How Fermat’s little theorem works
Example 1:
P = an integer Prime number a = an integer which is not multiple of P Let a = 2 and P = 17 According to Fermat's little theorem 2 17 - 1 ≡ 1 mod(17) we got 65536 % 17 ≡ 1 that mean (65536-1) is an multiple of 17
Example 2:
Find the remainder when you divide 3^100,000 by 53.
Since, 53 is prime number we can apply fermat's little theorem here.
Therefore: 3^53-1 ≡ 1 (mod 53)
3^52 ≡ 1 (mod 53)
Trick: Raise both sides to a larger power so that it is close to 100,000.
= Quotient = 1923 and remainder = 4.Multiplying both sides with 1923: (3^52)^1923 ≡ 1^1923 (mod 53) 3^99996 ≡ 1 (mod 53)Multiplying both sides with 3^4: 3^100,000 ≡ 3^4 (mod 53) 3^100,000 ≡ 81 (mod 53) 3^100,000 ≡ 28 (mod 53).Therefore, the remainder is 28 when you divide 3^100,000 by 53.
= Quotient = 1923 and remainder = 4.Multiplying both sides with 1923: (3^52)^1923 ≡ 1^1923 (mod 53) 3^99996 ≡ 1 (mod 53)Multiplying both sides with 3^4: 3^100,000 ≡ 3^4 (mod 53) 3^100,000 ≡ 81 (mod 53) 3^100,000 ≡ 28 (mod 53).Therefore, the remainder is 28 when you divide 3^100,000 by 53.Use of Fermat’s little theorem
If we know m is prime, then we can also use Fermat’s little theorem to find the inverse.
am-1 ≡ 1 (mod m)
If we multiply both sides with a-1, we get
a-1 ≡ a m-2 (mod m)
Below is the Implementation of above :
C++
// C++ program to find modular inverse of a// under modulo m using Fermat's little theorem.// This program works only if m is prime.#include <bits/stdc++.h>using namespace std;// To compute x raised to power y under modulo mint power(int x, unsigned int y, unsigned int m);// Function to find modular inverse of a under modulo m// Assumption: m is primevoid modInverse(int a, int m){ if (__gcd(a, m) != 1) cout << "Inverse doesn't exist"; else { // If a and m are relatively prime, then // modulo inverse is a^(m-2) mode m cout << "Modular multiplicative inverse is " << power(a, m - 2, m); }}// To compute x^y under modulo mint power(int x, unsigned int y, unsigned int m){ if (y == 0) return 1; int p = power(x, y / 2, m) % m; p = (p * p) % m; return (y % 2 == 0) ? p : (x * p) % m;}// Driver Programint main(){ int a = 3, m = 11; modInverse(a, m); return 0;} |
Java
// Java program to find modular// inverse of a under modulo m// using Fermat's little theorem.// This program works only if m is prime.class GFG { static int __gcd(int a, int b) { if (b == 0) { return a; } else { return __gcd(b, a % b); } } // To compute x^y under modulo m static int power(int x, int y, int m) { if (y == 0) return 1; int p = power(x, y / 2, m) % m; p = (p * p) % m; return (y % 2 == 0) ? p : (x * p) % m; } // Function to find modular // inverse of a under modulo m // Assumption: m is prime static void modInverse(int a, int m) { if (__gcd(a, m) != 1) System.out.print("Inverse doesn't exist"); else { // If a and m are relatively prime, then // modulo inverse is a^(m-2) mode m System.out.print( "Modular multiplicative inverse is " + power(a, m - 2, m)); } } // Driver code public static void main(String[] args) { int a = 3, m = 11; modInverse(a, m); }}// This code is contributed by Anant Agarwal. |
Python3
# Python program to find# modular inverse of a# under modulo m using# Fermat's little theorem.# This program works# only if m is prime.def __gcd(a, b): if(b == 0): return a else: return __gcd(b, a % b)# To compute x^y under modulo mdef power(x, y, m): if (y == 0): return 1 p = power(x, y // 2, m) % m p = (p * p) % m return p if(y % 2 == 0) else (x * p) % m# Function to find modular# inverse of a under modulo m# Assumption: m is primedef modInverse(a, m): if (__gcd(a, m) != 1): print("Inverse doesn't exist") else: # If a and m are relatively prime, then # modulo inverse is a^(m-2) mode m print("Modular multiplicative inverse is ", power(a, m - 2, m))# Driver codea = 3m = 11modInverse(a, m)# This code is contributed# by Anant Agarwal. |
C#
// C# program to find modular// inverse of a under modulo m// using Fermat's little theorem.// This program works only if m is prime.using System;class GFG { static int __gcd(int a, int b) { if (b == 0) { return a; } else { return __gcd(b, a % b); } } // To compute x^y under modulo m static int power(int x, int y, int m) { if (y == 0) return 1; int p = power(x, y / 2, m) % m; p = (p * p) % m; return (y % 2 == 0) ? p : (x * p) % m; } // Function to find modular // inverse of a under modulo m // Assumption: m is prime static void modInverse(int a, int m) { if (__gcd(a, m) != 1) Console.WriteLine( "Modular multiplicative inverse is " + power(a, m - 2, m)); else { // If a and m are relatively prime, then // modulo inverse is a^(m-2) mode m Console.WriteLine( "Modular multiplicative inverse is " + power(a, m - 2, m)); } } // Driver code public static void Main() { int a = 3, m = 11; modInverse(a, m); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program to find modular inverse of a// under modulo m using Fermat's little theorem.// This program works only if m is prime.// To compute x raised to// power y under modulo m// Recursive function to // return gcd of a and bfunction __gcd($a, $b){ // Everything divides 0 if ($a == 0 || $b == 0) return 0; // base case if ($a == $b) return $a; // a is greater if ($a > $b) return __gcd($a-$b, $b); return __gcd($a, $b-$a);}// Function to find modular// inverse of a under modulo m// Assumption: m is primefunction modInverse($a, $m){ if (__gcd($a, $m) != 1) echo "Inverse doesn't exist"; else { // If a and m are relatively // prime, then modulo inverse // is a^(m-2) mode m echo "Modular multiplicative inverse is ", power($a,$m - 2, $m); }}// To compute x^y under modulo mfunction power($x, $y, $m){ if ($y == 0) return 1; $p = power($x,$y / 2, $m) % $m; $p = ($p * $p) % $m; return ($y % 2 == 0) ? $p : ($x * $p) % $m;} // Driver Code $a = 3; $m = 11; modInverse($a, $m); // This code is contributed by anuj__67.?> |
Javascript
<script>// Javascript program to find modular inverse of a// under modulo m using Fermat's little theorem.// This program works only if m is prime.function __gcd(a, b){ if(b == 0) { return a; } else { return __gcd(b, a % b); }}// Function to find modular inverse of a under modulo m// Assumption: m is primefunction modInverse(a, m){ if (__gcd(a, m) != 1) document.write( "Inverse doesn't exist"); else { // If a and m are relatively prime, then // modulo inverse is a^(m-2) mode m document.write( "Modular multiplicative inverse is " + power(a, m - 2, m)); }}// To compute x^y under modulo mfunction power(x, y, m){ if (y == 0) return 1; var p = power(x, parseInt(y / 2), m) % m; p = (p * p) % m; return (y % 2 == 0) ? p : (x * p) % m;}// Driver Programvar a = 3, m = 11;modInverse(a, m);// This code is contributed by rutvik_56.</script> |
Output :
Modular multiplicative inverse is 4
Time Complexity: O(log m)
Auxiliary Space: O(log m) because of the internal recursion stack.
Some Article Based on Fermat’s little theorem
- Compute nCr % p | Set 3 (Using Fermat Little Theorem)
- Modular multiplicative inverse
- Primality Test | Set 2 (Fermat Method)
- Modulo 10^9+7 (1000000007)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
