THE GARDEN

Fermat's Little Theorem

Updated 13 Sep 2026

• •

  What it is

  • •

    For a prime $p$ and any integer $a$ not divisible by $p$, $a^{p-1} \equiv 1 \pmod p$. A direct corollary gives a fast way to compute modular inverses under a prime modulus without the extended Euclidean algorithm.

• •

  When to apply

  • •

    The modulus is prime and you need either to verify/exploit an exponentiation identity, or to invert an element mod p quickly with a single pow() call.

• •

  Symbols and assumptions

  • •

    $p$ is prime and $a\not\equiv0\pmod p$. A congruence means equal remainders, not equality as ordinary integers.

• •

  Math — step by step

  • •
    1. Multiply the nonzero residues $1,2,\ldots,p-1$ by $a$. They remain nonzero and distinct: $ai\equiv aj$ implies $i\equiv j$, because $a$ is invertible modulo the prime.
  • •
    2. The multiplication merely permutes the set. Therefore $a^{p-1}(p-1)!\equiv(p-1)!\pmod p$. The factorial is nonzero modulo $p$, so cancel it to obtain $a^{p-1}\equiv1$.
  • •
    3. Write $a\cdot a^{p-2}\equiv1$. This identifies $a^{p-2}$ as the inverse. Do not apply this inverse formula to zero or to an arbitrary composite modulus.
• •

  Worked example

  • •

    For $p=11,a=3$: $3^2\equiv9$; $3^4\equiv81\equiv4$; $3^8\equiv16\equiv5$.

  • •

    Then $3^9\equiv5\cdot3\equiv4$, so $3^{-1}\equiv4\pmod{11}$. Check $3\cdot4=12\equiv1$, and $3^{10}\equiv1$.

  • •

    Python: pow(3, 9, 11) returns 4. Extended Euclid gives the same inverse and also works for coprime numbers with a composite modulus.

• •

  Python

  • •

    inverse = pow(a, p - 2, p)
    

• •

  SageMath

  • •

    inverse = power_mod(3, -1, 13)     # 9, Sage resolves negative exponents directly
    inverse = inverse_mod(3, 13)       # 9, equivalent dedicated function
    

• •

  Related

  • •

    Extended Euclidean Algorithm

• •

  Cards

  • •

    What condition does Fermat's Little Theorem require on the modulus?

    • •

      The modulus p must be prime, and a must not be divisible by p.

  • •

    How do you get a modular inverse from Fermat's Little Theorem?

    • •

      Compute $a^{p-2} \bmod p$.

◌ Explore connections in Graph view