See a Divisibility Problem? Factor Into Primes First — Most of the Structure Becomes Visible

If I had to compress a full number theory course into a single reflex, it would be this: when a problem involves divisibility, do not stare at the numbers — turn them into their prime factorisations first. The prime atoms are where the structure lives. As soon as you rewrite a number as 2^3 \cdot 3^2 \cdot 5, facts that were invisible while you were looking at "360" become loud.

This is not a trick for competition problems alone. It is the working habit of every fluent number theorist. The instinct matters more than any specific theorem, because once the numbers are in prime form, most of the standard number-theory operations become one-line lookups.

What the primes reveal

Here is a tiny experiment. Answer these three questions without factoring.

Does 180 divide 540?
What is \gcd(180, 108)?
Is 720 a perfect square?

Hard to answer at a glance. Now here are the same numbers with their prime factorisations:

180 = 2^2 \cdot 3^2 \cdot 5
540 = 2^2 \cdot 3^3 \cdot 5
108 = 2^2 \cdot 3^3
720 = 2^4 \cdot 3^2 \cdot 5

The answers are now obvious.

180 \mid 540? Compare exponents. 180 has 2^2, 3^2, 5^1; 540 has 2^2, 3^3, 5^1. Every prime in 180 appears with exponent \leq its exponent in 540. So yes, 180 \mid 540.
\gcd(180, 108)? Take the minimum exponent at each prime. 2^{\min(2,2)} \cdot 3^{\min(2,3)} \cdot 5^{\min(1,0)} = 2^2 \cdot 3^2 \cdot 5^0 = 36.
Is 720 a perfect square? A number is a perfect square iff every prime exponent is even. 720 = 2^4 \cdot 3^2 \cdot 5^1. The exponent of 5 is odd. No.

None of those three questions had a fast path without the factorisations. With the factorisations, each collapsed to a single comparison of exponents.

The translation dictionary

Here is how common number-theory questions look after you factor each number as n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}.

Question	What to check in the factorisation
Does a \mid b?	Every prime in a has exponent \leq its exponent in b
\gcd(a, b)?	For each prime, take the minimum of the exponents
\operatorname{lcm}(a, b)?	For each prime, take the maximum of the exponents
Is n a perfect square?	Every exponent is even
Is n a perfect cube?	Every exponent is divisible by 3
Are a, b coprime?	No prime appears with a non-zero exponent in both
Number of positive divisors of n?	(a_1 + 1)(a_2 + 1)\cdots(a_r + 1)
Sum of divisors of n?	\prod_{i} \frac{p_i^{a_i + 1} - 1}{p_i - 1}

Eight standard questions. All of them reduce to exponent arithmetic once you have the prime factorisation in hand. This is why the first move is almost always "factor everything in sight."

An interactive demo

Problem:

Slide through five classic problems. Each one looks painful in its raw form and becomes one-line obvious after prime factorisation. The exponents are where the structure lives.

Why this works — the underlying reason

It comes down to the Fundamental Theorem of Arithmetic. Every positive integer greater than 1 has exactly one prime factorisation. That uniqueness means there is a bijection between positive integers and their exponent vectors (a_1, a_2, a_3, \ldots) — one integer per vector, one vector per integer.

Multiplication of integers corresponds to addition of exponent vectors:

n \cdot m \longleftrightarrow (a_1 + b_1, a_2 + b_2, \ldots).

Divisibility corresponds to componentwise \leq:

n \mid m \longleftrightarrow a_i \leq b_i \text{ for all } i.

GCD corresponds to componentwise minimum. LCM to componentwise maximum. Squares are vectors with even entries. Cubes have entries divisible by 3. And so on.

In other words: factoring converts multiplicative questions about integers into additive / order-theoretic questions about vectors of exponents. Addition and comparison are easy. Multiplication without factoring is hard. That swap is the whole benefit.

When the instinct is most useful

Some problem types where "factor first" saves you the most time:

"Find the smallest n such that n is divisible by each of 12, 15, 18." This is an LCM problem. Factor: 12 = 2^2 \cdot 3, 15 = 3 \cdot 5, 18 = 2 \cdot 3^2. Take max exponent at each prime: 2^2 \cdot 3^2 \cdot 5 = 180. Done.
"How many positive divisors does 1680 have?" Factor: 1680 = 2^4 \cdot 3 \cdot 5 \cdot 7. Count: (4+1)(1+1)(1+1)(1+1) = 40. Done.
"Prove n^4 + 4 is composite for n \geq 2." Factor the expression: n^4 + 4 = (n^2 - 2n + 2)(n^2 + 2n + 2) (Sophie Germain identity). Both factors exceed 1 for n \geq 2. Done.
"Find all n such that n! ends in exactly three zeroes." A zero at the end comes from a factor 10 = 2 \cdot 5. There are always more 2s than 5s in n!, so count the 5s using Legendre's formula. The question becomes "for which n is \lfloor n/5 \rfloor + \lfloor n/25 \rfloor + \cdots = 3?" Much cleaner after re-expressing in terms of prime exponents.

Notice the last one — sometimes the instinct generalises to factoring algebraic expressions, not just numbers. Same idea: whenever divisibility matters, look for the primes.

The one situation where you skip factoring

The Euclidean algorithm is the exception. For very large numbers where factoring is genuinely hard (fifty-digit numbers and up), you compute \gcd by the Euclidean algorithm without ever factoring. The algorithm uses only subtraction and remainder, and it is fast.

But for numbers of the size you encounter in school (up to six or seven digits), factoring and the Euclidean algorithm are comparable in effort — and factoring gives you strictly more information (you learn the prime decomposition, which often helps with other questions in the same problem). So for school-level work: factor first, unless the numbers are clearly too large to factor by hand.

Building the instinct

The reflex develops with practice. Some drills:

Memorise the factorisations of numbers up to 100. Not to recite them, but so that when you see 72, you immediately "feel" 2^3 \cdot 3^2.
Memorise squares and cubes of small primes: 4, 8, 9, 16, 25, 27, 32, 49, 64, 81, 100, 121, 125, 128. These appear constantly.
When you solve a problem by other means, always re-solve it using prime factorisations as a check. The second pass is faster, and sometimes reveals that your first approach was doing more work than necessary.

Within a few weeks, the instinct becomes automatic. You see a divisibility problem, and before you have finished reading it, your hand has already written the prime factorisations of the numbers involved. That is the state you are aiming for — and it is the entry-level skill that separates students who solve number theory cleanly from students who brute-force.

One-line takeaway

Factor first, reason second. Once the numbers are in prime form, divisibility, GCD, LCM, perfect powers, and divisor counts all become comparisons of exponent vectors — a few seconds of work. The "hard" part of almost every divisibility problem is deciding to factor.