AI summary by TwinMind
The Freshman's Dream (a classic mistake) - Numberphile
Numberphile
20m 20s
Introduction to the Freshman's Dream
- Common algebraic mistake: (a + b)² = a² + b²
- Named "freshman's dream" - term less than 100 years old
- Has own Wikipedia page, regularly made by students
- Variant mistake: √(a + b) = √a + √b
- Both false in regular arithmetic (e.g., (1+1)² = 4 ≠ 1² + 1² = 2)
- Correct expansion: (a + b)² = a² + 2ab + b² (FOIL method)
- Freshman's dream forgets middle term 2ab
Clock Arithmetic Introduction
- Clock arithmetic treats numbers same if they differ by clock size
- 12-hour clock: 1:00 = 13:00, 12:00 = 24:00 = 36:00
- Fast forward 50 hours = increase by 2 hours (not 50)
Two-Clock Arithmetic (Mod 2)
- Only two numbers: odd and even (or 0 and 1)
- 2 = 0 in mod 2 arithmetic
- Middle term 2ab becomes 0, so (a + b)² = a² + b²
- Example: (5 + 4)² = 9² = 81 ≡ 1 (mod 2)
- 5² + 4² = 25 + 16 = 41 ≡ 1 (mod 2)
- Square root variant also works in mod 2
Three-Clock Arithmetic (Mod 3)
- Uses cubes instead of squares: (a + b)³ = a³ + b³
- 3 ≡ 0 (mod 3), so middle terms vanish
- Normal expansion: (a + b)³ = a³ + 3a²b + 3ab² + b³
- Coefficients 3 become 0 in mod 3
Pascal's Triangle and Binomial Expansion
- Pascal's triangle construction: start with 1, add adjacent numbers
- Rows: [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1], [1,5,10,10,5,1]
- Binomial expansion: (a + b)ⁿ = Σ(n choose k)aⁿ⁻ᵏbᵏ
- Coefficients are binomial coefficients: n choose k = n!/(k!(n-k)!)
When Freshman's Dream Works
- Works for prime moduli: mod 2, mod 3, mod 5
- (a + b)⁵ = a⁵ + 5a⁴b + 10a³b² + 10a²b³ + 5ab⁴ + b⁵
- In mod 5: coefficients 5, 10 become 0
- Fails for composite numbers like mod 6
- Example failure: (1 + 1)⁶ = 64 ≡ 4 (mod 6), but 1⁶ + 1⁶ = 2
Mathematical Proof for Primes
- For prime p, all middle binomial coefficients (p choose k) divisible by p
- Proof uses unique factorization of integers
- p choose k = p!/(k!(p-k)!)
- Since p divides p! but not k! or (p-k)! (for 0 < k < p), p must divide the coefficient
- This explains why freshman's dream works exactly for prime moduli
Fermat's Little Theorem
- For prime p: aᵖ ≡ a (mod p)
- Distinguished from Fermat's Last Theorem
- Used in RSA encryption and cryptography
- Example verification: 4⁷ ≡ 4 (mod 7)
- 4² = 16 ≡ 2 (mod 7)
- 4⁴ = (4²)² ≡ 2² = 4 (mod 7)
- 4⁷ = 4⁴ × 4³ ≡ 4 × 2³ = 4 × 8 ≡ 4 × 1 = 4 (mod 7)
Applications of Modular Arithmetic
- Prevents computer overflow/timeout issues
- Binary arithmetic (mod 2)
- Computer systems use modular arithmetic for efficiency
- Real-world cryptographic applications
- Makes large number computations manageable
- Example: working with numbers up to Graham's number on huge modular clock
Primality Testing Example
- Testing number 341 with base 3
- 3⁴¹ - 3 divisible test mentioned (appears to fail)
