Number Theory · Chapter 21

Primes and Factors

Break numbers into primes, then count, add and multiply their divisors straight from the exponents.

What's this chapter about?

21.0 Primes, Factorization and Counting Divisors
21.1 Sum of Factors
21.2 Product of Factors
21.3 Practice Problems

You'll need

21.00%

Primes, Factorization and Counting Divisors

In this section you will be able to write any number as a product of primes and count its divisors straight from the exponents.

Twin brothers and their sister have ages that multiply to $128$ . Only one prime hides in $128$ , so every age is a power of $2$ .

Every whole number above $1$ splits into primes in exactly one way. In the factor tree under Concept 21.0.3, split $60$ as $6 \times 10$ , then start over with $4 \times 15$ . The leaves come out the same: $2, 2, 3, 5$ .

That one factorization tells you everything about the divisors. A divisor of $60 = 2^2 \cdot 3 \cdot 5$ just picks an exponent for each prime: $0$ to $2$ for the $2$ , $0$ or $1$ for the $3$ and the $5$ . Look: each divisor is one point of the lattice above.

A perfect square has only even exponents. So counting square divisors means counting even exponents, one prime at a time.

Exploreplay first, formulas later

Try this: This is 60 = 2² · 3 · 5. Count the points before you read Theorem 21.0.4. Why is it 3 × 2 × 2?
Try this: Raise the exponent of 2 from 2 to 3. How many new points appear, and why that many?
Try this: Press Squares. Which points light up, and what do their exponents have in common?

Name it

Definition 21.0.1 · Primes

Primes are numbers that have exactly two factors: $1$ and the number itself. For example, $2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots$ are all primes.

Remark 21.0.2

To check whether a number $n$ is prime, you only need to test the primes that are less than or equal to $\sqrt{n}$ .

Concept 21.0.3 · Prime Factorization

Prime factorization writes a number as a product of primes.

Example: the prime factorization of $60$ is $2^2 \times 3 \times 5$ .

Theorem 21.0.4 · Number of Factors of a Number

If the prime factorization of a number is

p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k},

then the number of factors of this number is

(e_1 + 1)(e_2 + 1)\cdots(e_k + 1).

Watch itpredict, then reveal

Example 21.1

AMC 10

Kiana has two older twin brothers. The product of their three ages is $128$ . What is the sum of their three ages?

1
Factor $128$ into primes. It is a power of $2$ : $128 = 2^k$ . What is $k$ ?

Predict first:
Your prediction

open on YouTube

Example 21.2

AIME

Let $n = 2^{31} 3^{19}$ . How many positive integer divisors of $n^2$ are less than $n$ but do not divide $n$ ?

1
Start small: $n = 2^3 \cdot 3^2 = 72$ , so $n^2 = 2^6 \cdot 3^4$ . How many divisors does $n^2$ have?

Predict first:
Your prediction

open on YouTube

Example 21.3

AIME

Let $n$ be the smallest positive integer that is a multiple of $75$ and has exactly $75$ positive integral divisors, including $1$ and itself. Find $\frac{n}{75}$ .

1
$75 = 3 \cdot 5^2$ . Which primes must $n$ contain, and at least how often?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Try it

Problem 21.3.6

AMC 10

How many positive even multiples of $3$ less than $2020$ are perfect squares?

Problem 21.3.7

AMC 10

How many positive integer divisors of $201^9$ are perfect squares or perfect cubes (or both)?

Problem 21.3.16

AMC 10

How many positive two-digit integers are factors of $2^{24} - 1$ ?

Contest cornerreal contest problems

Problem 21.3.1

AMC 10

A positive integer divisor of $12!$ is chosen at random. The probability that the divisor chosen is a perfect square can be expressed as $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. What is $m + n$ ?

Problem 21.3.11

AMC 10

For some positive integer $n$ , the number $110n^3$ has $110$ positive integer divisors, including $1$ and the number $110n^3$ . How many positive integer divisors does the number $81n^4$ have?

Problem 21.3.22

AIME

Find the number of ordered pairs of positive integers $(m, n)$ such that $m^2 n = 20^{20}$ .

Problem 21.3.34(additional)

AIME

How many positive integer divisors of $2004^{2004}$ are divisible by exactly $2004$ positive integers?

Checkpoint for section 21.0

Get 2 of 3 right to master this section. One try each, no hints.

21.10%

Sum of Factors

In this section you will be able to add up all the divisors of a number by multiplying one geometric sum per prime.

The divisors of $12$ are $1, 2, 3, 4, 6, 12$ , and they add up to $28$ . So does $(1 + 2 + 4)(1 + 3)$ . That is no accident.

Expand $(1 + 2 + 4)(1 + 3)$ : every term picks one power of $2$ and one power of $3$ . That is exactly one divisor of $12$ each time. So one sum per prime, multiplied together, adds up every divisor.

Each bracket is a geometric series: $1 + p + \cdots + p^{e} = \frac{p^{e+1} - 1}{p - 1}$ .

Need only the odd divisors? Drop the bracket for $2$ . The book prints Example 21.4 in Section 21.2, but it is a divisor-sum problem, so you’ll meet it here.

Exploreplay first, formulas later

Try this: This is 12 = 2² · 3. Expand (1 + 2 + 4)(1 + 3) by hand. Why does it list every divisor of 12 exactly once?
Try this: Press Odd. Which column grays out, and what is left of the sum?
Try this: Press Even. How do the odd sum and the even sum compare when the exponent of 2 is 2?

Name it

Theorem 21.1.1 · Sum of Factors of a Number

If the prime factorization of a number is

p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k},

then the sum of the factors of this number is

(1 + p_1 + p_1^2 + \cdots + p_1^{e_1})(1 + p_2 + p_2^2 + \cdots + p_2^{e_2})\cdots(1 + p_k + p_k^2 + \cdots + p_k^{e_k}).

Concept 21.1.2 · Sum of Factors of a Number

For each prime $p$ in the prime factorization, first find the sum of $p^k$ over all the possible exponents $k$ (from $0$ up to the exponent of $p$ ). Then multiply these sums over all of the primes to get the sum of all the factors of the number.

Watch itpredict, then reveal

Example 21.4

AMC 12

For $n$ a positive integer, let $f(n)$ be the quotient obtained when the sum of all positive divisors of $n$ is divided by $n$ . For example,

f(14) = (1 + 2 + 7 + 14) \div 14 = \frac{12}{7}.

What is $f(768) - f(384)$ ?

1
Factor both numbers. $768 = 2^a \cdot 3$ and $384 = 2^{a-1} \cdot 3$ . What is $a$ ?

Predict first:
Your prediction

open on YouTube

Try it

Problem 21.3.23

AMC 10/12

Let $N = 34 \cdot 34 \cdot 63 \cdot 270$ . What is the ratio of the sum of the odd divisors of $N$ to the sum of the even divisors of $N$ ?

Contest cornerreal contest problems

Problem 21.3.36(additional)

AIME

Let $S$ be the sum of all numbers of the form $a/b$ , where $a$ and $b$ are relatively prime positive divisors of $1000$ . What is the greatest integer that does not exceed $S/10$ ?

Checkpoint for section 21.1

Get 2 of 3 right to master this section. One try each, no hints.

21.20%

Product of Factors

In this section you will be able to multiply all the divisors of a number at once by pairing each divisor d with n/d.

The divisors of $36$ pair up: $1 \times 36$ , $2 \times 18$ , $3 \times 12$ , $4 \times 9$ . Each pair multiplies to $36$ . And $6$ is left over, paired with itself.

Pair every divisor $d$ with its partner $\frac{n}{d}$ . On the lattice, partners sit opposite each other across the center. With $f$ divisors there are $\frac{f}{2}$ pairs, each worth $n$ , so the product is $n^{f/2}$ .

When $n$ is a perfect square, the middle divisor $\sqrt{n}$ is its own partner. It counts as half a pair, and the formula still works.

Exploreplay first, formulas later

Light up:

exponent of 22

exponent of 32

n = 36 = 2² × 3²

You picked 2⁰ × 3¹ = 3. Its partner is 2² × 3¹ = 12, and 3 × 12 = 36.

Powers of 2:2⁰, 2¹, 2² → 3 choices
Powers of 3:3⁰, 3¹, 3² → 3 choices
Mirror points pair up across the center. Each pair multiplies to 36. There are 9 factors, so 9/2 pairs (the middle one pairs with itself, so it counts as half a pair).

36^(9/2) = 10,077,696

Try this: This is 36. Its divisor 3 is picked: where is its partner, and what do the two multiply to?
Try this: Pick 6. Who is its partner? What does that tell you about 6 × 6?
Try this: Why does a perfect square have an odd number of divisors?

Name it

Theorem 21.2.1 · Product of Factors of a Number

If a number $n$ has $f$ factors (count them with the number-of-factors formula), then the product of the factors of $n$ is

n^{f/2}.

Contest cornerreal contest problems

Problem 21.3.12

AMC 10

Let $S$ be the set of all positive integer divisors of $100{,}000$ . How many numbers are the product of two distinct elements of $S$ ?

Problem 21.3.33(additional)

AMC 10

Given that $3^8 \cdot 5^2 = a^b$ , where both $a$ and $b$ are positive integers, find the smallest possible value for $a + b$ .

Checkpoint for section 21.2

Get 2 of 3 right to master this section. One try each, no hints.

21.3

Practice Problems

In this section you will be able to mix primes, divisor counts and divisibility on contest problems from across the chapter.

Not every problem here says “divisor” out loud. Factor first anyway: primes, parity and last digits crack most of them.

Problems 21.3.24 to 21.3.38 are the book’s Additional Problems. The last two are challenge problems. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 21.3.2

AMC 10

A single bench section at a school event can hold either $7$ adults or $11$ children. When $N$ bench sections are connected end to end, an equal number of adults and children seated together will occupy all the bench space. What is the least possible positive integer value of $N$ ?

Problem 21.3.3

AMC 10

What is the least positive integer $m$ such that $m \cdot 2! \cdot 3! \cdot 4! \cdot 5! \cdots 16!$ is a perfect square?

Problem 21.3.4

AMC 10

For how many (not necessarily positive) integer values of $n$ is the value of $4000 \cdot \left(\frac{2}{5}\right)^n$ an integer?

Problem 21.3.5

AMC 10

The numbers from $1$ to $8$ are placed at the vertices of a cube in such a manner that the sum of the four numbers on each face is the same. What is this common sum?

Problem 21.3.8

AMC 12

What is the sum of the exponents of the prime factors of the square root of the largest perfect square that divides $12!$ ?

Problem 21.3.9

AMC 10

How many ways are there to write $2016$ as the sum of twos and threes, ignoring order? (For example, $1008 \cdot 2 + 0 \cdot 3$ and $402 \cdot 2 + 404 \cdot 3$ are two such ways.)

Problem 21.3.10

AIME

Find the number of positive integers with three not necessarily distinct digits, $abc$ , with $a \neq 0$ and $c \neq 0$ such that both $abc$ and $cba$ are multiples of $4$ .

Problem 21.3.13

AMC 10

The $25$ integers from $-10$ to $14$ , inclusive, can be arranged to form a $5$ -by- $5$ square in which the sum of the numbers in each row, the sum of the numbers in each column, and the sum of the numbers along each of the main diagonals are all the same. What is the value of this common sum?

Problem 21.3.14

AMC 10

All the numbers $2, 3, 4, 5, 6, 7$ are assigned to the six faces of a cube, one number to each face. For each of the eight vertices of the cube, a product of three numbers is computed, where the three numbers are the numbers assigned to the three faces that include that vertex. What is the greatest possible value of the sum of these eight products?

Problem 21.3.15

AMC 12

How many odd positive $3$ -digit integers are divisible by $3$ but do not contain the digit $3$ ?

Problem 21.3.17

AIME

There is a prime number $p$ such that $16p + 1$ is the cube of a positive integer. Find $p$ .

Problem 21.3.18

AMC 10

Joey and Chloe and their daughter Zoe all have the same birthday. Joey is $1$ year older than Chloe, and Zoe is exactly $1$ year old today. Today is the first of the $9$ birthdays on which Chloe's age will be an integral multiple of Zoe's age. What will be the sum of the two digits of Joey's age the next time his age is a multiple of Zoe's age?

Problem 21.3.19

AMC 10

What is the tens digit of $2015^{2016} - 2017$ ?

Problem 21.3.20

AMC 10

Let $N = 123456789101112\dots4344$ be the $79$ -digit number that is formed by writing the integers from $1$ to $44$ in order, one after the other. What is the remainder when $N$ is divided by $45$ ?

Problem 21.3.21

AMC 10

What is the hundreds digit of $(20! - 15!)$ ?

Problem 21.3.24(additional)

AMC 12

In multiplying two positive integers $a$ and $b$ , Ron reversed the digits of the two-digit number $a$ . His erroneous product was $161$ . What is the correct value of the product of $a$ and $b$ ?

Problem 21.3.25(additional)

AMC 10

Positive integers $a$ , $b$ , and $2009$ , with $a < b < 2009$ , form a geometric sequence with an integer ratio. What is $a$ ?

Problem 21.3.26(additional)

AMC 10

How many positive cubes divide $3! \cdot 5! \cdot 7!$ ?

Problem 21.3.27(additional)

AMC 12

This problem also appears in the book as 21.3.23.

Let $N = 34 \cdot 34 \cdot 63 \cdot 270$ . What is the ratio of the sum of the odd divisors of $N$ to the sum of the even divisors of $N$ ?

Problem 21.3.28(additional)

AMC 10

Suppose that $m$ and $n$ are positive integers such that $75m = n^3$ . What is the minimum possible value of $m + n$ ?

Problem 21.3.29(additional)

AMC 10

Elmo makes $N$ sandwiches for a fundraiser. For each sandwich he uses $B$ globs of peanut butter at $4$ ¢ per glob and $J$ blobs of jam at $5$ ¢ per blob. The cost of the peanut butter and jam to make all the sandwiches is $2.53. Assume that $B$ , $J$ , and $N$ are positive integers with $N > 1$ . What is the cost of the jam Elmo uses to make the sandwiches?

Problem 21.3.30(additional)

AMC 12

The largest prime factor of $16384$ is $2$ because $16384 = 2^{14}$ . What is the sum of the digits of the greatest prime number that is a divisor of $16383$ ?

Problem 21.3.31(additional)

AMC 12

How many ways are there to paint each of the integers $2, 3, \ldots, 9$ either red, green, or blue so that each number has a different color from each of its proper divisors?

Problem 21.3.32(additional)

AMC 10

The positive integers $A$ , $B$ , $A - B$ , and $A + B$ are all prime numbers. The sum of these four primes is

Problem 21.3.35(additional)

AIME

Find the number of positive integers that are divisors of at least one of $10^{10}$ , $15^7$ , $18^{11}$ .

Problem 21.3.37(additional)

AMC 12Challenge

For each positive integer $n$ , let $f_1(n)$ be twice the number of positive integer divisors of $n$ , and for $j \ge 2$ , let $f_j(n) = f_1(f_{j-1}(n))$ . For how many values of $n \le 50$ is $f_{50}(n) = 12$ ?

Problem 21.3.38(additional)

AMC 10Challenge

For each positive integer $n > 1$ , let $P(n)$ denote the greatest prime factor of $n$ . For how many positive integers $n$ is it true that both $P(n) = \sqrt{n}$ and $P(n + 48) = \sqrt{n + 48}$ ?