What is Prime Factorization?
Prime factorization is the process of breaking down a composite number into its prime factors (prime numbers that multiply together to give the original number). Every composite number has a unique prime factorization.
Key Concepts:
- Prime Number: A number greater than 1 with exactly two distinct positive divisors: 1 and itself
- Composite Number: A number greater than 1 that has more than two divisors
- Prime Factor: A prime number that divides a given number exactly
- Fundamental Theorem of Arithmetic: Every integer greater than 1 has a unique prime factorization
- Exponential Form: Prime factors can be written with exponents (e.g., 60 = 2² × 3 × 5)
Prime Factorization Example
Breaking down 60 into prime factors:
30 = 2 × 15
15 = 3 × 5
So: 60 = 2 × 2 × 3 × 5
Or: 60 = 2² × 3 × 5
Why Prime Factorization Matters
Prime factorization is fundamental in number theory and has practical applications:
• Finding GCD and LCM
• Cryptography (RSA)
• Solving Diophantine equations
• Computer algorithms
Unique Factorization
Every composite number has exactly one prime factorization (order doesn't matter).
84 = 2² × 3 × 7
84 = 7 × 3 × 2 × 2
All are the same factorization
Prime Numbers
Prime numbers are the building blocks of all integers. Understanding primes is essential for prime factorization.
Definition of Prime Numbers
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Not prime: 1 (neither prime nor composite)
Not prime: 4 (divisible by 2)
Not prime: 9 (divisible by 3)
Sieve of Eratosthenes
Ancient algorithm for finding all primes up to a given limit.
2. Circle 2, cross out multiples
3. Circle next uncrossed, cross multiples
4. Repeat until n
5. Circled numbers are primes
Prime Number Theorem
Approximately n/ln(n) primes are less than or equal to n.
10/ln(10) ≈ 4.34
Primes ≤ 100: 25
100/ln(100) ≈ 21.7
Twin Primes
Pairs of primes that differ by 2.
(17,19), (29,31), (41,43)
Twin prime conjecture: Infinite pairs exist
Still unproven!
Testing for Primality
Methods to check if a number is prime.
97 is prime?
Test primes ≤ √97 ≈ 9.85
2,3,5,7 don't divide 97
∴ 97 is prime
Prime Factorization of Primes
Prime numbers are their own prime factorization.
13 = 13
29 = 29
Prime numbers have exactly one prime factor: themselves
Factorization Methods
Several methods exist for finding prime factors of a number. Choose based on number size and context.
Trial Division
Divide by primes in increasing order until quotient is 1.
84 ÷ 2 = 42
42 ÷ 2 = 21
21 ÷ 3 = 7
7 ÷ 7 = 1
Factors: 2,2,3,7
Factor Tree Method
Visual method breaking number into factors until all are prime.
/ \
2 30
/ \
2 15
/ \
3 5
Factors: 2,2,3,5
Prime Factorization by Division
Divide by smallest prime factor repeatedly.
2 | 42
3 | 21
7 | 7
| 1
Factors: 2,2,3,7
Using Exponents
Combine repeated factors using exponents.
360 = 2³ × 3² × 5
Compact representation
Easier for calculations
For Large Numbers
Advanced algorithms for very large numbers.
Quadratic sieve
General number field sieve
Used in cryptography
Very computationally intensive
Divisibility Rules
Quick checks to identify possible factors.
Divisible by 3: Sum of digits ÷ 3
Divisible by 5: Last digit 0 or 5
Divisible by 11: Alternating sum ÷ 11
Saves time in trial division
Factor Trees
Factor trees provide a visual representation of the factorization process, making it easier to understand.
Factor Tree: A diagram showing the breakdown of a composite number into its prime factors through successive factorization.
Building a Factor Tree
Start with the number, find two factors, continue until all factors are prime.
/ \
6 8
/ \ / \
2 3 2 4
/ \
2 2
Primes: 2,2,2,2,3
Different Trees, Same Result
Different factor trees give the same prime factors.
/ \ / \
4 12 3 16
/ \ / \ / \
2 2 3 4 4 4
/ \ / \ / \
2 2 2 2 2 2
Both give: 2⁴ × 3
Using Factor Trees for GCF
Compare factor trees to find common factors.
48: 2⁴ × 3
Common: 2² × 3 = 12
GCF(36,48) = 12
Using Factor Trees for LCM
Combine factor trees to find least common multiple.
48: 2⁴ × 3
LCM: 2⁴ × 3² = 144
Take highest powers
LCM(36,48) = 144
Factor Tree Applications
Educational tool for understanding factorization.
• Step-by-step process
• Multiple factorization paths
• Foundation for GCF/LCM
• Prepares for algebra
Optimal Factor Trees
Some trees are more efficient than others.
Better: 100 → 10 × 10
Worse: 100 → 2 × 50
Both correct
First is more symmetric
Divisors & Multiples from Prime Factorization
Prime factorization makes finding divisors and multiples systematic and efficient.
Finding All Divisors
Generate divisors from prime factorization exponents.
Divisors: Combine powers
2⁰3⁰5⁰=1, 2¹3⁰5⁰=2
2²3⁰5⁰=4, 2⁰3¹5⁰=3
2¹3¹5⁰=6, 2²3¹5⁰=12
... 2²3¹5¹=60
Total: (2+1)(1+1)(1+1)=12
Number of Divisors Formula
If n = p₁ᵃ¹ × p₂ᵃ² × ... × pₖᵃᵏ, then number of divisors = (a₁+1)(a₂+1)...(aₖ+1)
Number of divisors:
(2+1)(1+1)(1+1)
= 3 × 2 × 2 = 12
60 has 12 divisors
Sum of Divisors
Formula using prime factorization.
Sum = Π (pᵢᵃⁱ⁺¹ - 1)/(pᵢ - 1)
60 = 2² × 3 × 5
Sum = (2³-1)/(2-1) × (3²-1)/(3-1) × (5²-1)/(5-1)
= 7 × 4 × 6 = 168
Finding Multiples
Multiples contain all prime factors with at least same exponents.
Must have at least 2² and 3¹
24 = 2³ × 3 ✓
36 = 2² × 3² ✓
48 = 2⁴ × 3 ✓
18 = 2 × 3² ✗ (missing 2²)
Perfect Numbers
Numbers where sum of proper divisors equals the number.
Divisors: 1,2,3,6
Proper: 1,2,3
Sum: 1+2+3=6 ✓
28 = 2² × 7
Proper divisors sum to 28
Next: 496, 8128, ...
Abundant & Deficient
Classify numbers by divisor sum.
12: 1+2+3+4+6=16>12
Deficient: Sum < number
8: 1+2+4=7<8
Perfect: Sum = number
6: 1+2+3=6
Greatest Common Divisor & Least Common Multiple
Prime factorization provides efficient methods for finding GCD and LCM.
GCD from Prime Factors
Take smallest power of each common prime.
48 = 2⁴ × 3
Common primes: 2,3
Smallest powers: 2², 3¹
GCD = 2² × 3 = 12
LCM from Prime Factors
Take largest power of each prime present.
48 = 2⁴ × 3
All primes: 2,3
Largest powers: 2⁴, 3²
LCM = 2⁴ × 3² = 144
Relationship: GCD × LCM = a × b
Product of two numbers equals product of their GCD and LCM.
36 × 48 = 1728
GCD × LCM = 12 × 144 = 1728
Useful verification
Also finds one given the other
Euclidean Algorithm
Efficient method for finding GCD without factorization.
48 ÷ 36 = 1 R12
36 ÷ 12 = 3 R0
GCD = 12
Works for large numbers
Much faster than factorization
Applications of GCD
Simplifying fractions, ratio problems, modular arithmetic.
GCD(36,48)=12
36÷12=3, 48÷12=4
36/48 = 3/4
Also for gear ratios
And periodic patterns
Applications of LCM
Synchronization problems, adding fractions, repeating events.
LCM(12,15)=60
Meet every 60 min
Fractions: 1/4 + 1/6
LCM(4,6)=12
3/12 + 2/12 = 5/12
Real-World Applications of Prime Factorization
Prime factorization has practical applications in various fields:
Cryptography & Security
- RSA encryption system
- Digital signatures
- Secure communications
- Public key infrastructure
Computer Science
- Hash functions
- Random number generation
- Algorithm design
- Error detection codes
Mathematics Education
- Simplifying fractions
- Finding GCD and LCM
- Solving Diophantine equations
- Number theory problems
Engineering
- Gear ratio calculations
- Signal processing
- Synchronization problems
- Optimization algorithms
Finance
- Interest calculation periods
- Payment scheduling
- Investment cycles
- Risk analysis
Daily Life
- Recipe scaling
- Tile patterns
- Scheduling events
- Puzzle solving
Solved Prime Factorization Examples
Step-by-step solutions to common prime factorization problems:
Practice Problems
Test your understanding with these prime factorization problems:
Solution:
1. Divide by 2: 120 ÷ 2 = 60
2. Divide by 2: 60 ÷ 2 = 30
3. Divide by 2: 30 ÷ 2 = 15
4. Divide by 3: 15 ÷ 3 = 5
5. Divide by 5: 5 ÷ 5 = 1
Therefore, 120 = 2³ × 3 × 5.
Solution:
1. Factor 54: 54 = 2 × 3³
2. Factor 72: 72 = 2³ × 3²
3. Common primes: 2 and 3
4. Smallest powers: 2¹ and 3²
5. Multiply: 2 × 3² = 2 × 9 = 18
Therefore, GCD(54,72) = 18.
Solution:
1. Factor 15: 15 = 3 × 5
2. Factor 25: 25 = 5²
3. All primes: 3 and 5
4. Largest powers: 3¹ and 5²
5. Multiply: 3 × 5² = 3 × 25 = 75
Therefore, LCM(15,25) = 75.
Solution:
1. Prime factorize: 144 = 2⁴ × 3²
2. Use formula: (a+1)(b+1)
3. Exponents: 4 and 2
4. Calculate: (4+1)(2+1) = 5 × 3 = 15
Therefore, 144 has 15 divisors.
Solution:
1. Check divisibility by primes ≤ √101
2. √101 ≈ 10.05, test primes ≤ 10
3. Test 2: 101 odd, not divisible by 2
4. Test 3: 1+0+1=2, not divisible by 3
5. Test 5: doesn't end with 0 or 5
6. Test 7: 101 ÷ 7 = 14.428... not integer
Therefore, 101 is prime.
How to Find Prime Factors Step-by-Step
Follow this systematic approach to find prime factors efficiently:
Start with the Number
Begin with the number you want to factorize. If it's 1, it has no prime factors.
Goal: Find prime factors of 60
Check for Small Primes
Test divisibility by small primes: 2, 3, 5, 7, 11, etc.
60 is divisible by 2
First factor: 2
Divide and Continue
Divide by the prime factor and continue with the quotient.
Now factor 30
Repeat process
Use Divisibility Rules
Apply divisibility rules to quickly identify possible factors.
30 ÷ 2 = 15
15: ends with 5 → divisible by 5
15 ÷ 5 = 3
Continue Until Prime
Keep dividing until all factors are prime numbers.
Stop here
All factors are prime
Write in Exponential Form
Combine repeated factors using exponents for compact representation.
Exponential form: 2² × 3 × 5
Final answer
Pro Tips for Prime Factorization
- Memorize small primes up to at least 50 for efficiency
- Use divisibility rules to quickly eliminate possibilities
- For large numbers, test primes up to the square root
- Check if number is even - if yes, 2 is always a factor
- Use factor trees for visual understanding and organization
Frequently Asked Questions
Common questions about prime factorization, factors, divisors, and related concepts: