Prime Factor Analysis

In one sentence

Every integer greater than $1$ can be written as a product of primes, and in only one way:

360 = 2^{3} \times 3^{2} \times 5^{1} .

So everything about an integer is contained in a row of exponents. Prime factor analysis means: stop staring at the number itself and look at that row of exponents.

$a$ divides $b$ : none of $a$ 's bars is taller than the matching bar of $b$ .
A perfect square: every exponent is even.
The greatest common divisor takes the lower bar; the least common multiple takes the higher one.
A prime: just one bar, of height $1$ , so the only way to split it is $1 \times$ itself.

Predict first

$360 = 2^{3} \times 3^{2} \times 5$ . How many positive divisors does it have? (Hint: in a divisor, the exponent of $2$ can be $0, 1, 2$ or $3$ .)

Choose an answer first; then you can see the result.

Stop 1 · Primes and composites (Vol. 6)

A prime has the simplest bar chart of all, so “some expression is prime” is a strong condition: as soon as the expression factors, one of the factors is forced to be $\pm 1$ .

Example: find all positive integers n for which n² − 8n + 15 is prime

Step 1 / 5

Factor first
Cross method: $15 = 3 \times 5$ and $3 + 5 = 8$ .

$n^{2} - 8 n + 15 = (n - 3) (n - 5)$
A prime splits only one way
Both factors positive
Both factors negative
Conclusion

Stop 2 · The Fundamental Theorem of Arithmetic (Vol. 6)

Put two numbers side by side and compare bars: for each prime, the lower bar goes to the gcd, the higher bar to the lcm.

Example: gcd(a, b) = 12, lcm(a, b) = 360, a ≤ b. How many pairs (a, b) are there?

Step 1 / 5

Factor the two given numbers
$12 = 2^{2} \times 3$ and $360 = 2^{3} \times 3^{2} \times 5$ . Look at the simplest pair first: $a = 12$ , $b = 360$ .

$g cd lcm = 2^{2} \cdot 3^{1} \cdot 5^{0} = 2^{3} \cdot 3^{2} \cdot 5^{1}$
One prime at a time
Each prime splits 2 ways
Try another split
Remove the repeats

Stop 3 · Perfect squares (Vol. 6)

In a perfect square, every bar has an even height. Not a square? See which bars have an “odd one out” and top them up.

Example: what is the smallest positive integer k that makes 360k a perfect square?

Step 1 / 4

Look at the parity of the exponents
$360 = 2^{3} \times 3^{2} \times 5$ . The exponents are $3, 2, 1$ : the exponents of $2$ and $5$ are odd, so each has one block left over.

$2^{3} \times 3^{2} \times 5^{1}$
Top up the odd ones out
Check
Why it cannot be smaller

The other way round: if a product is a square, must each factor be a square? Drag $a$ and $b$ below and find the pattern.

12 \times 27 = 324 = 1 8^{2}

, but neither

12

nor

27

is a square. Now try

a = 4

b = 25

. Which reading shows the difference between the two cases?

When $a$ and $b$ are coprime, no prime is shared by both, so their exponents cannot “team up to make an even number”. Only then does “ $ab$ is a square” mean that $a$ and $b$ are each squares. For example, consecutive positive integers $n$ and $n + 1$ are coprime, so if $n (n + 1)$ were a square, $n$ and $n + 1$ would both be squares. But two positive squares differ by at least $3$ . So $n (n + 1)$ is never a perfect square.

Stop 4 · Integer roots of quadratic equations (Vol. 2)

Integer-root problems can often be turned into “a product of two integers equals a specific number”. The fewer prime factors that number has, the fewer the possibilities.

Find all integers $k$ for which both roots of $x^{2} - k x + k + 6 = 0$ are integers.

Example: both roots of x² − kx + k + 6 = 0 are integers

Step 1 / 5

Vieta's formulas
Call the two integer roots $x_{1}$ and $x_{2}$ . Their sum is $k$ and their product is $k + 6$ .

$x_{1} + x_{2} = k, x_{1} x_{2} = k + 6$
Eliminate k
7 is prime
Do not forget the negatives
Check and answer

Practice

Exercise 1Basic

How many positive divisors does $720$ have?

Exercise 2Advanced

What is the smallest positive integer $k$ that makes $84 k$ a perfect square?

Exercise 3Challenge

Find all integers $k$ for which both roots of $x^{2} - k x + k + 4 = 0$ are integers. (There are two answers; separate them with a comma.)

In one sentence

Stop 1 · Primes and composites (Vol. 6)

Example: find all positive integers n for which n² − 8n + 15 is prime

Stop 2 · The Fundamental Theorem of Arithmetic (Vol. 6)

Example: gcd(a, b) = 12, lcm(a, b) = 360, a ≤ b. How many pairs (a, b) are there?

Stop 3 · Perfect squares (Vol. 6)

Example: what is the smallest positive integer k that makes 360k a perfect square?

Stop 4 · Integer roots of quadratic equations (Vol. 2)

Example: both roots of x² − kx + k + 6 = 0 are integers

Practice

Mistake Museum · Exhibits from this stop

The product is a square, so each factor is a square

Forgetting negative factors and 1

Stops on this line