Prime Factorization

Prime factorization is the process of breaking down a number into its prime factors. Every integer > 1 can be uniquely expressed as a product of prime numbers.

Example: 60 = 2² × 3 × 5

This theorem states that every integer greater than 1 can be uniquely represented as a product of prime numbers (ignoring order).

This means no matter how you factor a number, you'll always get the same prime factors. This tool demonstrates this with multiple factor tree paths.

A factor tree starts with your number at the top and branches down into factors until you reach only prime numbers.

1. Start at the top with your number
2. Each branch shows two factors that multiply to the number above
3. Continue branching until all leaves are prime (shown in green)
4. Collect all the prime leaves - these are your prime factors

To find the GCD using prime factorization:

1. Factor each number into primes
2. For each prime, take the minimum power that appears in all numbers
3. Multiply these together

Example: GCD(48, 60)

• 48 = 2⁴ × 3
• 60 = 2² × 3 × 5
• GCD = 2^min(4,2) × 3^min(1,1) = 2² × 3 = 12

To find the LCM using prime factorization:

1. Factor each number into primes
2. For each prime, take the maximum power that appears in any number
3. Multiply these together

Example: LCM(48, 60)

• 48 = 2⁴ × 3
• 60 = 2² × 3 × 5
• LCM = 2^max(4,2) × 3^max(1,1) × 5 = 2⁴ × 3 × 5 = 240

From the prime factorization, you can generate all divisors by taking all possible combinations of the prime powers.

Example: 60 = 2² × 3 × 5

Divisors are products of 2^a × 3^b × 5^c where:

• a ∈ {0, 1, 2}
• b ∈ {0, 1}
• c ∈ {0, 1}

Number of divisors = (2+1)(1+1)(1+1) = 12