🎭 The Secret Factory of Numbers: Factorials and Primes
The Story Begins…
Imagine a giant cookie factory. Every day, the factory makes cookies numbered 1, 2, 3, 4, 5… and so on. One special day, they decide to multiply ALL the cookies together from 1 to some number.
That’s what a factorial is!
5! = 5 × 4 × 3 × 2 × 1 = 120
We write it with an exclamation mark because it’s exciting! 🎉
🍪 Part 1: Binomial Divisibility
What’s a Binomial Coefficient?
Think of it like this: You have 5 friends, and you want to pick 2 to play on your team.
How many different pairs can you make? That’s written as:
C(5,2) = 5! ÷ (2! × 3!) = 10
The Magic Rule
Here’s a cool secret: Binomial coefficients are ALWAYS whole numbers!
Even though we’re dividing factorials, the answer is never a fraction.
Why? Because when you pick things from a group, you always get a complete count!
Example:
C(6,2) = 6! ÷ (2! × 4!)
= 720 ÷ (2 × 24)
= 720 ÷ 48
= 15 ✓ (a whole number!)
When Does a Prime Divide C(n,k)?
A prime p divides C(n,k) when there’s “borrowing” in the subtraction n - k written in base p.
Simple Version: If you write n and k in prime-base digits, and k needs to “borrow” from n during subtraction, then p divides C(n,k).
🔍 Part 2: Legendre’s Formula - The Prime Counter
The Big Question
How many times does a prime number appear inside a factorial?
Example: How many 2s are hiding in 10!?
Legendre’s Magic Formula
Count it step by step:
- Divide by the prime
- Divide by prime²
- Divide by prime³
- Keep going until you get 0
- Add them all up!
graph TD A["10! has how many 2s?"] --> B["10 ÷ 2 = 5"] B --> C["10 ÷ 4 = 2"] C --> D["10 ÷ 8 = 1"] D --> E["10 ÷ 16 = 0"] E --> F["Total: 5+2+1 = 8"]
The Formula
For prime p in n!:
Count = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …
The ⌊ ⌋ means “round down” (floor).
Real Example: 2s in 10!
| Step | Calculation | Result |
|---|---|---|
| ÷2 | 10÷2 | 5 |
| ÷4 | 10÷4 | 2 |
| ÷8 | 10÷8 | 1 |
| ÷16 | 10÷16 | 0 ✓ |
| Total | 8 |
10! = 3,628,800 = 2⁸ × (other stuff)
Another Example: 3s in 20!
| Step | Calculation | Result |
|---|---|---|
| ÷3 | 20÷3 | 6 |
| ÷9 | 20÷9 | 2 |
| ÷27 | 20÷27 | 0 ✓ |
| Total | 8 |
🔢 Part 3: Trailing Zeros - The Zero Hunt!
What Are Trailing Zeros?
Trailing zeros are the zeros at the END of a number.
100 has 2 trailing zeros 5000 has 3 trailing zeros 120 has 1 trailing zero
Where Do They Come From?
Every trailing zero comes from multiplying by 10.
And 10 = 2 × 5
So every trailing zero needs one 2 AND one 5!
The Secret
In factorials, we always have MORE 2s than 5s.
So just count the 5s!
graph TD A["Trailing zeros in n!"] --> B["Count the 5s"] B --> C["Use Legendre for prime 5"] C --> D["⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋..."]
Example: Trailing Zeros in 100!
| Step | Calculation | Result |
|---|---|---|
| ÷5 | 100÷5 | 20 |
| ÷25 | 100÷25 | 4 |
| ÷125 | 100÷125 | 0 ✓ |
| Total | 24 |
100! ends with exactly 24 zeros!
Quick Practice
How many trailing zeros in 50!?
- 50 ÷ 5 = 10
- 50 ÷ 25 = 2
- 50 ÷ 125 = 0
Answer: 12 trailing zeros!
🎯 The Connection: All Three Together
graph TD A["FACTORIAL n!"] --> B["Legendre's Formula"] B --> C["Count any prime p"] C --> D["For p=5: Trailing Zeros"] A --> E["Binomial C#40;n,k#41;"] E --> F["Always divides evenly"] F --> G["Prime divisibility patterns"]
Why This Matters
- Cryptography uses these prime patterns
- Computer science uses modular arithmetic
- Competition math loves these problems!
🌟 Quick Summary
| Concept | What It Does | Formula |
|---|---|---|
| Binomial | Counts combinations | C(n,k) = n!/(k!(n-k)!) |
| Legendre | Counts primes in n! | ⌊n/p⌋ + ⌊n/p²⌋ + … |
| Trailing Zeros | Counts zeros at end | Just count the 5s! |
🎮 Try This!
Question: How many trailing zeros does 1000! have?
Solution:
- 1000 ÷ 5 = 200
- 1000 ÷ 25 = 40
- 1000 ÷ 125 = 8
- 1000 ÷ 625 = 1
- 1000 ÷ 3125 = 0
Answer: 200 + 40 + 8 + 1 = 249 zeros!
You now know how to:
- ✅ Understand why binomials are always whole numbers
- ✅ Count primes hiding in any factorial
- ✅ Calculate trailing zeros instantly
You’re a factorial detective now! 🕵️♀️