Fermat's Little Theorem Calculator

⚛️ Fermat's Little Theorem Calculator

📘 What is Fermat's Little Theorem?

Fermat's Little Theorem is a fundamental result in number theory that provides a powerful tool for working with modular arithmetic. It was first stated by the brilliant French mathematician Pierre de Fermat in 1640. The theorem is foundational to many areas of mathematics and computer science, especially in the field of cryptography.

The theorem states that if `p` is a prime number, then for any integer `a` that is not divisible by `p`, the number `a^(p-1) - 1` is an integer multiple of `p`. This is typically expressed in the language of modular arithmetic as:

a^(p-1) ≡ 1 (mod p)

Where:

• `a` is an integer that is not a multiple of `p`. (i.e., `gcd(a, p) = 1`).
• `p` is a prime number.
• `≡` denotes congruence, meaning that when `a^(p-1)` is divided by `p`, the remainder is 1.

A more general version of the theorem, which works for any integer `a` (even multiples of `p`), is:

a^p ≡ a (mod p)

This formulation is useful because it removes the condition that `a` cannot be a multiple of `p`. Our Fermat's Little Theorem Calculator primarily uses the first form but handles all valid inputs correctly.

🧐 Proof of Fermat's Little Theorem (Simplified)

There are several elegant proofs of Fermat's Little Theorem. Here are two of the most common approaches, simplified for clarity.

1. Combinatorial Proof (The Necklace Argument) 📿

This proof is intuitive and visual. Imagine you have beads of `a` different colors and you want to make necklaces of length `p`, where `p` is a prime number.

1. The total number of possible strings of `p` beads using `a` colors is `a^p`.
2. Out of these, `a` strings consist of beads of a single color (all red, all blue, etc.). These are the "monochromatic" strings.
3. This leaves `a^p - a` strings that use at least two colors.
4. Now, group these `a^p - a` strings into necklaces. A necklace is formed by joining the ends of a string. Since `p` is a prime number, rotating any non-monochromatic string will give `p` distinct strings. For example, if p=5 and the string is `RGBYR`, its rotations are `GBYRR`, `BYRRG`, etc., and all 5 will be unique.
5. This means the `a^p - a` non-monochromatic strings can be perfectly bundled into groups of `p`. Therefore, `a^p - a` must be divisible by `p`.
6. In modular arithmetic terms, this is written as: `a^p - a ≡ 0 (mod p)`, which simplifies to `a^p ≡ a (mod p)`.
7. If `a` is not divisible by `p`, we can divide both sides by `a` to get the more common form: `a^(p-1) ≡ 1 (mod p)`.

2. Proof using Modular Arithmetic and Group Theory 🔢

This proof is more formal and relies on properties of modular arithmetic.

1. Consider the set of `p-1` integers: `{1, 2, 3, ..., p-1}`. These are the non-zero residues modulo `p`.
2. Let `a` be an integer not divisible by `p`. Multiply each element in the set by `a` and take the result modulo `p`: `{a mod p, 2a mod p, ..., (p-1)a mod p}`.
3. We can prove that this new set is just a permutation of the original set `{1, 2, ..., p-1}`. No element is 0 (since `p` is prime and doesn't divide `a` or any number from 1 to p-1), and all elements are distinct.
4. Since the sets are the same, the product of their elements must also be the same modulo `p`.
   `(1 * 2 * ... * (p-1)) ≡ (a * 2a * ... * (p-1)a) (mod p)`
5. This simplifies to: `(p-1)! ≡ a^(p-1) * (p-1)! (mod p)`.
6. Since `(p-1)!` is not divisible by `p` (as it's a product of numbers less than the prime `p`), we can "cancel" it from both sides.
7. This leaves us with the desired result: `1 ≡ a^(p-1) (mod p)`.

Our Fermat's Little Theorem calculator with steps uses an algorithm called modular exponentiation (or exponentiation by squaring) to efficiently compute these large powers, which is a practical application of these theoretical principles.

⚙️ How to Solve Fermat's Little Theorem Problems: Examples

Fermat's Little Theorem is incredibly useful for simplifying calculations involving large exponents and modular arithmetic. Let's see some Fermat's Little Theorem examples.

Example 1: Using Fermat's Little Theorem to Find a Remainder

Problem: Find the remainder when `7^100` is divided by 13.

• Here, `a = 7` and `p = 13`. Since 13 is prime and does not divide 7, we can apply the theorem.
• The theorem states: `7^(13-1) ≡ 7^12 ≡ 1 (mod 13)`.
• We can use this fact to simplify the exponent 100. We write `100` in terms of `12`: `100 = 12 * 8 + 4`.
• So, `7^100 = 7^(12*8 + 4) = (7^12)^8 * 7^4`.
• Now, apply the modulus: `(7^12)^8 * 7^4 ≡ (1)^8 * 7^4 (mod 13)`.
• This simplifies to `7^4 (mod 13)`. This is a much smaller calculation.
• `7^2 = 49 ≡ 10 (mod 13)`.
• `7^4 = (7^2)^2 ≡ 10^2 = 100 (mod 13)`.
• To find `100 mod 13`, we see that `13 * 7 = 91`, so `100 - 91 = 9`.
• Therefore, `7^100 ≡ 9 (mod 13)`. The remainder is 9.

Example 2: Finding a Multiplicative Inverse

Problem: Find the multiplicative inverse of 3 modulo 17.

• We are looking for a number `x` such that `3x ≡ 1 (mod 17)`.
• Fermat's Little Theorem states `3^(17-1) ≡ 3^16 ≡ 1 (mod 17)`.
• We can rewrite `3^16` as `3 * 3^15`.
• So, `3 * 3^15 ≡ 1 (mod 17)`.
• Comparing this with `3x ≡ 1 (mod 17)`, we see that `x = 3^15 (mod 17)`.
• Calculating `3^15 mod 17` (which our fermat's little theorem calculator mod can do instantly) gives `6`.
• Thus, the multiplicative inverse of 3 mod 17 is 6. Check: `3 * 6 = 18 ≡ 1 (mod 17)`. Correct!

🌐 Applications of Fermat's Little Theorem

This theorem isn't just a mathematical curiosity; it has profound practical applications.

1. Cryptography (Fermat's Little Theorem in RSA) 🔐

The most famous application is in public-key cryptography, particularly the RSA algorithm. While RSA relies more directly on Euler's generalization, Fermat's Little Theorem is the conceptual stepping stone.

In RSA, a public key `(e, n)` and a private key `(d, n)` are generated. A message `M` is encrypted as `C = M^e (mod n)` and decrypted as `M = C^d (mod n)`. The relationship between `e` and `d` is `ed ≡ 1 (mod φ(n))`, where `φ(n)` is Euler's totient function. If `n = pq` where `p` and `q` are prime, then `φ(n) = (p-1)(q-1)`. The security of RSA relies on the difficulty of factoring the large number `n` to find `p` and `q`.

2. Primality Testing 🔍

Fermat's Little Theorem can be used as a basis for a primality test. To test if a number `p` is prime, we can pick a random integer `a` and check if `a^(p-1) ≡ 1 (mod p)`. If it's not, then `p` is definitely composite.
However, if it is, `p` is *probably* prime. This test is not foolproof. There exist composite numbers called Carmichael numbers (e.g., 561) that satisfy the congruence for all `a` coprime to them, making them appear prime to this test. More sophisticated tests like Miller-Rabin are used in practice.

🌍 Euler's Generalization of Fermat's Little Theorem

Leonhard Euler extended Fermat's work to create a more general theorem that works for any modulus `n`, not just primes. This 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`. For a prime `p`, `φ(p) = p-1`, as all numbers from 1 to `p-1` are relatively prime to it.

Euler's theorem states that for any integer `a` that is relatively prime to `n` (`gcd(a, n) = 1`):

a^φ(n) ≡ 1 (mod n)

You can see how this is a direct generalization. If `n` is a prime `p`, `φ(p) = p-1`, and Euler's theorem becomes `a^(p-1) ≡ 1 (mod p)`, which is exactly Fermat's Little Theorem.

🧰 Bonus Utility Tools

💖 Support Our Work

If you find this tool useful, please consider a small donation. It helps us maintain and develop more free, high-quality tools for everyone.

Donate via UPI (India)

Scan the QR code with your UPI app.

Donate via UPI

Support via PayPal

Use PayPal for international contributions.

Donate via PayPal