Prime Factorization is the habit of breaking integers into primes to control divisors, gcd, lcm, and exponents. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
$$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \quad (\text{unique up to order})$$
Every integer greater than $1$ factors into primes in exactly one way, and that factorization controls its divisors, gcd, lcm, and perfect-power structure.
Why It Works
1
Existence: any $n > 1$ either is prime or has a proper factor; repeatedly splitting factors terminates since they shrink, leaving a product of primes.
2
Uniqueness follows from Euclid's lemma: if a prime $p$ divides a product, it divides one of the factors.
3
From $n = p_1^{e_1} \cdots p_k^{e_k}$, the number of positive divisors is $(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$, since each divisor picks an exponent $0 \le f_i \le e_i$.
4
$n$ is a perfect square exactly when every exponent $e_i$ is even.
A divisor chooses an exponent of $2$ from $\{0,1,2,3\}$, of $3$ from $\{0,1,2\}$, and of $5$ from $\{0,1\}$.
3
Multiply the counts: $(3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2$.
4
This gives $24$ divisors.
Answer:
$24$
Warm-up
What is the smallest positive integer $n$ such that $n$ has exactly $15$ positive divisors?
1
If $n = \prod p_i^{e_i}$, then $\tau(n) = \prod (e_i + 1) = 15$. Factor $15 = 15$ or $15 = 3 \cdot 5$.
2
Case $15 = 15$: one prime with exponent $14$, smallest is $2^{14} = 16384$.
3
Case $15 = 5 \cdot 3$: exponents $4$ and $2$. To minimize, put the larger exponent on the smaller prime: $2^4 \cdot 3^2 = 16 \cdot 9 = 144$.
4
Compare $144 < 16384$, so the minimum is $144$.
Answer:
$144$
Contest level
Find the number of ordered pairs of positive integers $(a, b)$ with $\operatorname{lcm}(a, b) = 2^3 \cdot 3^2 \cdot 5$.
1
For each prime, the exponents in $a$ and $b$ must have maximum equal to the exponent in the lcm. Handle each prime independently.
2
Prime $2$ (max must be $3$): pairs of exponents $(x, y)$ in $\{0,\dots,3\}^2$ with $\max(x,y) = 3$. Count $= 2 \cdot 4 - 1 = 7$ (either coordinate is $3$, minus the double count).
Multiply across primes: $7 \cdot 5 \cdot 3 = 105$.
Answer:
$105$
Olympiad / Challenge
Prove that the product of any $k$ consecutive positive integers is divisible by $k!$.
1
The product $\frac{n!}{(n-k)!} = n(n-1)\cdots(n-k+1)$ equals $k! \cdot \binom{n}{k}$, so the claim is that $\frac{n(n-1)\cdots(n-k+1)}{k!} = \binom{n}{k}$ is an integer.
2
Argue prime by prime using $p$-adic valuations. For each prime $p$, by Legendre's formula $v_p\!\left(\binom{n}{k}\right) = \sum_{i \ge 1}\left(\left\lfloor \tfrac{n}{p^i}\right\rfloor - \left\lfloor \tfrac{k}{p^i}\right\rfloor - \left\lfloor \tfrac{n-k}{p^i}\right\rfloor\right)$.
3
Each summand is $\lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor$ with $x = k/p^i$, $y = (n-k)/p^i$, which is always $0$ or $1$ (never negative) because $\lfloor x \rfloor + \lfloor y \rfloor \le \lfloor x + y \rfloor$.
4
So $v_p\!\left(\binom{n}{k}\right) \ge 0$ for every prime $p$; a rational with nonnegative valuation at every prime is an integer. Hence $k! \mid n(n-1)\cdots(n-k+1)$.
Answer:
$k!$ divides the product (equivalently, $\binom{n}{k}$ is an integer).
Going Deeper
Generalization: the factorization $n = \prod p_i^{e_i}$ makes arithmetic functions read off directly — $\tau(n) = \prod(e_i+1)$ divisors, $n$ is a $k$-th power iff every $e_i$ is a multiple of $k$, and $\gcd$/$\operatorname{lcm}$ are min/max of exponents prime by prime. Many problems reduce to choosing exponents under constraints.
Where it appears: divisor-counting problems, 'smallest $n$ with exactly $D$ divisors', perfect-square/perfect-power conditions, and lcm/gcd counting where you analyze one prime at a time and multiply the independent counts.
Pitfall: unique factorization holds for integers $> 1$, but the unit $1$ has the empty factorization (no primes), so $1$ is neither prime nor composite — and $\tau(1) = 1$. Also, to minimize a number with a given divisor count, assign the largest exponents to the smallest primes; the naive 'use distinct small primes' is often not optimal.
Spot the Signal
Look for problems where the key step is breaking integers into primes to control divisors, gcd, lcm, and exponents.
You can describe the hard part as breaking integers into primes to control divisors, gcd, lcm, and exponents, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the integer constraint that calls for prime factorization, then rewrite the givens around it.
Name the relation that makes Prime Factorization legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Prime Factorization just because the surface looks familiar; verify the required condition first.
Applying Prime Factorization because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let prime factorization reveal the integer structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is breaking integers into primes to control divisors, gcd, lcm, and exponents.