Fermat's Little Theorem Explained: Modular Arithmetic Applications

Understanding Fermat's Little Theorem

Fermat's Little Theorem (FLT) states: If p is prime and a isn't divisible by p, then a^p-1 ≡ 1 mod p. This foundational number theory concept revolutionizes modular exponentiation calculations. After analyzing this video lecture, I recognize students often struggle with its computational implementation. Let's bridge that gap.

Core theorem mechanics

The theorem's power emerges from its rearrangement: a^p ≡ a mod p. This equivalence enables efficient computation of large exponents. Consider p=7 and a=3:
3⁶ = 729
729 ÷ 7 = 104 with remainder 1 → 729 ≡ 1 mod 7

The video correctly emphasizes that FLT only applies when p is prime and a isn't a multiple of p. Industry-standard references like Rosen's Discrete Mathematics confirm this constraint prevents division by zero in modular inverse calculations.

Wilson's Theorem connection

Wilson's Theorem states: (p-1)! ≡ -1 mod p for prime p. This synergizes with FLT as shown in combinatorial proofs. For example:
When p=5:
(5-1)! = 24
24 mod 5 = 4 ≡ -1 mod 5

This relationship is frequently tested in exams like JEE and GRE. The video's demonstration of factorial cancellation patterns reveals why these theorems share conceptual DNA.

Practical Computation Techniques

Binary exponentiation method

For calculating a^k mod p:

1. Convert exponent k to binary
2. Compute successive squares: a², a⁴, a⁸ mod p
3. Multiply results corresponding to binary 1s

Example: 5¹³ mod 11
13 = 1101₂ → Use 5⁸, 5⁴, 5¹
5¹ ≡ 5, 5² ≡ 3, 5⁴ ≡ 3² ≡ 9, 5⁸ ≡ 9² ≡ 81 ≡ 4 mod 11
5¹³ ≡ 4 × 9 × 5 ≡ 180 ≡ 4 mod 11

This method reduces O(n) operations to O(log n). Practice shows students gain 3x speed improvement in exams using this technique.

Modular inverse calculation

FLT enables inverse finding via a^-1 ≡ a^p-2 mod p. For 3^-1 mod 7:
3⁵ = 243 ≡ 5 mod 7 → 5 ≡ inverse of 3 since 3×5=15≡1 mod 7

Common pitfalls:

• Forgetting primality check (non-prime p breaks FLT)
• Missing a ≠ 0 mod p requirement
• Calculation errors in binary exponentiation steps

Advanced Applications and Problem Solving

nCr mod p computation

To compute combinations mod prime:

1. Use n! / (r! × (n-r)!) mod p
2. Convert to n! × [r!]^-1 × [(n-r)!]^-1 mod p
3. Apply FLT for inverse calculations

Case study: 5C2 mod 7
Numerator: 5! = 120
Denominator: 2! × 3! = 2 × 6 = 12
120 × 12^-1 mod 7
12 ≡ 5 mod 7 → inverse is 3 (since 5×3=15≡1)
120 ≡ 1 mod 7 → 1 × 3 = 3

The video correctly warns against direct factorial computation for large n. My experience confirms precomputing modular inverses saves critical time.

Real-world extensions

Beyond exams, FLT underpins RSA encryption. The video doesn't mention that FLT's exponentiation efficiency enables secure key exchange. When p exceeds 1024 bits, binary exponentiation becomes essential for feasible computation.

Implementation Checklist

1. Verify primality with trial division or probabilistic tests
2. Check a ≢ 0 mod p before applying FLT
3. Use binary exponentiation for powers exceeding 10⁶
4. Precompute factorials for combinatorial problems
5. Validate results with small test cases

Recommended Resources

• Textbook: Elementary Number Theory by David Burton (theorem proofs with historical context)
• Tool: Modular Arithmetic Calculator (ideal for beginners verifying hand calculations)
• Platform: Project Euler (advanced problems combining FLT with programming)

Conclusion

Fermat's Little Theorem transforms impossible computations into manageable tasks through modular reduction. Which application area do you find most challenging—combinatorics or cryptography? Share your approach in the comments!