Fermat's little theorem (statement)

Statement of the Theorem

What Each Part Means

$p$ is prime: This theorem only works for primes. Try $p = 4$ (composite) with $a = 2$ : we get $2^{3} = 8 \equiv 0 \pmod{4}$ , not1.
$\gcd(a, p) = 1$ : The number $a$ must be coprime to $p$ . If $a$ is a multiple of $p$ , then $a^{p-1} \equiv 0 \pmod{p}$ , not 1.
$a^{p-1} \equiv 1 \pmod{p}$ : When you compute $a^{p-1}$ and divide by $p$ , the remainder is exactly 1.

Building the Intuition: Why Would This Be True?

Formula Intuitive Path (Not a Proof, Just Direction)

Question: Why does raising to power $(p-1)$ give us 1 modulo $p$ ? Hint from multiplication tables: Consider the numbers $\{1, 2, 3, \ldots, p-1\}$ modulo $p$ . When we multiply all of them by some $a$ coprime to $p$ , we get the same set just rearranged (this is because multiplication by $a$ is a bijection in modular arithmetic when $\gcd(a,p)=1$ ). So: $\{a \cdot 1, a \cdot 2, \ldots, a \cdot (p-1)\} \equiv \{1, 2, \ldots, p-1\} \pmod{p}$

Multiplying all elements on both sides: $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$ Since $(p-1)!$ is coprime to $p$ (none of $1, 2, \ldots, p-1$ share a factor with prime $p$ ), we can "cancel" it, leaving: $a^{p-1} \equiv 1 \pmod{p}$

(Full rigorous proof comes from group theory—Lagrange's theorem applied to $(\mathbb{Z}/p\mathbb{Z})^*$ —but this gives the flavor.)

Worked Examples

Worked example Example 2: Simplifying Large Exponents

Problem: Find $7^{222} \bmod 11$ .

Solution:

$p = 11$ is prime, $a = 7$ , and $\gcd(7, 11) = 1$ ✓
By FLT: $7^{10} \equiv 1 \pmod{11}$ Step 1: Express222 in terms of 10: $222 = 10 \cdot 22 + 2$ Why this step? We want to "extract" as many copies of $7^{10}$ as possible since each equals1.

Step 2: Rewrite the exponent: $7^{222} = 7^{10 \cdot 22 + 2} = (7^{10})^{22} \cdot 7^2$

Step 3: Apply FLT: $(7^{10})^{22} \equiv 1^{22} \equiv 1 \pmod{11}$

Step 4: Compute the remainder: $7^{222} \equiv 1 \cdot 7^2 \equiv 49 \pmod{11}$ $49 = 4 \cdot 11 + 5$ $\boxed{7^{222} \equiv 5 \pmod{11}}$

Why this is powerful: Without FLT, computing $7^{222}$ directly would require222 multiplications. FLT reduces it to a single small calculation.

Common Mistakes & How to Avoid Them

Key Formulas & When to Use Them

Applications Preview

Modular Inverses: To find $a^{-1} \bmod p$ , compute $a^{p-2} \bmod p$ (since $a \cdot a^{p-2} = a^{p-1} \equiv 1$ ).
Fast Exponentiation: Computing $a^n \bmod p$ becomes efficient: reduce $n \bmod (p-1)$ first.
Primality Testing: If $a^{p-1} \not\equiv 1 \pmod{p}$ for coprime $a$ , then $p$ is definitely composite (though the converse isn't always true—leads to Fermat pseudoprimes).
RSA Encryption: The security of RSA relies on a generalization of FLT (Euler's theorem).

Recall Explain to a 12-Year-Old

Imagine you have a special clock that only goes up to a prime number of hours—say 5 hours. Now, pick any number that doesn't land exactly on one of the hour marks when you divide evenly (like 3).

Fermat discovered something magical: if you keep multiplying your number by itself exactly $(5-1) = 4$ times, and then see where you land on the clock, you'll always end up back at 1o'clock!

So $3 \times 3 \times 3 \times 3 = 81$ . If we go around our5-hour clock, 81 hours later is the same as 1 o'clock (since $81 = 16 \times 5 + 1$ ).

This only works when your clock has a prime number of hours. If it's 4 hours (not prime), the magic breaks. That's why primes are special—they have this hidden pattern that regular numbers don't.

Connections

Modular Arithmetic Basics - prerequisite for understanding $a^{p-1} \equiv 1 \pmod{p}$
Properties of Prime Numbers - why this theorem is exclusive to primes
Euler's Totient Function - generalizes FLT to composite moduli via Euler's theorem
Wilson's Theorem - another special property of primes involving $(p-1)!$
Carmichael Numbers - composites that "fake" Fermat's theorem for all bases
Multiplicative Group Modulo Prime - the group theory foundation ( $(\mathbb{Z}/p\mathbb{Z})^*$ has order $p-1$ )
Modular Exponentiation Algorithms - using FLT to speed up computations
RSA Cryptosystem - relies on generalizing FLT for security

#flashcards/maths

What does Fermat's Little Theorem state for a prime p and integer a where gcd(a,p)=1? :: $a^{p-1} \equiv 1 \pmod{p}$

What are the two conditions required for the classical form of Fermat's Little Theorem?

(1)

p

must be prime, (2)

\gcd(a, p) = 1

(a is coprime to p)

What is the alternative form of Fermat's Little Theorem that works for all integers a?

a^p \equiv a \pmod{p}

when

p

is prime

Why does Fermat's Little Theorem fail for composite moduli?

Because theorem relies on the multiplicative group modulo p having exactly p-1 elements, which only happens when p is prime; composite moduli don't have this structure

How can you use FLT to find the modular inverse of a modulo prime p?

a^{-1} \equiv a^{p-2} \pmod{p}

, since

a \cdot a^{p-2} = a^{p-1} \equiv 1 \pmod{p}

If you need to compute

7^{222} \bmod 11

using FLT, what is the first step?

Express 222 as

222 = 10 \cdot 22 + 2

where 10 = p-1, then use

7^{10} \equiv 1 \pmod{11}

to simplify to

7^2 \bmod 11

What mistake do students make when applying FLT to a=6, p=3?

They forget to check

\gcd(6,3) = 3 \neq 1

, so the condition

\gcd(a,p)=1

fails and FLT doesn't apply;

6^2 \equiv 0 \pmod{3}

, not 1

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Fermat's Little Theorem ek bahut hi powerful result hai number theory mein. Iska matlab simple hai:agar apke pas ek prime number $p$ hai aur koi bhi integer $a$ hai jo $p$ se divide nahi hota (matlab $\gcd(a,p) = 1$ ), to jab aap $a$ ko $(p-1)$ baar multiply karke power mein late ho aur phir $p$ se divide karte ho, to remainder hamesha 1 ata hai. Formula yeh hai: $a^{p-1} \equiv 1 \pmod{p}$ .

Yeh theorem isliye important hai kyunki yeh humein bahut bade exponents ko simplify karne mein mad karta hai. For example, agar aapko $7^{222} \bmod 11$ nikalna hai, to seedha calculate karna mushkil hai. Lekin FLT kehta hai ki $7^{10} \equiv 1 \pmod{11}$ (kyunki 11 prime hai aur $11-1=10$ ). Ab222 ko $10 \times 22 + 2$ likh sakte ho, matlab $7^{222} = (7^{10})^{22} \cdot 7^2 \equiv 1^{22} \cdot 49 \equiv 5 \pmod{11}$ . Kitna asaan ho gaya!

Yeh theorem cryptography (RSA jaise systems), primality testing (kya yeh number prime hai check karne ke liye), aur modular arithmetic problems mein extensively use hota hai.Ek important baat yad rakhni hai: yeh sirf prime modulus ke liye kaam karta hai.Agar aap composite number jaise 4 ya 6 pe apply karoge, to galat answer ayega. Aur dusri condition yeh hai ki $a$ aur $p$ coprime hone chahiye—yani unka GCD exactly 1 hona chahiye. Agar $a$ already $p$ ka multiple hai, to $a^{p-1}$ zero hoga, ek nahi.

Statement of the Theorem

What Each Part Means

Building the Intuition: Why Would This Be True?

Worked Examples

Common Mistakes & How to Avoid Them

Key Formulas & When to Use Them

Applications Preview

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Number Theory (Intermediate)

Connections