Fermat's little theorem (statement) — Hinglish notes

2.5.11 · Maths › Number Theory (Intermediate)

Statement of the Theorem

Har Part Ka Matlab

$p$ is prime: Yeh theorem sirf primes ke liye kaam karta hai. $p = 4$ (composite) aur $a = 2$ try karo: hum paate hain $2^{3} = 8 \equiv 0 (mod 4)$ , 1 nahi.
$g cd (a, p) = 1$ : Number $a$ , $p$ ke saath coprime hona chahiye. Agar $a$ , $p$ ka multiple hai, toh $a^{p - 1} \equiv 0 (mod p)$ hoga, 1 nahi.
$a^{p - 1} \equiv 1 (mod p)$ : Jab tum $a^{p - 1}$ compute karte ho aur $p$ se divide karte ho, remainder exactly 1 aata hai.

Intuition Build Karna: Yeh Sach Kyun Hoga?

Formula Intuitive Path (Proof Nahi, Sirf Direction)

Sawaal: Power $(p - 1)$ tak uthane par $p$ modulo mein 1 kyun milta hai? Multiplication tables se hint: ${1, 2, 3, \dots, p - 1}$ modulo $p$ ke numbers consider karo. Jab hum inhe kisi $a$ se multiply karte hain jo $p$ ke saath coprime hai, toh hum wohi set paate hain, bas re-arranged (yeh isliye hai kyunki $a$ se multiplication ek bijection hai modular arithmetic mein jab $g cd (a, p) = 1$ ). Toh: ${a \cdot 1, a \cdot 2, \dots, a \cdot (p - 1)} \equiv {1, 2, \dots, p - 1} (mod p)$

Dono taraf ke saare elements ko multiply karne par: $a^{p - 1} \cdot (p - 1)! \equiv (p - 1)! (mod p)$ Kyunki $(p - 1)!$ , $p$ ke saath coprime hai ( $1, 2, \dots, p - 1$ mein se koi bhi prime $p$ ke saath koi factor share nahi karta), hum ise "cancel" kar sakte hain, aur milta hai: $a^{p - 1} \equiv 1 (mod p)$

(Full rigorous proof group theory se aati hai—Lagrange's theorem $(Z / p Z)^{*}$ par apply hoti hai—lekin yeh uska flavor deta hai.)

Worked Examples

Common Mistakes aur Unhe Kaise Bachein

Key Formulas aur Kab Use Karein

Applications Preview

Modular Inverses: $a^{- 1} mod p$ nikalne ke liye, $a^{p - 2} mod p$ compute karo (kyunki $a \cdot a^{p - 2} = a^{p - 1} \equiv 1$ ).
Fast Exponentiation: $a^{n} mod p$ compute karna efficient ban jaata hai: pehle $n mod (p - 1)$ reduce karo.
Primality Testing: Agar coprime $a$ ke liye $a^{p - 1} \neq \equiv 1 (mod p)$ hai, toh $p$ definitely composite hai (lekin converse hamesha sach nahi hota—yeh Fermat pseudoprimes ki taraf le jaata hai).
RSA Encryption: RSA ki security FLT ke ek generalization (Euler's theorem) par rely karti hai.

Recall Ek 12-Saal Ke Bacche Ko Explain Karo

Socho tumhare paas ek special clock hai jo sirf prime number of hours tak jaati hai—maano 5 ghante. Ab koi bhi number lo jo divide karne par exactly ghante ke nishaan par nahi padta (jaise 3).

Fermat ne kuch magical discover kiya: agar tum apne number ko khud se exactly $(5 - 1) = 4$ baar multiply karo, aur phir dekho ki clock par kahan pahunche, tum hamesha 1 baje par wapas aoge!

Toh $3 \times 3 \times 3 \times 3 = 81$ . Agar hum apni 5-ghante wali clock par jayein, 81 ghante baad 1 baje jaisa hi hoga (kyunki $81 = 16 \times 5 + 1$ ).

Yeh sirf tab kaam karta hai jab tumhari clock mein prime number of hours hon. Agar 4 ghante hon (prime nahi), toh magic toot jaata hai. Isliye primes special hain—unmein ek hidden pattern hota hai jo regular numbers mein nahi hota.

Connections

Modular Arithmetic Basics - $a^{p - 1} \equiv 1 (mod p)$ samajhne ke liye prerequisite
Properties of Prime Numbers - kyun yeh theorem sirf primes ke liye hai
Euler's Totient Function - FLT ko composite moduli tak generalize karta hai Euler's theorem ke through
Wilson's Theorem - primes ki ek aur special property jo $(p - 1)!$ se related hai
Carmichael Numbers - composites jo saare bases ke liye Fermat's theorem "fake" karte hain
Multiplicative Group Modulo Prime - group theory foundation ( $(Z / p Z)^{*}$ ka order $p - 1$ hai)
Modular Exponentiation Algorithms - computations speed up karne ke liye FLT use karna
RSA Cryptosystem - security ke liye FLT ko generalize karne par rely karta hai

#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 (mod p)$

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

(1)

p

must be prime, (2)

g cd (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 (mod 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} (mod p)

, since

a \cdot a^{p - 2} = a^{p - 1} \equiv 1 (mod p)

If you need to compute

7^{222} mod 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 (mod 11)

to simplify to

7^{2} mod 11

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

They forget to check

g cd (6, 3) = 3 \neq = 1

, so the condition

g cd (a, p) = 1

fails and FLT doesn't apply;

6^{2} \equiv 0 (mod 3)

, not 1