Topic 7 of 10

Prime Numbers

🎯 Learning Objectives

8.1 Definition

🔑 Prime Number

A number p is prime if:

  • It has exactly two factors: 1 and p
  • p ≠ 1 (1 is NOT prime - it only has one factor)

First Few Prime Numbers

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47

⚠️ Important Facts

  • First Prime: 2 (the only even prime)
  • After 2: All even numbers are composite (divisible by 2)
  • Why 1 is NOT prime: factors(1) = {1} (only one factor, but prime requires exactly TWO factors)

8.2 Sieve of Eratosthenes

Algorithm to Find Primes up to n

  1. List all numbers from 2 to n
  2. Start with first number (2)
  3. Mark 2 as prime
  4. Cross out all multiples of 2
  5. Find next unmarked number (3)
  6. Mark 3 as prime
  7. Cross out all multiples of 3
  8. Repeat until reaching √n

🎨 Interactive Sieve of Eratosthenes

Click the buttons to see the sieve in action (finding primes up to 50):

Status: Ready to start

Visual Example (finding primes up to 100)

2 [crossed: 4, 6, 8, 10, 12, 14, 16, 18, 20, ...] 3 [crossed: 9, 15, 21, 27, 33, 39, 45, 51, ...] 5 [crossed: 25, 35, 45, 55, 65, 75, 85, 95, ...] 7 [crossed: 49, 77, 91, ...] Remaining primes up to 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

8.3 Prime Factorization

🏛️ Fundamental Theorem of Arithmetic

Every integer greater than 1 can be decomposed into a UNIQUE product of prime factors

This means every number has exactly one prime factorization (order doesn't matter).

Examples of Prime Factorization

Example 1: 12

12 = 2 × 6 = 2 × (2 × 3) = 2² × 3

Example 2: 126

126 = 2 × 63 = 2 × (3 × 21) = 2 × 3 × (3 × 7) = 2 × 3² × 7

Example 3: 360

360 = 2³ × 3² × 5 = 8 × 9 × 5 = 8 × 45

💡 Applications of Prime Factorization

  • Finding GCD: Take minimum powers of common prime factors
  • Simplifying fractions: Cancel common prime factors
  • Understanding divisibility: A number divides another if its prime factors are contained
  • LCM calculation: Take maximum powers of all prime factors

8.4 How Many Primes?

🌟 Theorem: Infinitely Many Primes

There are INFINITELY many prime numbers

Key Insights:

  • No largest prime exists
  • Primes continue forever
  • Gaps between primes can be arbitrarily large

Distribution of Primes

  • Primes become less frequent as numbers get larger
  • But they never stop appearing
  • Between 1-100: 25 primes
  • Between 101-200: 21 primes
  • Between 201-300: 16 primes
  • Between 901-1000: 14 primes

🔍 Interesting Prime Facts

  • Twin Primes: Primes that differ by 2 (like 3,5 or 11,13 or 17,19)
  • Mersenne Primes: Primes of the form 2ⁿ - 1
  • Prime Gaps: The gap between consecutive primes can be as large as we want
  • Goldbach Conjecture: Every even integer > 2 is the sum of two primes (unproven!)

🧮 Practice Problems

Problem 1: Prime Identification

Which of the following numbers are prime?

  1. 17
  2. 21
  3. 29
  4. 39
  5. 41

Solutions:

  1. 17 is PRIME - factors: {1, 17}
  2. 21 is NOT prime - factors: {1, 3, 7, 21} (21 = 3 × 7)
  3. 29 is PRIME - factors: {1, 29}
  4. 39 is NOT prime - factors: {1, 3, 13, 39} (39 = 3 × 13)
  5. 41 is PRIME - factors: {1, 41}

Problem 2: Prime Factorization

Find the complete prime factorization of:

  1. 84
  2. 150
  3. 210

Solutions:

  1. 84 = 2² × 3 × 7
    84 = 4 × 21 = 4 × 3 × 7 = 2² × 3 × 7
  2. 150 = 2 × 3 × 5²
    150 = 2 × 75 = 2 × 3 × 25 = 2 × 3 × 5²
  3. 210 = 2 × 3 × 5 × 7
    210 = 2 × 105 = 2 × 3 × 35 = 2 × 3 × 5 × 7

Problem 3: Using Prime Factorization for GCD

Find the GCD using prime factorization:

  1. gcd(48, 18)
  2. gcd(60, 90)
  3. gcd(84, 126)

Solutions:

  1. gcd(48, 18) = 6
    48 = 2⁴ × 3, 18 = 2 × 3²
    GCD = 2¹ × 3¹ = 6
  2. gcd(60, 90) = 30
    60 = 2² × 3 × 5, 90 = 2 × 3² × 5
    GCD = 2¹ × 3¹ × 5¹ = 30
  3. gcd(84, 126) = 42
    84 = 2² × 3 × 7, 126 = 2 × 3² × 7
    GCD = 2¹ × 3¹ × 7¹ = 42

Problem 4: Sieve of Eratosthenes

Use the Sieve of Eratosthenes to find all prime numbers up to 30. List the steps:

Solution:

Step-by-step process:

  1. Start: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
  2. Mark 2 prime, cross multiples: 2, 3, X, 5, X, 7, X, 9, X, 11, X, 13, X, 15, X, 17, X, 19, X, 21, X, 23, X, 25, X, 27, X, 29, X
  3. Mark 3 prime, cross multiples: 2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, X, 23, X, 25, X, X, X, 29, X
  4. Mark 5 prime, cross multiples: 2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, X, 23, X, X, X, X, X, 29, X
  5. Stop at √30 ≈ 5.5

Final Answer: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

← Previous: Functions 📋 Topics Overview Next: Irrational Numbers →