// NUMBER THEORY · ADVANCED

Fermat's Little Theorem

The tiny power law that underpins modular inverses, fast exponentiation, and the simplest primality test.

See the Cycle Play Fermat Test
Advanced·20 min·Mathematics · Number Theory
Reviewed by CodeTikki Academic Team

Prerequisites: Modular arithmetic · Prime numbers · Modular inverses

// VISUALIZER

Watch the power cycle collapse to 1

Pick a prime p and a base a. The powers a^1, a^2, ..., a^(p-1) modulo p always end at 1. That is Fermat's Little Theorem in action.

2^12
2^24
2^31
2^42
2^54
2^61

Fermat's Little Theorem: for prime p = 7 and base a = 2, the last value in the power cycle should be 1.

Last power

2^6 ≡ 1 (mod 7)

// MINI GAME

Fermat Test

Use a^(n-1) mod n to decide: is n prime, definitely composite, or a Fermat pseudoprime? Beware the liars!

Loading test...

// FLOWCHART

Algorithm flow

// FLOWCHART · Fermat's Little Theorem
Compute a^(p-1) mod p
YesNoYesNoYesNoStartRead p, aIs p prime?GCD(a, p) = 1?Compute a^(p-1) mod pResult = 1?Theorem confirmedTheorem does not apply or p not primeEnd

Press PLAY to trace the algorithm through the flowchart.

0 / 8

// PSEUDOCODE

Trace the code

// PSEUDOCODE · Fermat's Little Theorem
Fast modular exponentiation for 2^10 mod 11
a = 2, p = 11
1function modPow(a, e, mod):
2 result = 1
3 while e > 0:
4 if e is odd:
5 result = (result * a) % mod
6 a = (a * a) % mod
7 e = e / 2
8 return result

Press PLAY to step through the algorithm line by line.

0 / 19

// TUTORIAL QUIZZES

Test your mastery

From the statement of the theorem to pseudoprimes, fast exponents, and RSA connections.

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

The Fermat Check: Compute a^(p-1) mod pL4The Modular Inverse: Fast Inverse with FermatL5The Power Reducer: Big Exponents Modulo a PrimeL5The Pseudoprime Hunter: Find a LiarL7The Miller-Rabin Witness: Stronger Primality TestL9

// REFERENCES

Sources & further reading

  1. [1]
    Fermat's Little TheoremPierre de Fermat (1640) — first stated without proof
  2. [2]
    Disquisitiones ArithmeticaeCarl Friedrich Gauss — modular arithmetic and number theory
  3. [3]
    Introduction to Algorithms (CLRS)T. H. Cormen et al. — modular arithmetic and number-theoretic algorithms
  4. [4]
    A Course in Number Theory and CryptographyNeal Koblitz — primality testing and RSA

// READY?

Count the numbers coprime to n

Next up: Euler's Totient Function. It generalizes Fermat's theorem and is the heart of RSA.

Euler's Totient Browse Tutorials