Free CAT library

Factors, Divisors & Product Splitting

Deconstruct numbers into prime factors to calculate the total number of divisors, their sum, their product, and how to split numbers into paired factors.

1. The Story & Mental Model

Think of prime factorization as the DNA sequence of a number. Every integer is built from prime building blocks. The number 360360, for example, is just 23×32×512^3 \times 3^2 \times 5^1.

When you want to build a divisor (a factor) of 360, you are basically walking through a buffet line of these prime blocks.

  • You arrive at the '2s' station. You can choose to take no 2s, one 2, two 2s, or three 2s. That's (3+1)=4(3 + 1) = 4 choices.

  • Next, the '3s' station. You can take no 3s, one 3, or two 3s. That's (2+1)=3(2 + 1) = 3 choices.

  • Finally, the '5s' station. You can take no 5s or one 5. That's (1+1)=2(1 + 1) = 2 choices.

Every unique combination makes a unique divisor! The total number of unique divisors is simply the product of your choices at each station: 4×3×2=244 \times 3 \times 2 = 24. This Combinatorics perspective turns abstract formulas into logical counting exercises.

2. The CAT Question Blueprint

The examiner will almost never ask "How many factors does 120 have?" That's too easy. Instead, they will:

  • Ask for the number of even or odd factors. (Constraining your choices at the '2s' station).

  • Ask for factors that are perfect squares or perfect cubes. (You can only pick powers that are multiples of 2 or 3).

  • Ask for the sum of the reciprocals of all factors.

  • Give you the total number of factors and ask you to reverse-engineer the minimum possible original number.

3. Core Concepts, Formulae & Derivations

Let the prime factorization of a number NN be:

N=p1a×p2b×p3c…N = p_1^a \times p_2^b \times p_3^c \dots

A. Total Number of Factors (Divisors)

T=(a+1)(b+1)(c+1)…T = (a+1)(b+1)(c+1)\dots

(Derived directly from the "buffet line" choices).

B. Sum of Factors

S=(p1a+1−1p1−1)×(p2b+1−1p2−1)×…S = \left( \frac{p_1^{a+1}-1}{p_1-1} \right) \times \left( \frac{p_2^{b+1}-1}{p_2-1} \right) \times \dots

(This is the product of geometric progressions representing the sum of choices at each station).

C. Number of Odd vs. Even Factors

  • Odd Factors: Ignore the prime 2 completely. Calculate the total factors using only the odd prime bases.

  • Even Factors: Total Factors - Odd Factors. (Or, at the '2s' station, you cannot choose 202^0. You have aa choices instead of a+1a+1).

D. Product of All Factors

P=NT/2P = N^{T/2}

(If N=12N=12, factors are 1, 2, 3, 4, 6, 12. Notice they form pairs that multiply to 12: 1×121\times12, 2×62\times6, 3×43\times4. There are T/2T/2 pairs).

(If NN is a perfect square, TT is odd, and the formula still holds valid!)

E. Expressing N as a Product of Two Factors

  • If NN is NOT a perfect square: Number of ways = T/2T / 2.

  • If NN is a perfect square: Number of ways = (T+1)/2(T + 1) / 2 if identical factors are allowed, or (T−1)/2(T - 1) / 2 if identical factors are excluded.

4. Common Pitfalls & Speed Shortcuts

  • Pitfall: Applying the formulas without fully resolving the base numbers to primes. For example, treating N=42×33N = 4^2 \times 3^3 directly. 44 is not prime! You must write it as 24×332^4 \times 3^3 before applying any formula.

  • Shortcut: If a number has an odd number of factors, it MUST be a perfect square. If it has a prime number of factors (like exactly 3 factors), it must be the square of a prime number (e.g., 25=5225 = 5^2, factors are 1, 5, 25).

Formulas

Total Number of Factors

T=(a+1)(b+1)(c+1)…T = (a+1)(b+1)(c+1)\dots

Bases p1, p2, p3 must be distinct prime numbers.
Sum of Factors

S=∏piai+1−1pi−1S = \prod \frac{p_i^{a_i+1}-1}{p_i-1}

Based on the sum of geometric progressions.
Product of Factors

P=NT/2P = N^{T/2}

Matches factors in pairs from the outermost inwards.

Traps and tips

  • Before applying any formula, verify that all bases are strictly prime.
  • A number with exactly 3 factors is always the square of a prime.
  • For the sum of factors, if a prime power is small (like 2^2), it's faster to just add (1+2+4) instead of using the formula.

Solved examples

The Odd and Even Split

Find the total number of factors, the number of even factors, and the number of odd factors for N=1080N = 1080.

Show solution

First, find the prime factorization of 1080.

1080=108×10=(27×4)×(2×5)=(33×22)×2×51080 = 108 \times 10 = (27 \times 4) \times (2 \times 5) = (3^3 \times 2^2) \times 2 \times 5

N=23×33×51N = 2^3 \times 3^3 \times 5^1.

1. Total Factors (T):

T=(3+1)(3+1)(1+1)=4×4×2=32T = (3+1)(3+1)(1+1) = 4 \times 4 \times 2 = 32.

2. Odd Factors:

To make an odd factor, we cannot use any 22s. So we completely ignore 232^3.

We only look at 33×513^3 \times 5^1.

Odd Factors = (3+1)(1+1)=4×2=8(3+1)(1+1) = 4 \times 2 = 8.

3. Even Factors:

Even Factors = Total Factors - Odd Factors = 32−8=2432 - 8 = 24.

(Alternatively, for even factors, we must pick at least one 2. So we have 3 choices for the base 2 (21,22,232^1, 2^2, 2^3) instead of 4. 3×4×2=243 \times 4 \times 2 = 24).

Takeaway: To find odd factors, completely drop the prime factor 2 and calculate normally.

Perfect Square Divisors

How many factors of N=25×34×52N = 2^5 \times 3^4 \times 5^2 are perfect squares?

Show solution

For a factor to be a perfect square, all its prime bases must have even exponents.

So, we can only choose even powers from our 'buffet'.

From 252^5, we can choose: 20,22,242^0, 2^2, 2^4. (3 choices)

From 343^4, we can choose: 30,32,343^0, 3^2, 3^4. (3 choices)

From 525^2, we can choose: 50,525^0, 5^2. (2 choices)

Total perfect square factors = 3×3×2=183 \times 3 \times 2 = 18.

Takeaway: For perfect square factors, count only the even exponents available for each prime base (including 0).

Summing the Fragments

Calculate the sum of all factors of 360360.

Show solution

First, factorize 360360:

360=36×10=23×32×51360 = 36 \times 10 = 2^3 \times 3^2 \times 5^1.

We use the sum of factors formula (or just sum the individual geometric progressions):

For base 2 (232^3): (20+21+22+23)=1+2+4+8=15(2^0 + 2^1 + 2^2 + 2^3) = 1 + 2 + 4 + 8 = 15.

For base 3 (323^2): (30+31+32)=1+3+9=13(3^0 + 3^1 + 3^2) = 1 + 3 + 9 = 13.

For base 5 (515^1): (50+51)=1+5=6(5^0 + 5^1) = 1 + 5 = 6.

Sum of all factors = Product of these sums.

S=15×13×6=15×78=1170S = 15 \times 13 \times 6 = 15 \times 78 = 1170.

Takeaway: The sum of factors is the product of the sums of all possible powers of each prime base.

The Product Phenomenon

What is the product of all factors of 144144?

Show solution

First, find the total number of factors (TT) for 144144.

144=122=(22×3)2=24×32144 = 12^2 = (2^2 \times 3)^2 = 2^4 \times 3^2.

Total factors T=(4+1)(2+1)=5×3=15T = (4+1)(2+1) = 5 \times 3 = 15.

Notice TT is odd, which makes sense because 144 is a perfect square.

The formula for the product of factors is P=NT/2P = N^{T/2}.

P=14415/2P = 144^{15/2}.

To evaluate this, rewrite 144 as 12212^2:

P=(122)15/2=1215P = (12^2)^{15/2} = 12^{15}.

The product of all factors of 144 is 121512^{15}.

Takeaway: The product of all factors is N^(T/2). If N is a perfect square, substitute N with x^2 to resolve the fractional exponent gracefully.

Reverse Engineering the Number

Find the smallest positive integer NN that has exactly 15 factors.

Show solution

We know the formula for total factors is T=(a+1)(b+1)(c+1)…T = (a+1)(b+1)(c+1)\dots

Here, T=15T = 15.

We need to express 15 as a product of integers greater than 1.

The ways to write 15 are:

  1. 1515 (a single prime base)

  2. 5×35 \times 3 (two prime bases)

Let's test these cases to find the minimum NN.

Case 1: T=15T = 15

This means (a+1)=15(a+1) = 15, so a=14a = 14.

The number is of the form p14p^{14}.

To minimize NN, choose the smallest prime, p=2p = 2.

N=214=16384N = 2^{14} = 16384.

Case 2: T=5×3T = 5 \times 3

This means (a+1)=5(a+1)=5 and (b+1)=3(b+1)=3, so a=4a=4 and b=2b=2.

The number is of the form p14×p22p_1^4 \times p_2^2.

To minimize NN, assign the largest exponent to the smallest prime.

So, p1=2p_1 = 2 and p2=3p_2 = 3.

N=24×32=16×9=144N = 2^4 \times 3^2 = 16 \times 9 = 144.

Comparing the two cases, 144144 is much smaller than 1638416384.

The smallest number with exactly 15 factors is 144.

Takeaway: To find the smallest number with a given number of factors, factorize the factor count, assign the resulting exponents in decreasing order to primes in increasing order (2, 3, 5...).

Product Splitting

In how many ways can 12001200 be expressed as a product of two co-prime factors?

Show solution

First, let's find the prime factorization of 1200.

1200=12×100=(22×3)×(22×52)=24×31×521200 = 12 \times 100 = (2^2 \times 3) \times (2^2 \times 5^2) = 2^4 \times 3^1 \times 5^2.

For two factors AA and BB to be co-prime, they cannot share any common prime bases. gcd⁡(A,B)=1\gcd(A, B) = 1.

This means all the 22s must go to either AA or BB. You cannot split the 242^4 into 222^2 and 222^2, otherwise they share a factor of 2.

Similarly, the 313^1 must go entirely to AA or BB.

The 525^2 must go entirely to AA or BB.

So, we have 3 distinct "prime blocks": (24)(2^4), (31)(3^1), (52)(5^2).

For each block, we have 2 choices (put it in AA or put it in BB).

Total arrangements = 23=82^3 = 8.

However, A×BA \times B is the same as B×AB \times A. The order of factors doesn't matter when expressing as a product of two factors.

So we divide by 2.

Ways = 23−1=22=42^{3 - 1} = 2^2 = 4.

The 4 ways are:

  1. 1×12001 \times 1200

  2. 16×7516 \times 75

  3. 3×4003 \times 400

  4. 25×4825 \times 48

Takeaway: The number of ways to express N as a product of two co-prime factors is 2^(k-1), where k is the number of distinct prime bases in N.

Practice questions

Question 1 · CAT Level

Let N=25×34×53×72N = 2^5 \times 3^4 \times 5^3 \times 7^2. How many positive divisors of NN are multiples of 1212 but not multiples of 180180?

  1. A

    72

  2. B

    84

  3. C

    96

  4. D

    108

Show answer and explanation

Answer: (B) 84

Any divisor has the form d=2a⋅3b⋅5c⋅7dd = 2^a \cdot 3^b \cdot 5^c \cdot 7^d with 0≤a≤50 \le a \le 5, 0≤b≤40 \le b \le 4, 0≤c≤30 \le c \le 3, and 0≤d≤20 \le d \le 2.

For dd to be a multiple of 12=22⋅3112 = 2^2 \cdot 3^1, we require a≥2a \ge 2 (44 choices) and b≥1b \ge 1 (44 choices), giving 4×4×4×3=1924 \times 4 \times 4 \times 3 = 192 divisors.

For dd to be a multiple of 180=22⋅32⋅51180 = 2^2 \cdot 3^2 \cdot 5^1, we require a≥2a \ge 2 (44 choices), b≥2b \ge 2 (33 choices), and c≥1c \ge 1 (33 choices).

This gives 4×3×3×3=1084 \times 3 \times 3 \times 3 = 108 multiples of 180180.

Since every multiple of 180180 is automatically a multiple of 1212, the required count is 192−108=84192 - 108 = 84.

Question 2 · CAT Level

How many ordered pairs of non-zero integers (x,y)(x, y) satisfy the equation:

1x+1y=120\frac{1}{x} + \frac{1}{y} = \frac{1}{20}

  1. A

    15

  2. B

    28

  3. C

    29

  4. D

    30

Show answer and explanation

Answer: (C) 29

Rearranging gives 20(x+y)=xy  ⟹  xy−20x−20y+400=40020(x + y) = xy \implies xy - 20x - 20y + 400 = 400, which factors as (x−20)(y−20)=400(x - 20)(y - 20) = 400.

Here 400=202=24×52400 = 20^2 = 2^4 \times 5^2, so the total number of positive divisors is d(400)=(4+1)(2+1)=15d(400) = (4+1)(2+1) = 15.

For positive factors of 400400, each divisor pair (u,v)(u, v) with uv=400uv = 400 gives valid non-zero positive solutions x=u+20,y=v+20x = u+20, y = v+20 (1515 pairs).

For negative factors, (x−20)(y−20)=(−u)(−v)=400(x-20)(y-20) = (-u)(-v) = 400 gives x=20−ux = 20 - u and y=20−vy = 20 - v.

If u=20u = 20, then x=20−20=0x = 20 - 20 = 0, making 1x\frac{1}{x} undefined; all other 1414 negative factor pairs yield valid non-zero integers.

Thus, the total number of integer solutions is 15+14=2915 + 14 = 29.

Question 3 · CAT Level

A positive integer NN has exactly 1515 factors, and 2N2N has exactly 2020 factors. How many factors does N2N^2 have?

  1. A

    30

  2. B

    45

  3. C

    50

  4. D

    60

Show answer and explanation

Answer: (B) 45

Let the prime factorization of NN be 2a⋅p1b1…pkbk2^a \cdot p_1^{b_1} \dots p_k^{b_k}.

The number of factors is d(N)=(a+1)K=15d(N) = (a+1)K = 15, where K=∏(bi+1)K = \prod (b_i+1).

Multiplying by 22 increments the power of 22 by 11, so d(2N)=(a+2)K=20d(2N) = (a+2)K = 20.

Dividing the two equations gives a+2a+1=2015=43  ⟹  3a+6=4a+4  ⟹  a=2\frac{a+2}{a+1} = \frac{20}{15} = \frac{4}{3} \implies 3a + 6 = 4a + 4 \implies a = 2.

Substituting a=2a=2 into (a+1)K=15(a+1)K = 15 yields 3K=15  ⟹  K=53K = 15 \implies K = 5, which implies N=22⋅p4N = 2^2 \cdot p^4 for some odd prime pp.

Then N2=24⋅p8N^2 = 2^4 \cdot p^8.

Hence, the number of factors of N2N^2 is (4+1)(8+1)=5×9=45(4+1)(8+1) = 5 \times 9 = 45.

Question 4 · CAT Level

Let SS be the set of all positive divisors of N=3600N = 3600. How many ordered pairs of divisors (d1,d2)∈S×S(d_1, d_2) \in S \times S are relatively prime (i.e., gcd⁡(d1,d2)=1\gcd(d_1, d_2) = 1)?

  1. A

    180

  2. B

    210

  3. C

    225

  4. D

    245

Show answer and explanation

Answer: (C) 225

Factor N=3600=24×32×52N = 3600 = 2^4 \times 3^2 \times 5^2. Any pair of divisors d1=2x13x25x3d_1 = 2^{x_1} 3^{x_2} 5^{x_3} and d2=2y13y25y3d_2 = 2^{y_1} 3^{y_2} 5^{y_3} satisfy gcd⁡(d1,d2)=1\gcd(d_1, d_2) = 1 if and only if min⁡(xi,yi)=0\min(x_i, y_i) = 0 for each prime.

For a prime pip_i with maximum power aia_i, the pair of exponents (xi,yi)(x_i, y_i) can be:

  • xi=0x_i = 0 with yi∈{0,1,…,ai}y_i \in \{0, 1, \dots, a_i\} (ai+1a_i + 1 choices),

  • yi=0y_i = 0 with xi∈{1,2,…,ai}x_i \in \{1, 2, \dots, a_i\} (aia_i choices).

Thus, each prime provides (ai+1)+ai=2ai+1(a_i + 1) + a_i = 2a_i + 1 independent choices.

Applying this product across all prime factors yields (2×4+1)(2×2+1)(2×2+1)=9×5×5=225(2 \times 4 + 1)(2 \times 2 + 1)(2 \times 2 + 1) = 9 \times 5 \times 5 = 225.

Therefore, there are exactly 225225 ordered pairs of co-prime divisors.

Question 5 · CAT Level

For how many positive integers n≤1000n \le 1000 is the sum of all positive divisors of nn, denoted σ(n)\sigma(n), an odd integer?

  1. A

    31

  2. B

    42

  3. C

    53

  4. D

    64

Show answer and explanation

Answer: (C) 53

Let n=2a⋅p1b1…pkbkn = 2^a \cdot p_1^{b_1} \dots p_k^{b_k}. The sum of divisors is σ(n)=(1+2+⋯+2a)∏i=1k(1+pi+⋯+pibi)\sigma(n) = (1 + 2 + \dots + 2^a) \prod_{i=1}^k (1 + p_i + \dots + p_i^{b_i}).

The term (1+2+⋯+2a)=2a+1−1(1 + 2 + \dots + 2^a) = 2^{a+1} - 1 is always odd for any integer a≥0a \ge 0.

For each odd prime pip_i, the geometric sum contains bi+1b_i + 1 odd terms, which is odd if and only if bi+1b_i + 1 is odd, meaning bib_i is even.

Thus, σ(n)\sigma(n) is odd if and only if all odd prime factors have even exponents, which occurs if and only if nn is either a perfect square or 22 times a perfect square.

Case 1 (perfect square): k2≤1000  ⟹  k∈{1,2,…,31}k^2 \le 1000 \implies k \in \{1, 2, \dots, 31\} (3131 values).

Case 2 (2×2 \times square): 2m2≤1000  ⟹  m2≤500  ⟹  m∈{1,2,…,22}2m^2 \le 1000 \implies m^2 \le 500 \implies m \in \{1, 2, \dots, 22\} (2222 values).

These two sets are disjoint (differing in parity of the power of 22), giving a total of 31+22=5331 + 22 = 53 integers.

Study this concept with interactive practice in PrepSoc.

Open the concept library