How to Count the Factors of a Number

Lesson 3.1 found that perfect squares alone have an odd divisor count. Lesson 3.3 gave every number a unique prime fingerprint. Now we count a number's divisors straight from that fingerprint, without listing a single one.

Problem

A machine builds divisors of

12 = 2^{2} \times 3

by choosing how many 2s (0, 1, or 2) and how many 3s (0 or 1) to multiply together. How many different divisors can it build?

Show a hint

You make two separate choices, the number of $2$ s (three options) and the number of $3$ s (two options). Every pairing of one choice with the other gives a divisor. Count the pairings.
Three options for the $2$ s and two options for the $3$ s give $3 \times 2$ combinations. List them as $2^{i} \times 3^{j}$ and confirm you get $1, 2, 3, 4, 6, 12$ .

Show the full solution

The

2

s can appear

0

1

, or

2

times, which is three choices, and the

3

can appear

0

1

times, which is two. The choices are independent, so the divisors number

3 \times 2 = 6 .

Listing them as

2^{i} \times 3^{j}

gives

1, 2, 3, 4, 6, 12

, exactly six. Each prime offers one more choice than its exponent, and independent choices multiply.

The rule becomes a picture for

72 = 2^{3} \times 3^{2}

. Each divisor picks one power of

2

for its column, from

2^{0}

up to

2^{3}

, giving four columns, and one power of

3

for its row, from

3^{0}

up to

3^{2}

, giving three rows. Every cell of the grid is one divisor, the product of its row and column headers, so the divisors fill a tidy

4 \times 3

rectangle. That is why the count is

(3 + 1) (2 + 1) = 12

, the same as adding one to each exponent and multiplying. The two green cells,

9

and

36

, are the divisors that happen to be perfect squares themselves, a hint of something we will return to in a moment.

Problem

The fingerprint of 360 is

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

. Use the add-one-and-multiply rule to count how many positive divisors 360 has without listing them.

Show a hint

Each prime contributes one more choice than its exponent. The prime $2$ has exponent $3$ , so it offers $3 + 1$ choices. Do the same for $3$ and for $5$ , then multiply.
The choice counts are $3 + 1 = 4$ for the $2$ s, $2 + 1 = 3$ for the $3$ s, and $1 + 1 = 2$ for the $5$ . Multiply $4 \times 3 \times 2$ .

Show the full solution

Add one to each exponent and multiply.

(3 + 1) (2 + 1) (1 + 1) = 4 \times 3 \times 2 = 24 .

360

has

24

positive divisors, found without writing one of them down. The rule handles as many primes as a number carries, turning a long listing chore into a single multiplication.

Problem

Compare

96 = 2^{5} \times 3

and

100 = 2^{2} \times 5^{2}

. Apply the counting rule to each. Which number has more divisors?

Show a hint

Apply add-one-and-multiply to each. For $96 = 2^{5} \times 3$ , the counts are $5 + 1$ and $1 + 1$ . For $100 = 2^{2} \times 5^{2}$ , the counts are $2 + 1$ and $2 + 1$ .
$96$ gives $6 \times 2 = 12$ divisors, while $100$ gives $3 \times 3 = 9$ . Which is larger?

Show the full solution

For

96 = 2^{5} \times 3

, the count is

(5 + 1) (1 + 1) = 6 \times 2 = 12.

For

100 = 2^{2} \times 5^{2}

, it is

(2 + 1) (2 + 1) = 3 \times 3 = 9.

The bigger number has fewer divisors, so the answer is

96

. Divisor count follows the shape of the exponents, not the size of the number. One tall stack of

2

s beats two medium stacks here.

Problem

The divisor count

(a + 1) (b + 1) \dots

is odd only when every exponent is even, the fingerprint of a perfect square. How many numbers from 1 to 50 have an odd number of divisors?

Show a hint

The divisor count is a product $(a + 1) (b + 1) \dots$ . A product of whole numbers is odd only when every single factor in it is odd. So ask, when is every $a + 1$ odd?
Every $a + 1$ is odd exactly when every exponent $a$ is even, which is precisely when the number is a perfect square. So count the perfect squares from $1$ to $50$ .

Show the full solution

A product of whole numbers is odd only when every factor is odd, and

a + 1

is odd exactly when

a

is even. So an odd divisor count means every exponent is even, which is the fingerprint of a perfect square. From

1

50

the squares are

1, 4, 9, 16, 25, 36, 49,

the squares of

1

through

7

, since

8^{2} = 64

overshoots. That is

7

numbers. This is lesson 3.1's result again, now falling straight out of the counting rule.

Problem

Find the smallest whole number with exactly 12 divisors by breaking 12 into exponent-plus-one pieces, building the smallest number from each, and comparing.

Show a hint

You need $(a + 1) (b + 1) \dots = 12$ . The ways to write $12$ as such a product include $12$ , $6 \times 2$ , $4 \times 3$ , and $3 \times 2 \times 2$ . Each gives a set of exponents to spend on primes.
To keep the number small, give the biggest exponents to the smallest primes. For the split $3 \times 2 \times 2$ , that means $2^{2} \times 3^{1} \times 5^{1}$ . Build the number for each split and take the least.
Compare $2^{11} = 2048$ , $2^{5} \times 3 = 96$ , $2^{3} \times 3^{2} = 72$ , and $2^{2} \times 3 \times 5 = 60$ . Which is smallest?

Show the full solution

The exponent-plus-one values have to multiply to

12

, and to keep the number small the biggest exponents go on the smallest primes.

12 = 12 \Rightarrow 2^{11} = 2048

12 = 6 \times 2 \Rightarrow 2^{5} \times 3 = 96

12 = 4 \times 3 \Rightarrow 2^{3} \times 3^{2} = 72

12 = 3 \times 2 \times 2 \Rightarrow 2^{2} \times 3 \times 5 = 60

The smallest is

60

. Spreading the choices across

2, 3, 5

is cheaper than stacking them all on

2

Problem

720 = 2^{4} \times 3^{2} \times 5

. An even divisor must contain at least one 2. How many even divisors does 720 have?

Show a hint

An even divisor must take at least one $2$ . Normally the $2$ s offer choices $0, 1, 2, 3, 4$ , but forbidding zero $2$ s leaves only $1, 2, 3, 4$ . The $3$ s and the $5$ keep all their choices.
So the even divisors number $4 \times (2 + 1) \times (1 + 1)$ . Alternatively, count all the divisors and subtract the odd ones, which are the divisors of $3^{2} \times 5$ .

Show the full solution

An even divisor of

720 = 2^{4} \times 3^{2} \times 5

must take at least one

2

, so the

2

s drop from five choices to the four

1, 2, 3, 4

. The

3

s still give

2 + 1 = 3

and the

5

gives

1 + 1 = 2

, so the even divisors number

4 \times 3 \times 2 = 24 .

Restricting one prime's choices counts a whole family of divisors directly. Cross-check,

720

has

30

divisors and

6

odd ones, and

30 - 6 = 24

Every tool in this chapter came from the same move. Find a number's primes, read the fingerprint, and divisibility, perfect powers, GCD, LCM, and the exact divisor count all follow. Chapter 4 turns to fractions.

Practice these ideas

Practice

A number is given as

2^{4} \times 5^{2}

. Use the add-one-and-multiply rule to count its positive divisors.

Show the solution

Add one to each exponent and multiply.

(4 + 1) (2 + 1) = 5 \times 3 = 15 .

The divisors are

2^{i} \times 5^{j}

with

i

from

0

4

and

j

from

0

2

, which is

5

3

pairs.

Practice

Factor

600 = 2^{3} \times 3 \times 5^{2}

and apply the counting rule. How many positive divisors does 600 have?

Show the solution

Reading the fingerprint

600 = 2^{3} \times 3^{1} \times 5^{2}

(3 + 1) (1 + 1) (2 + 1) = 4 \times 2 \times 3 = 24 .

Once a number is in fingerprint form, its divisor count is one multiplication away.

Practice

Which has more divisors,

64 = 2^{6}

90 = 2 \times 3^{2} \times 5

? Count each and enter the number with more.

Show the solution

For

64 = 2^{6}

, the count is

6 + 1 = 7

. For

90 = 2 \times 3^{2} \times 5

, it is

(1 + 1) (2 + 1) (1 + 1) = 2 \times 3 \times 2 = 12

. So

90

has more, twelve against seven. Spreading primes out makes far more divisors than stacking one prime high, so the count tracks fingerprint shape, not size.

Practice

How many whole numbers from 1 to 100 have an odd number of divisors?

Show the solution

A divisor count is odd only when every exponent is even, which means the number is a perfect square. From

1

100

those are

1, 4, 9, 16, 25, 36, 49, 64, 81, 100,

the squares of

1

through

10

, so the answer is

10

. Odd divisor counts belong to perfect squares and nothing else, so counting them is just counting squares.

Practice

Find the smallest whole number with exactly 8 divisors.

Show the solution

The exponent-plus-one values must multiply to

8

, and the biggest exponents go on the smallest primes.

8 = 8 \Rightarrow 2^{7} = 128, 8 = 4 \times 2 \Rightarrow 2^{3} \times 3 = 24, 8 = 2 \times 2 \times 2 \Rightarrow 2 \times 3 \times 5 = 30.

The smallest is

24

, whose divisors are

1, 2, 3, 4, 6, 8, 12, 24

Practice

How many positive divisors does

2^{10}

have?

Show the solution

The divisors of

2^{10}

are

2^{0}, 2^{1}, \dots, 2^{10}

, one for each exponent from

0

10

, so there are

10 + 1 = 11

. A prime raised to the power

a

has

a + 1

divisors, the simplest case of the rule.

Practice

A number has exactly three divisors only when it is the square of a prime. How many numbers from 1 to 50 have exactly three divisors?

Show the solution

For

(a + 1) (b + 1) \dots

to equal

3

, and

3

is prime, the product must be the single factor

3

. That forces one prime with exponent

2

and nothing else, so the number is a prime squared. Up to

50

those are

2^{2} = 4, 3^{2} = 9, 5^{2} = 25, 7^{2} = 49,

since

1 1^{2} = 121

overshoots. That is

4

numbers. The divisors of

p^{2}

are just

1

p

, and

p^{2}

, which is why three divisors always means a prime square.

Practice

How many of 360's divisors are even, given

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

Show the solution

An even divisor needs at least one

2

, so the

2

s drop from four choices to the three

1, 2, 3

. The

3

s give

2 + 1 = 3

and the

5

gives

1 + 1 = 2

, so the even divisors number

3 \times 3 \times 2 = 18 .

Cross-check,

360

has

24

divisors and

6

odd ones, the divisors of

3^{2} \times 5

, and

24 - 6 = 18

Practice

Divisor counting rule. For

n = p^{a} q^{b} \dots

, count is

(a + 1) (b + 1) \dots

. Depends on exponent shape, not size. Odd count ↔ perfect square. Trim one prime's choices for a sub-family. Run backward to design a number with a target count.

Practice

Locker

n

is flipped once per divisor, so it ends open only when it has an odd divisor count, exactly the perfect squares. Open lockers: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Counting a Number's Divisors

Practice these ideas