Fermat's Little Theorem Explained

Fermat's Little Theorem

Fermat's Little Theorem states that if p is a prime number and a is an integer such that p does not divide a, then: 

ap-1 ≡ 1 (mod p)

A practical use of this theorem is in computing modular inverses and modular exponentiation efficiently, especially in number theory and cryptography.

Algorithm

To compute ap-2 mod p, we use binary exponentiation: 

 
modular_pow(a, b, p):
    result = 1
    a = a % p
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % p
        a = (a * a) % p
        b = b // 2
    return result

Time and Space Complexity

  • Time Complexity: O(log b) for exponentiation
  • Space Complexity: O(1)

Easy Problems

1. Compute ab mod p

 
// C++
#include <iostream>
using namespace std;

long long mod_pow(long long a, long long b, long long p) {
    long long res = 1;
    a = a % p;
    while (b > 0) {
        if (b % 2 == 1)
            res = (res * a) % p;
        a = (a * a) % p;
        b /= 2;
    }
    return res;
}

int main() {
    cout << mod_pow(3, 200, 13) << endl; // Output: 9
    return 0;
}

2. Modular Inverse of a number mod p

// C++
#include <iostream>
using namespace std;

long long mod_inverse(long long a, long long p) {
    return mod_pow(a, p - 2, p);
}

int main() {
    long long a = 3, p = 11;
    cout << mod_inverse(a, p) << endl; // Output: 4
    return 0;
}

Intermediate Problems

1. Calculate nCr % p (p is prime)


// C++
#include <iostream>
using namespace std;

const int MAX = 1000;
long long fact[MAX];

long long mod_pow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b) {
        if (b % 2) res = (res * a) % p;
        a = (a * a) % p;
        b /= 2;
    }
    return res;
}

void compute_factorials(int p) {
    fact[0] = 1;
    for (int i = 1; i < MAX; ++i)
        fact[i] = (fact[i - 1] * i) % p;
}

long long nCr_mod_p(int n, int r, int p) {
    if (r > n) return 0;
    compute_factorials(p);
    long long num = fact[n];
    long long denom = (fact[r] * fact[n - r]) % p;
    return (num * mod_pow(denom, p - 2, p)) % p;
}

int main() {
    cout << nCr_mod_p(10, 3, 13) << endl; // Output: 3
    return 0;
}

2. Check if a number is a Fermat pseudoprime to base a


// C++
#include <iostream>
using namespace std;

bool is_fermat_pseudoprime(int n, int a) {
    if (n <= 1 || n == a) return false;
    return mod_pow(a, n - 1, n) == 1;
}

int main() {
    cout << is_fermat_pseudoprime(561, 2) << endl; // Output: 1 (true)
    return 0;
}

Hard Problem

Modular Inverse for an Array under Modulo p (where p is prime)

Precompute modular inverses for all numbers from 1 to N efficiently using Fermat's Little Theorem.

// C++
#include <iostream>
#include <vector>
using namespace std;

vector<long long> compute_mod_inverses(int n, int p) {
    vector<long long> inv(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = mod_pow(i, p - 2, p);
    }
    return inv;
}

int main() {
    int n = 10, p = 13;
    vector<long long> inv = compute_mod_inverses(n, p);
    for (int i = 1; i <= n; ++i) {
        cout << "Inverse of " << i << " mod " << p << " is " << inv[i] << endl;
    }
    return 0;
}