Fermat’s Little Theorem

Fermat’s Little Theorem#

Fermat’s Little Theorem states that if \(p\) is a prime number and \(a\) is an integer not divisible by \(p\), then:

\[ a^{p-1} \equiv 1 \mod p \]

This theorem is used in number theory and cryptography. It can be used to compute large powers modulo a prime number efficiently.

The steps to apply Fermat’s Little Theorem are as follows:

  1. Ensure \(p\) is prime: Verify that \(p\) is a prime number.

  2. Ensure \(a\) is not divisible by \(p\): Check that \(a\) is an integer not divisible by \(p\).

  3. Apply the theorem: Compute \(a^{p-1} \mod p\).

For example, to compute \(3^{6} \mod 7\):

  1. \(p = 7\) is prime.

  2. \(a = 3\) is not divisible by 7.

  3. Apply the theorem: \(3^{7-1} \equiv 1 \mod 7\)

  4. \(3^{6} \mod 7 = 1\)

Therefore, \(3^{6} \equiv 1 \mod 7\).

Hide code cell source 
import sympy as sp
from sympy import *
from math import gcd
import random

Implementation:#

def check_congruence(a, n):
    if pow(a, n-1, n) == 1 % n:
        print(f"true, {n} is congruent with base {a}.")
    else:
        print(f"false, {n} is not congruent with base {a}.")
        
def fermats_test(n, a):
    if pow(a, n-1, n) == 1:
        return True
    else:
        return False

Examples:#

Checking \(91\) and \(3\) for Fermat’s Little Theorem:#

%%time

n = 91
a = 3

check_congruence(a, n)

if fermats_test(n, a):
    print(f"{n} is probably prime.")
else:
    print(f"{n} is composite.")

true, 91 is congruent with base 3.
91 is probably prime.
CPU times: user 65 μs, sys: 14 μs, total: 79 μs
Wall time: 69.1 μs

Explanation

Testing if 91 is Prime with Base 3

Using Fermat’s Little Theorem:

\[ 3^{90} \mod 91 \]

Calculate \(3^{90} \mod 91\):

\[ 3^{90} \equiv 1 \mod 91 \]

Since the congruence holds true, 91 is probably prime.

Result:

  • True, 91 is congruent with base 3.

  • 91 is probably prime.

Checking \(88\) and \(6\) for Fermat’s Little Theorem:#

%%time

n = 88
a = 6

check_congruence(a,n)

if fermats_test(n, a):
    print(f"{n} is probably prime.")
else:
    print(f"{n} is composite.")

false, 88 is not congruent with base 6.
88 is composite.
CPU times: user 64 μs, sys: 13 μs, total: 77 μs
Wall time: 68.2 μs

Explanation

Testing if 88 is Prime with Base 6

Using Fermat’s Little Theorem:

\[ 6^{87} \mod 88 \]

Calculate \(6^{87} \mod 88\):

\[ 6^{87} \not\equiv 1 \mod 88 \]

Since the congruence does not hold true, 88 is composite.

Result:

  • False, 88 is not congruent with base 6.

  • 88 is composite.

Checking \(104729\) and \(2\) for Fermat’s Little Theorem:#

%%time

n = 104729
a = 2

check_congruence(a,n)

if fermats_test(n, a):
    print(f"{n} is probably prime.")
else:
    print(f"{n} is composite.")

true, 104729 is congruent with base 2.
104729 is probably prime.
CPU times: user 76 μs, sys: 0 ns, total: 76 μs
Wall time: 68.9 μs

Explanation

Testing if 104729 is Prime with Base 2

Using Fermat’s Little Theorem:

\[ 2^{104728} \mod 104729 \]

Calculate \(2^{104728} \mod 104729\):

\[ 2^{104728} \equiv 1 \mod 104729 \]

Since the congruence holds true, 104729 is probably prime.

Result:

  • True, 104729 is congruent with base 2.

  • 104729 is probably prime.

Contents