Overview
This lecture focuses on factorials, including their definition, properties, prime factorization, calculation of highest powers, and trailing zeros in factorials.
Definition and Basics of Factorials
- n factorial (n!) is the product of all positive integers from 1 to n.
- 0 factorial (0!) is defined as 1.
Prime Factorization of Factorials
- To find the number of factors of n!, express n! as a product of its prime factors.
- Each prime up to n appears in the prime factorization with various powers.
Highest Power of a Prime in n!
- The highest power of a prime p in n! is found by summing ⎣n/p⎦ + ⎣n/p²⎦ + ⎣n/p³⎦ + ... until the quotient is zero.
- Example: Highest power of 2 in 15! is 7 + 3 + 1 = 11.
Calculating the Highest Power for Non-prime Numbers
- For a composite number k, break it into primes: k = p₁^a × p₂^b × ... .
- The highest power of k in n! is min(floor(power of p₁ in n! / a), floor(power of p₂ in n! / b), ...).
- Example: For 6 in 60!, calculate the highest powers of 2 and 3, and take the minimum.
Trailing Zeros in Factorials
- Trailing zeros in n! equal the highest power of 10 in n!.
- Since 10 = 2 × 5, trailing zeros are determined by the number of times 5 appears in the prime factorization (since there are always more 2s).
- Example: Number of trailing zeros in 100! is 24 (from 5^24).
Patterns and Shortcuts
- As the prime number increases, its highest power in n! decreases.
- For numbers like 10, 6, or other composites, focus on the lower-count prime factor when counting occurrences in n!.
Key Terms & Definitions
- Factorial (n!) — Product of all positive integers from 1 to n.
- Prime Factorization — Expressing a number as a product of prime numbers.
- Highest Power — The largest exponent of a given prime dividing n!.
- Trailing Zeros — The number of zeros at the end of n! due to factors of 10.
Action Items / Next Steps
- Practice problems on highest powers of primes and trailing zeros in factorials.
- Review the concept of breaking composite numbers into primes for such calculations.