GMAT Online Course: Prime Factorization
- Goalisb
- 1 day ago
- 7 min read
The Unbreakable Code: Mastering Prime Factorization for GMAT Number Properties
Every positive integer greater than 1 has a unique identity, a fundamental structure that reveals its essence: its prime factorization. This concept is the bedrock of advanced number theory on the GMAT, serving as the most powerful tool for understanding factors, multiples, divisibility, Greatest Common Divisors (GCD), and Least Common Multiples (LCM).
While seemingly abstract, prime factorization provides a systematic and foolproof method to solve a wide array of quantitative problems. This lesson will thoroughly explain what prime factorization is, how to find it efficiently, and its multifaceted applications.
I. Revisiting Prime and Composite Numbers: The Building Blocks
Before delving into prime factorization, let's firmly define its components:
Prime Number: A positive integer greater than 1 that has exactly two distinct positive factors: 1 and itself.
Examples: 2, 3, 5, 7, 11, 13, 17, 19, ...
Note: 2 is the only even prime number.
Composite Number: A positive integer greater than 1 that has more than two distinct positive factors. These numbers can be formed by multiplying smaller prime numbers.
Examples: 4 (factors: 1, 2, 4), 6 (factors: 1, 2, 3, 6), 9 (factors: 1, 3, 9), 10, 12, ...
The Number 1: The number 1 is unique; it is considered neither prime nor composite. It has only one positive factor (itself).
Zero and Negative Integers: By convention, prime and composite numbers are defined only for positive integers greater than 1. Zero and negative integers are neither prime nor composite.
II. The Fundamental Theorem of Arithmetic (Unique Prime Factorization)
This is one of the most important theorems in number theory, underpinning the entire concept of prime factorization.
Theorem: Every integer greater than 1 is either a prime number itself or can be represented as a product of prime numbers, and this representation is unique, apart from the order of the prime factors.1
This means every number has a unique "prime fingerprint." For example, 12 is always 2 2 3 (or 2^2 3), never 2 6 or 3 * 4 as a final prime factorization.
III. Methods for Prime Factorization: Breaking Down Numbers
The goal is to express a number as a product of only prime numbers.
Division Method (Ladder Method):
Start by dividing the number by the smallest prime number (2) that divides it evenly.
Continue dividing the quotient by the smallest prime number until you reach a prime quotient.
Repeat the process with the next smallest prime if 2 no longer divides evenly.
Example: Prime factorize 180.
2 | 180 2 | 90 3 | 45 3 | 15 5 | 5 | 1
So, 180 = 2 2 3 3 5 = 2^2 3^2 5^1.
Factor Tree Method:
Start with the number at the top.
Branch out into any two factors of the number.
Continue branching each composite factor until all branches end in prime numbers.
Example: Prime factorize 180.
180 / \ 18 10 / \ / \ 2 9 2 5 / \ 3 3
Collecting all the prime numbers at the ends of the branches: 2, 3, 3, 2, 5.
Sorted and with exponents: 2^2 3^2 5^1.
IV. Applications of Prime Factorization: Unlocking Number Properties
Prime factorization is not just an exercise; it's a powerful analytical tool.
Finding All Factors of a Number:
Once you have the prime factorization N = p1^a p2^b p3^c ..., any factor of N will be in the form p1^x p2^y p3^z ... where 0 ≤ x ≤ a, 0 ≤ y ≤ b, 0 ≤ z ≤ c, etc.
Example: Find all factors of 180 (2^2 3^2 5^1).
Factors of 2^2: 2^0=1, 2^1=2, 2^2=4
Factors of 3^2: 3^0=1, 3^1=3, 3^2=9
Factors of 5^1: 5^0=1, 5^1=5 To find all factors, take every combination of these: (e.g., 1*1*1=1, 1*1*5=5, 1*3*1=3, 2*1*1=2, 2*3*5=30, 4*9*5=180, etc.) This systematic approach ensures you don't miss any.
Counting the Number of Factors:
This is a common GMAT question type.
If N = p1^a p2^b p3^c ... (where p1, p2, p3 are distinct prime numbers and a, b, c are their exponents), then the total number of positive factors of N is:
Number of Factors = (a + 1)(b + 1)(c + 1)...
Example: How many factors does 180 have?
180 = 2^2 3^2 5^1
Exponents are a=2, b=2, c=1.
Number of factors = (2+1)(2+1)(1+1) = 3 3 2 = 18.
Identifying Perfect Squares and Perfect Cubes:
A number is a perfect square if and only if all the exponents in its prime factorization are even.
Example: 36 = 2^2 * 3^2. Both exponents (2 and 2) are even.
Example: 72 = 2^3 * 3^2. Exponent of 2 (3) is odd, so not a perfect square.
A number is a perfect cube if and only if all the exponents in its prime factorization are multiples of 3.
Example: 64 = 2^6. Exponent 6 is a multiple of 3.
Example: 216 = 2^3 * 3^3. Both exponents (3 and 3) are multiples of 3.
Finding GCD and LCM (Reinforcement):
GCD: Product of common prime factors raised to their lowest powers.
LCM: Product of all distinct prime factors raised to their highest powers.
(As covered in Lesson 2.2, prime factorization makes these calculations very straightforward).
V. Why Prime Factorization is Crucial for the GMAT
Foundation for Number Properties: It's the underlying principle for understanding GCD, LCM, number of factors, perfect squares/cubes, and divisibility rules.
Problem Simplification: Complex number problems often become manageable when numbers are broken down into their prime components.
Data Sufficiency: Prime factorization is frequently tested in DS questions related to properties of integers.
Efficiency: It provides a systematic and efficient way to analyze numbers, avoiding guesswork or tedious trial-and-error.
VI. Common Pitfalls to Avoid
Including 1 as a Prime Factor: Remember, 1 is NOT a prime number.
Missing a Prime Factor: Be systematic with your division or factor tree to ensure all prime factors are identified.
Mistakes in Exponents: Double-check the count of each prime factor.
Not Using Distinct Primes: Prime factorization must use only prime numbers as bases.
Forgetting the +1 in the Number of Factors formula: A common error in this formula.
Interactive Check Your Understanding:
Prime factorize 252.
How many positive factors does 252 have?
Is 400 a perfect square? Use prime factorization to explain.
If a number has a prime factorization of 2^a * 3^b, and it has 12 factors, what are possible integer values for a and b?
Practice Questions:
Which of the following numbers has the most positive factors?
a) 36
b) 48
c) 72
d) 100
If N = 2^3 3^x 5^2 and N has 48 positive factors, what is the value of x?
What is the smallest positive integer K such that 120K is a perfect square?
If A = 2^a 3^b 5^c and B = 2^x 3^y 5^z, and GCD(A, B) = 2^2 3^1 and LCM(A, B) = 2^4 3^3 * 5^1, what are the values of a, b, c, x, y, z? (List the possibilities for each exponent).
A positive integer M has exactly 3 positive factors. Which of the following could be M?
a) 8
b) 9
c) 12
d) 25
e) Both b and d
Solutions to Practice Questions:
Which number has the most positive factors?
a) 36: 2^2 3^2. Factors = (2+1)(2+1) = 3 3 = 9.
b) 48: 2^4 3^1. Factors = (4+1)(1+1) = 5 2 = 10.
c) 72: 2^3 3^2. Factors = (3+1)(2+1) = 4 3 = 12.
d) 100: 2^2 5^2. Factors = (2+1)(2+1) = 3 3 = 9.
The correct answer is c) 72.
N = 2^3 3^x 5^2 has 48 factors. Find x:
Number of factors = (3+1)(x+1)(2+1) = 48
4 (x+1) 3 = 48
12 * (x+1) = 48
x+1 = 48 / 12
x+1 = 4
x = 3.
Smallest positive integer K such that 120K is a perfect square:
First, prime factorize 120: 120 = 2^3 3^1 5^1.
For 120K to be a perfect square, all exponents in its prime factorization must be even.
Current exponents: 2^3 (odd), 3^1 (odd), 5^1 (odd).
To make them even, K must supply at least 2^1, 3^1, and 5^1.
So, K = 2^1 3^1 5^1 = 2 3 5 = 30.
120 * 30 = 3600 = 60^2.
A = 2^a 3^b 5^c, B = 2^x 3^y 5^z
GCD(A, B) = 2^2 * 3^1
LCM(A, B) = 2^4 3^3 5^1
For each prime factor p:
min(exponent_A, exponent_B) = GCD_exponent
max(exponent_A, exponent_B) = LCM_exponent
For prime 2:
min(a, x) = 2
max(a, x) = 4
Possibilities for (a, x): (2, 4) or (4, 2)
For prime 3:
min(b, y) = 1
max(b, y) = 3
Possibilities for (b, y): (1, 3) or (3, 1)
For prime 5:
min(c, z) = 0 (since 5 is not in GCD, its lowest exponent must be 0)
max(c, z) = 1
Possibilities for (c, z): (0, 1) or (1, 0)
So, a and x are 2, 4 (in some order).
b and y are 1, 3 (in some order).
c and z are 0, 1 (in some order).
Positive integer M has exactly 3 positive factors:
For a number to have exactly 3 factors, its number of factors formula (a+1)(b+1)... must equal 3.
Since 3 is a prime number, the only way to get a product of 3 is 3 * 1.
This implies (a+1) = 3 and there are no other prime factors, or (b+1)=1 for any other primes.
So, a = 2, and there is only one prime factor.
Therefore, M must be the square of a prime number (p^2).
Let's check the options:
a) 8 = 2^3. Factors = 3+1 = 4. (No)
b) 9 = 3^2. Factors = 2+1 = 3. (Yes, 3 is prime)
c) 12 = 2^2 3^1. Factors = (2+1)(1+1) = 3 2 = 6. (No)
d) 25 = 5^2. Factors = 2+1 = 3. (Yes, 5 is prime)
Since both 9 and 25 are squares of prime numbers, they both have exactly 3 factors.
The correct answer is e) Both b and d.