Fermat's Little Theorem Calculator

A Deep Dive into Fermat's Little Theorem

Welcome to the ultimate guide on Fermat's Little Theorem, a fundamental result in number theory that provides a powerful shortcut for modular exponentiation. This guide, along with our intuitive Fermat's Little Theorem Calculator, will demystify this elegant theorem and show you how to apply it to solve complex problems with ease.

What is Fermat's Little Theorem?

First, let's state Fermat's Little Theorem. It's a statement about the relationship between a prime number and integers raised to a power. The theorem has two common forms:

Form 1: The Main Statement

If 'p' is a prime number, then for any integer 'a' not divisible by 'p', it holds that:

This means if you raise 'a' to the power of (p-1) and divide by 'p', the remainder will always be 1.

Form 2: A Generalization

A slightly different but equivalent form applies to *any* integer 'a' (even those divisible by 'p'):

This means if you raise 'a' to the power of 'p', the result will have the same remainder as 'a' when divided by 'p'. Our calculator uses the first, more common form to simplify calculations.

Fermat's Little Theorem Examples

The true power of this theorem is its ability to simplify very large exponents. Let's walk through some classic Fermat's Little Theorem examples. This is exactly how our calculator provides step-by-step solutions.

Example 1: A Classic Problem

Use Fermat's Little Theorem to find 7¹²¹ mod 13.

• Step 1 (Check Conditions): The modulus, p=13, is a prime number. The base, a=7, is not divisible by 13. The conditions are met.
• Step 2 (Apply Theorem): We know that a^p-1 ≡ 1 (mod p). So, 7^13-1 ≡ 1 (mod 13), which means 7¹² ≡ 1 (mod 13).
• Step 3 (Simplify the Exponent): We need to rewrite the exponent 121 in terms of 12. We do this with division: 121 ÷ 12 = 10 with a remainder of 1. So, 121 = 12 × 10 + 1.
• Step 4 (Substitute and Solve):
  • 7¹²¹ = 7^{(12 × 10 + 1)} = (7¹²)¹⁰ × 7¹
  • Now, we take the mod 13: (7¹²)¹⁰ × 7¹ ≡ (1)¹⁰ × 7 (mod 13)
  • This simplifies to 1 × 7 ≡ 7 (mod 13).
• Answer: 7¹²¹ mod 13 is 7.

Example 2: A Larger Exponent

Use Fermat's Little Theorem to find 23¹⁰⁰² mod 41.

• Step 1 (Check): p=41 is prime. a=23 is not divisible by 41. Conditions met.
• Step 2 (Apply): We know 23^41-1 ≡ 1 (mod 41), so 23⁴⁰ ≡ 1 (mod 41).
• Step 3 (Simplify): We rewrite the exponent 1002: 1002 ÷ 40 = 25 with a remainder of 2. So, 1002 = 40 × 25 + 2.
• Step 4 (Substitute):
  • 23¹⁰⁰² = (23⁴⁰)²⁵ × 23²
  • mod 41: ≡ (1)²⁵ × 23² (mod 41)
  • ≡ 1 × 529 (mod 41)
  • Now we just need to find the remainder of 529 ÷ 41. 529 = 41 × 12 + 37.
• Answer: 23¹⁰⁰² mod 41 is 37.

As you can see, this method allows you to simplify each expression using Fermat's Little Theorem without needing a powerful computer for the raw exponentiation.

Proof of Fermat's Little Theorem (Intuitive Idea)

A full, rigorous proof of Fermat's Little Theorem can be done using modular arithmetic, binomial coefficients, or group theory. Here is an intuitive outline using a combinatorial argument (Multinomial Coefficients):

1. Consider a string of 'p' beads, where each bead can be one of 'a' different colors. The total number of possible strings is a^p.
2. Of these, 'a' strings are monochromatic (all beads are the same color).
3. The remaining (a^p - a) strings are multicolored. If you rotate these strings, they come in groups of 'p' unique rotations. For example, a string R-G-B for p=3 gives R-G-B, G-B-R, and B-R-G.
4. Since these (a^p - a) strings can be perfectly bundled into groups of size 'p', it must be that 'p' divides (a^p - a).
5. This means a^p - a ≡ 0 (mod p), which is equivalent to a^p ≡ a (mod p), the second form of the theorem.

Euler's Totient Theorem: The Generalization

What if the modulus is not a prime number? The generalization to Fermat's Little Theorem is known as Euler's Totient Theorem. It uses Euler's totient function, φ(n), which counts the number of positive integers up to 'n' that are relatively prime to 'n'.

Euler's Theorem states that for any integer 'a' that is coprime to 'n':

Note that if 'n' is a prime number 'p', then φ(p) = p-1, and Euler's theorem reduces exactly to Fermat's Little Theorem.

Conclusion: A Cornerstone of Number Theory

Fermat's Little Theorem is a beautiful and surprisingly useful result in mathematics. It forms the basis of primality testing and is a key ingredient in the RSA encryption algorithm that secures much of our digital communication. This Fermat's Little Theorem Calculator is designed to make this powerful tool accessible, providing clear, step-by-step solutions that illuminate the process and help you master one of number theory's most elegant theorems.