Paper I · 9 Logical Reasoning & Analytical Ability · 9.1 Number system and simplification
9.1.10 Counting factors: number and sum of factors, perfect squares and co-primes
Write N as a product of prime powers once; the number, sum and product of its factors, and every "how many factors are …" question, then follow by counting choices of exponents.
- APPSC Paper I · Paper I
- Standard level
- 6 min read
- Free
Core facts
- Let N = pᵃ × qᵇ × rᶜ (p, q, r distinct primes).
- Number of factors = (a + 1)(b + 1)(c + 1). (Each prime's exponent can be 0 to a.)
- Sum of factors = (1 + p + … + pᵃ)(1 + q + … + qᵇ)(1 + r + … + rᶜ).
- Product of factors = N^(d/2), where d is the number of factors.
- Odd factors: ignore the power of 2. Even factors = total − odd.
- Perfect squares (and only they) have an odd number of factors.
- A number has exactly 3 factors only if it is the square of a prime.
- Perfect number: sum of its factors other than itself equals the number (6, 28, 496).
- Co-primes up to N (Euler's φ): φ(N) = N × (1 − 1/p)(1 − 1/q)(1 − 1/r).
Example 1. How many factors does 540 have? Solution. 540 = 2² × 3³ × 5. Factors = 3 × 4 × 2. Answer: 24
Example 2. Find the sum of the factors of 72. Solution. 72 = 2³ × 3². Sum = (1 + 2 + 4 + 8)(1 + 3 + 9) = 15 × 13. Answer: 195
Example 3. Does 196 have an odd or even number of factors? Solution. 196 = 14² = 2² × 7², a perfect square: 3 × 3 = 9 factors. Answer: odd (9)
Explained
Type 1: odd and even factors.
Example 4. How many even factors does 2,160 have? (a) 8 (b) 24 (c) 32 (d) 40 Solution. 2,160 = 2⁴ × 3³ × 5. Total = 5 × 4 × 2 = 40. Odd = 4 × 2 = 8. Even = 40 − 8. Answer: (c) 32
Type 2: factors that are multiples of k. Force the primes of k into the factor; count the remaining choices.
Example 5. How many factors of 1,080 are divisible by 6? Solution. 1,080 = 2³ × 3³ × 5. A factor divisible by 6 needs 2 to the power 1–3 (3 choices), 3 to the power 1–3 (3 choices), 5 to the power 0–1 (2 choices). 3 × 3 × 2. Answer: 18
- Shortcut: factors of N divisible by k = factors of N/k (here 1,080/6 = 180 = 2² × 3² × 5 → 18).
Type 3: perfect-square factors. Allow only even exponents.
Example 6. How many factors of 3,600 are perfect squares? Solution. 3,600 = 2⁴ × 3² × 5². Even exponents: 2 → {0, 2, 4} = 3; 3 → {0, 2} = 2; 5 → {0, 2} = 2. 3 × 2 × 2. Answer: 12
Type 4: product of factors.
Example 7. Find the product of all factors of 36. Solution. 36 has 9 factors. Product = 36^(9/2) = 6⁹. Answer: 6⁹
Type 5: ways to write N as a product of two factors. Unordered pairs = d/2 for a non-square; (d + 1)/2 for a square (counting k × k once).
Example 8. In how many ways can 420 be written as a product of two natural numbers (order not counted)? And 144? Solution. 420 = 2² × 3 × 5 × 7 has 24 factors → 12 pairs. 144 = 2⁴ × 3² has 15 factors → (15 + 1)/2 = 8. Answer: 12; 8
Type 6: co-prime count.
Example 9. How many numbers from 1 to 60 are co-prime to 60? Solution. 60 = 2² × 3 × 5. φ = 60 × 1/2 × 2/3 × 4/5. Answer: 16
Example 10. Sum of the odd factors of 360. Solution. Odd part of 360 = 3² × 5. Sum = (1 + 3 + 9)(1 + 5) = 13 × 6. Answer: 78
Speed tips.
- Always factorise completely before using a formula; 3,600 is 2⁴ × 3² × 5², not 36 × 100.
- For "divisible by k" use the N/k shortcut; for "not divisible by k" subtract from the total.
Common traps
- ✗ "Factors of 2⁴ × 3³ × 5 = 4 × 3 × 1 = 12." ✓ Add 1 to every exponent: 5 × 4 × 2 = 40.
- ✗ "Even factors = half the total." ✓ Even = total − odd: for 2,160, 40 − 8 = 32.
- ✗ "Ways to write 144 as a product of two numbers = 15/2." ✓ For a square add 1 first: (15 + 1)/2 = 8.
- ✗ "Smallest number with 12 factors is 2¹¹ or 72." ✓ Try every exponent pattern: 60 = 2² × 3 × 5.
- ✗ "A number with exactly 3 factors can be any square." ✓ It must be the square of a prime (36 has 9 factors).
Quick revision
- N = pᵃqᵇrᶜ: factors (a+1)(b+1)(c+1).
- Sum of factors: product of (1 + p + … + pᵃ).
- Product of factors: N^(d/2).
- Odd factors: drop the 2s; even = total − odd.
- Factors divisible by k = factors of N/k.
- Square factors: even exponents only.
- Odd number of factors ⇔ perfect square.
- Exactly 3 factors ⇔ square of a prime.
- φ(N) = N(1 − 1/p)(1 − 1/q)…; sum of co-primes below N = Nφ(N)/2.
- Smallest with d factors: largest exponent on the smallest prime, try all patterns.
Go deeper: Deeper (beyond what APPSC Paper I usually asks)
Deeper Advanced
Example 11. Smallest natural number with exactly 12 factors. (a) 48 (b) 60 (c) 72 (d) 96 Solution. 12 = 12, 6 × 2, 4 × 3 or 3 × 2 × 2, giving exponent patterns 11; 5,1; 3,2; 2,1,1. Give the largest exponent to the smallest prime: 2¹¹ = 2,048; 2⁵ × 3 = 96; 2³ × 3² = 72; 2² × 3 × 5 = 60. Answer: (b) 60
Example 12. How many numbers from 1 to 100 have exactly three factors? Solution. They are squares of primes: 2², 3², 5², 7² (11² = 121 is too big). Answer: 4
Example 13. Caselet. 100 bulbs, numbered 1 to 100, are all off. Person k toggles every bulb whose number is a multiple of k, for k = 1 to 100. How many bulbs are on at the end? Solution. Bulb n is toggled once for each factor of n. It ends on only if it has an odd number of factors, that is, if n is a perfect square: 1, 4, …, 100. Answer: 10
Example 14. Find the sum of all numbers below 60 that are co-prime to 60. Solution. Co-primes come in pairs k and 60 − k, each pair adding to 60. There are φ(60) = 16 of them, so 8 pairs. Answer: 480
- General: sum of numbers below N co-prime to N = N × φ(N)/2 (N > 2).
Example 15. How many factors of 1,800 are multiples of 10 but not of 20? Solution. 1,800 = 2³ × 3² × 5². Multiples of 10: 1,800/10 = 180 = 2² × 3² × 5 → 18. Multiples of 20: 1,800/20 = 90 = 2 × 3² × 5 → 12. 18 − 12. Answer: 6
Practise this topic. Questions on Numerical ability, with answers explained.
All Number system and simplification notes · APPSC Paper I syllabus · APPSC Paper I Mock 1 with answers · Start free
Medha AI writes its own notes and checks them against the sources listed. Medha AI is an independent preparation service. It is not affiliated with, endorsed by or connected to APPSC, TSPSC, MPSC, UPSC or any other commission or government body.