Lecture Notes on Factorials and Prime Factors

Introduction

• Presented by Ravi Prakash.
• Focus on factorials in the context of numbers.

Key Concepts

1. Factorials

   • Definition: Multiplication of all positive integers up to n.
   • Notation: n! = 1 × 2 × 3 × ... × n.
   • Example: 5! = 120.
   • Special case: 0! = 1.

2. Finding Number of Factors

   • Example: Find factors of 15! by breaking it down into prime factors.
   • Identify prime factors up to 15: 2, 3, 5, 7, 11, 13.
   • Count occurrences of each prime factor in 15!:
     • 2 occurs 11 times, 3 occurs 6 times, 5 occurs 3 times, 7 occurs 2 times, 11 occurs 1 time, 13 occurs 1 time.
   • Number of factors formula: (e1 + 1)(e2 + 1)(e3 + 1)..., where ei is the power of the i-th prime.
   • Example calculation yields 336 factors for 15!.

Highest Power of Prime Factors in Factorials

1. Calculating Highest Power

   • Example: Highest power of 2 in 15!.
   • Method: Successively divide by 2 and count how many times.
     • 15 ÷ 2 = 7 (7 times)
     • 7 ÷ 2 = 3 (3 times)
     • 3 ÷ 2 = 1 (1 time)
   • Total: 11.

2. Finding Highest Power of a Prime

   • Example for a non-prime number (e.g., 6) in 60!:
   • Break down into prime factors: 6 = 2 × 3.
   • Calculate highest power of 2 and 3 separately.
   • Use the minimum of the two to find the highest power of 6.

Example Calculations

• Highest power of 3 in 60!: 20 + 6 + 2 = 28.
• Highest power of 5 in 60!: 60 ÷ 5 = 12 + 60 ÷ 25 = 2 = 14.
• Leading to the conclusion that highest power of 10 in 60! depends on the number of 5s.

Trailing Zeros

1. Definition: The number of trailing zeros in a factorial is determined by the number of 10s in the factorization.

   • 10 = 2 × 5.
   • In any factorial, 2s will outnumber 5s.
   • Therefore, trailing zeros = highest power of 5.

2. Calculation

   • Example: Find trailing zeros in 100!.
   • Step through divisions by 5:
     • 100 ÷ 5 = 20 + 100 ÷ 25 = 4 = 24.
   • Result: 24 trailing zeros.

Summary

• Factorials are foundational in combinatorics and number theory.
• The process of finding prime factors and their powers in factorials is crucial for solving complex problems involving combinations, permutations, and trailing zeros.