◆ QA · Number System

Factors & Divisibility , formulas + CAT PYQs

Focused Number System kit. The full chapter formula sheet (with explanations & basic examples) is tucked below; every CAT PYQ for Factors & Divisibility is here.

14CAT PYQs
Number Systemchapter
Formulas PYQs (14)↩ Full Number System chapter

Number System, formula sheet

Show the full Number System formula sheet (explanations + basic examples)
1Divisibility by 2, 4, 8 (powers of 2)
  • By 2: last digit is 0, 2, 4, 6 or 8.
  • By 4: last two digits divisible by 4 (or both zero).
  • By 8: last three digits divisible by 8 (or all zero).
  • General rule: divisible by 2ⁿ if the last n digits are divisible by 2ⁿ.
  • Use it to test divisibility by a power of 2 without dividing the whole number.
  • e.g. 1316 → last two digits 16, and 16 ÷ 4 = 4, so 1316 is divisible by 4.
N divisible by 2ⁿ ⇔ last n digits divisible by 2ⁿ
2Divisibility by 3 and 9
  • By 3: digit-sum is divisible by 3.
  • By 9: digit-sum is divisible by 9.
  • Just add the digits, if that small sum passes, the whole number does.
  • e.g. 4527 → 4+5+2+7 = 18, divisible by both 3 and 9, so 4527 is too.
3 | N ⇔ 3 | (sum of digits)
3Divisibility by 5, 6, 12
  • By 5: last digit is 0 or 5.
  • By 6: divisible by its co-prime factors 2 and 3 (6 = 2 × 3).
  • By 12: divisible by both 3 and 4.
  • For any composite, test divisibility by its co-prime factors.
  • Break a composite divisor into co-prime parts and check each separately.
  • e.g. 132 is divisible by 12 because it is divisible by 3 (1+3+2=6) and by 4 (last two digits 32).
6 | N ⇔ 2 | N and 3 | N
4Divisibility by 7, 11, 13 (grouping)
  • Make groups of three digits from the right.
  • Take (sum of odd-placed groups) − (sum of even-placed groups).
  • If that difference is divisible by 7 / 11 / 13, so is N.
  • Same grouping rule works for all three primes.
  • Lets you test big numbers for 7, 11 or 13 using small 3-digit chunks.
  • e.g. 1001 = 7×11×13, so any 3-digit block repeated (e.g. 256256) is divisible by all three.
e.g. 346527659 → (346+659)−527 = 478 ÷ 7
5Divisibility by 11 (alternating sum)
  • Take (sum of odd-placed digits) − (sum of even-placed digits).
  • If the difference is divisible by 11, the number is too.
  • Quick single-digit alternating add/subtract test for 11.
  • e.g. 918082 → (9+8+8) − (1+0+2) = 25 − 3 = 22, divisible by 11, so 918082 is too.
11 | N ⇔ 11 | (Σ odd-pos − Σ even-pos)
6Osculation (13, 17)
  • For 13: one-more osculator 4, drop last digit, add 4 × (last digit), repeat.
  • For 17: negative osculator 5, drop last digit, subtract 5 × (last digit), repeat.
  • A shrink-and-repeat trick to test 13 or 17 when no other rule is handy.
  • e.g. 13 itself: 1 + 3×4 = 13 → divisible by 13.
1859 → 185+9×4 = 221 → 22+1×4 = 26 (÷13)
7Number families
  • Natural N = {1, 2, 3…}; Whole W = N ∪ {0}.
  • Integers Z = {… −2, −1, 0, 1, 2 …}.
  • Rational = p/q, q ≠ 0 (terminating or recurring decimals).
  • Irrational = non-terminating, non-recurring (√2, √3, π).
  • Complex a + ib; conjugate of a + ib is a − ib.
  • Knowing which set a number lives in tells you what operations stay "closed".
  • e.g. 0.75 = 3/4 is rational; √2 = 1.41421… never repeats, so it is irrational.
8Prime & composite
  • A prime has exactly two factors: 1 and itself.
  • Primes > 3 are of the form 6k ± 1 (converse not always true).
  • 1 is neither prime nor composite; 2 is the only even prime.
  • The 6k±1 form lets you scan candidates for primes quickly.
  • e.g. 7 = 6×1+1 and 11 = 6×2−1 are prime; but 25 = 6×4+1 is not (converse fails).
primes > 3 ⇒ 6k ± 1
9Primality test
  • Pick the smallest n with n² > N.
  • Check divisibility by every prime < n.
  • If none divides N, then N is prime.
  • You only need to test primes up to √N, not all the way to N.
  • e.g. 97: √97 ≈ 9.8, test 2,3,5,7, none divides 97, so it is prime.
check primes p ≤ √N
10Co-prime (relatively prime)
  • Two numbers with no common factor except 1.
  • 1 is co-prime to every number; two consecutive integers are co-prime.
  • A prime is co-prime to all numbers except its multiples; two primes are always co-prime.
  • Co-prime numbers can be tested for divisibility independently (used in rules above).
  • e.g. 8 and 15 share no common factor except 1, so HCF(8,15) = 1, they are co-prime.
11Fractions
  • Proper: value < 1 (numerator < denominator).
  • Improper: value > 1 (numerator > denominator).
  • Mixed: integer + proper fraction, e.g. 2¾.
  • Classifying a fraction tells you at a glance whether its value is below or above 1.
  • e.g. 3/5 is proper (< 1); 7/5 is improper (> 1) = mixed 1⅖.
12Prime factorisation form
  • Any composite N can be written with distinct primes a, b, c…
  • This standard form drives the factor, sum and product formulas below.
  • Write any number as primes-to-powers first; every counting formula needs it.
  • e.g. 360 = 2³ × 3² × 5¹.
N = aᵖ × bᑫ × cʳ …
13Number of factors
  • Add 1 to each prime's exponent and multiply.
  • Count includes 1 and N itself.
  • The fastest way to count all divisors of a number.
  • e.g. 360 = 2³×3²×5 → (3+1)(2+1)(1+1) = 4×3×2 = 24 factors.
X = (p+1)(q+1)(r+1)…
14As a product of two factors
  • If X (total factors) is even: X/2 ways.
  • If X is odd: (X+1)/2 ways (N is a perfect square).
  • As a product of two distinct factors: (X−1)/2 ways.
  • Counts the ways to write N as (one factor) × (another factor).
  • e.g. 12 has 6 factors → 6/2 = 3 ways: 1×12, 2×6, 3×4.
even X → X/2 · odd X → (X+1)/2
15Perfect squares ↔ factor count
  • A perfect square has an odd number of factors, and vice-versa.
  • Use it to spot or confirm a perfect square just from its factor count.
  • e.g. 100 = 2²×5² has 9 factors → expressible as a product of two numbers in 5 ways.
  • e.g. 36 = 2²×3² has (2+1)(2+1) = 9 factors (odd), and 36 = 6² is a perfect square.
odd #factors ⇔ perfect square
16Sum & product of factors
  • Sum of all factors of N = aᵖ × bᑫ × cʳ.
  • Product of all factors = N raised to (X/2), X = total factors.
  • Gives the total of, or product of, every divisor without listing them.
  • e.g. 12 = 2²×3 → sum of factors = (2³−1)/(2−1) × (3²−1)/(3−1) = 7 × 4 = 28 (=1+2+3+4+6+12).
Sum = (aᵖ⁺¹−1)/(a−1) × (bᑫ⁺¹−1)/(b−1) × … Product = N^(X/2)
17Cyclicity of unit digits
  • The last digit of powers repeats in a fixed cycle.
  • To find a unit digit, reduce the exponent mod the cyclicity.
  • Lets you find the last digit of any huge power instantly.
  • e.g. 2¹⁰: cycle of 2 is 2,4,8,6 (length 4); 10 mod 4 = 2 → 2nd in cycle = 4. (2¹⁰=1024 ✓)
2,3,7,8 → cycle 4 · 4,9 → cycle 2 · 0,1,5,6 → cycle 1
18Last two digits, base ends in 1
  • For (…a1)^(…b): tens digit = last digit of (a × b); units digit = 1.
  • Fast last-two-digits shortcut when the base ends in 1.
  • e.g. 31¹²: a=3, b=2, a×b=6 → last two digits are 61.
(…a1)^(…b) → [last digit of a×b] then 1
19Last two digits, base ends in 5
  • If the second-last digit of base and the power are both odd → ends in 75.
  • Otherwise → ends in 25.
  • One-glance rule for the last two digits of any power of a number ending in 5.
  • e.g. 35³: tens digit 3 (odd) and power 3 (odd) → ends in 75. (35³ = 42875 ✓)
both odd → 75, else → 25
20Last two digits, ends in 3, 7, 9
  • Convert the base to a power that ends in 1, then use rule 18.
  • e.g. 7² = 49, 7⁴ = …01 → reduce the exponent through that.
  • Turn an awkward base into one ending in 1, then apply rule 18.
  • e.g. 7¹²: 7⁴ ends in 01, so 7¹² = (7⁴)³ ends in 01.
21Highest power of a prime in n!
  • Sum the quotients of n divided by p, p², p³, … (floor each).
  • Tells you the largest power of a prime that divides n! (e.g. for trailing zeros).
  • e.g. power of 5 in 25! = ⌊25/5⌋ + ⌊25/25⌋ = 5 + 1 = 6.
E(p, n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …
22Highest power of a composite in n!
  • Split the composite into co-prime factors and find each one's power.
  • The lowest of those powers is the answer.
  • e.g. power of 10 in 30! = min(power of 2, power of 5) = min(26, 7) = 7.
  • For a composite, the scarcest prime-power limits the answer, use it for trailing zeros.
  • e.g. trailing zeros in 30! = power of 5 (the scarcer of 2 and 5) = ⌊30/5⌋+⌊30/25⌋ = 7.
10 = 2×5 ⇒ take the smaller power
23HCF (GCD)
  • Factorisation: product of least powers of common primes.
  • Division: divide larger by smaller, then divisor by remainder, repeat until remainder 0; last divisor is the HCF.
  • HCF is the largest number that divides all the given numbers.
  • e.g. HCF(12, 18): 12 = 2²×3, 18 = 2×3² → common least powers 2¹×3¹ = 6.
24LCM
  • Factorisation: product of highest powers of all primes present.
  • Division: divide the row by common factors until none share a factor; multiply divisors × leftovers.
  • LCM is the smallest number that every given number divides into.
  • e.g. LCM(12, 18): take highest powers 2²×3² = 36.
25HCF & LCM of fractions
  • Reduce fractions to lowest terms first.
  • How to take HCF/LCM when the quantities are fractions, not whole numbers.
  • e.g. HCF(2/3, 4/9) = HCF(2,4)/LCM(3,9) = 2/9.
HCF = HCF(num)/LCM(den) LCM = LCM(num)/HCF(den)
26HCF × LCM identity
  • For two numbers: HCF × LCM = product of the numbers.
  • For n numbers: product = (HCF)ⁿ⁻¹ × LCM.
  • If HCF(a,b) = H, then (a+b) and (a−b) are also divisible by H.
  • Once you know one of HCF/LCM and the numbers, the other follows for free.
  • e.g. a=12, b=18: HCF×LCM = 6×36 = 216 = 12×18. ✓
HCF × LCM = a × b
27Remainder-based HCF / LCM
  • Same remainder p, q, r when divided by H ⇒ H is HCF of (a−p), (b−q), (c−r).
  • Constant remainder R from a, b, c ⇒ N = LCM(a,b,c)·k + R.
  • If a−x = b−y = c−z = P, smallest number = LCM(a,b,c) − P.
  • Handles "leaves the same / a fixed remainder" word problems via HCF or LCM.
  • e.g. smallest number leaving remainder 3 by both 4 and 6 = LCM(4,6) + 3 = 15.
28Division algorithm
  • Dividend = Divisor × Quotient + Remainder.
  • The basic identity linking dividend, divisor, quotient and remainder.
  • e.g. 17 ÷ 5: 17 = 5×3 + 2, so quotient 3, remainder 2.
M = N·Q + R, 0 ≤ R < N
29Reducing remainders
  • Remainders distribute across × + and −.
  • Rem(a×b / c) = Rem(a/c) × Rem(b/c), then reduce again.
  • Rem((a±b)/c) = Rem(a/c) ± Rem(b/c).
  • Break a big product/sum into small remainders and recombine, avoids huge arithmetic.
  • e.g. Rem(17×19 / 5) = Rem(2×4 / 5) = Rem(8/5) = 3.
Rem(ab/c) = [Rem(a/c)·Rem(b/c)] mod c
30Negative remainders
  • Write the base as (multiple of divisor ± 1) to simplify large powers.
  • e.g. 15⁹⁷ / 8 = (16−1)⁹⁷ / 8 = (−1)⁹⁷ → remainder 8 − 1 = 7.
  • Rewriting the base as "divisor ± 1" makes powers collapse to ±1.
  • e.g. 9¹⁰⁰ / 10 = (10−1)¹⁰⁰ ≡ (−1)¹⁰⁰ = 1 (mod 10) → remainder 1.
(16−1)⁹⁷ ≡ (−1)⁹⁷ ≡ −1 ≡ 7 (mod 8)
31Fermat's little theorem
  • If M and N are co-prime and N is prime, then M^(N−1) leaves remainder 1 on division by N.
  • A power-of-1 shortcut for remainders when the divisor is prime.
  • e.g. 3⁶ mod 7 = 1 (since 7 prime, gcd(3,7)=1). (3⁶ = 729 = 7×104 + 1 ✓)
M^(N−1) ≡ 1 (mod N), N prime, gcd(M,N)=1
32Wilson's theorem
  • For prime N, (N−1)! + 1 is divisible by N.
  • A neat test/shortcut tying factorials to primality.
  • e.g. N=5: (5−1)! + 1 = 24 + 1 = 25 = 5×5, divisible by 5. ✓
(N−1)! + 1 ≡ 0 (mod N), N prime
33aⁿ ± bⁿ divisibility
  • aⁿ + bⁿ is divisible by (a + b) when n is odd.
  • aⁿ − bⁿ is divisible by (a − b) always; also by (a + b) when n is even.
  • Useful identity: if a + b + c = 0 then a³ + b³ + c³ = 3abc.
  • Instantly spots a factor of expressions like aⁿ ± bⁿ.
  • e.g. 3³ + 2³ = 35 is divisible by 3 + 2 = 5 (odd power). (35 = 5×7 ✓)
aⁿ+bⁿ ÷ (a+b) for odd n
34Base systems
  • Base-10: 101 = 1×10² + 0×10¹ + 1×10⁰.
  • Convert base-10 → base B by repeated division by B; read remainders bottom-up.
  • For base > 10, digits 10, 11, 12… are written A, B, C…
  • Converts numbers between base-10 and any other base.
  • e.g. 13 in base 2: 13 = 8+4+1 = 1101₂. Back: 1×8+1×4+0×2+1 = 13. ✓
(dₙ…d₁d₀)_B = Σ dᵢ × Bⁱ
14 CAT questions

Practice questions generated · up to 100

Original easy-hard warm-up drills (not CAT PYQs). Pick the levels, generate a set, reveal answers.

Factors & Divisibility, CAT PYQs

Factors & Divisibility

ModerateCAT 1991

To decide whether a number of n digits is divisible by 7, we can define a process by which its magnitude is reduced as follows: (i₁, i₂, i₃, … , are the digits of the number, starting from the most significant digit). i₁, i₂, ……. iₙ ⇒ i₁·3ⁿ⁻¹ + i₂·3ⁿ⁻² + ……… + iₙ·3⁰. e.g., 259 ⇒ 2·3² + 5·3¹ + 9·3⁰ = 18 + 15 + 9 = 42. Ultimately the resulting number will be seven after repeating the above process a certain number of times. After how many such stages, does the number 203 reduce to 7?

  • (1) 2
  • (2) 3
  • (3) 4
  • (4) 1
Show solution
(1) 2. 203 ⇒ 2·3² + 0·3¹ + 3·3⁰ = 18 + 0 + 1 = 21. Then 21 ⇒ 2·3¹ + 1·3⁰ = 6 + 1 = 7. Therefore we can reduce 203 to 7 in 2 stages.
ModerateCAT 1998

A number is formed by writing first 54 natural numbers in front of each other as 12345678910111213… Find the remainder when this number is divided by 8:

  • (1) 1
  • (2) 7
  • (3) 2
  • (4) 0
Show solution
(3) 2. Divisibility by 8 depends only on the last three digits. The last 3 digits of this number is 354. The remainder is 2 if we divide 354 by 8.
ModerateCAT 2000

Let N = 55³ + 17³ − 72³. N is divisible by

  • (1) both 7 and 13
  • (2) both 3 and 13
  • (3) both 17 and 7
  • (4) both 3 and 17
Show solution
(4) both 3 and 17. We know, if a + b + c = 0 then a³ + b³ + c³ = 3abc. Now, 55³ + 17³ − 72³ = 3(55)(17)(−72). Hence, N is divisible by both 3 and 17.
ModerateCAT 2000

Let S be the set of prime numbers greater than or equal to 2 and less than 100. Multiply all elements of S. With how many consecutive zeros will the product end?

  • (1) 1
  • (2) 4
  • (3) 5
  • (4) 10
Show solution
(1) 1. There is only one 5 and one 2 in the set of prime numbers from 2 to 100. Hence, there would be only one zero at the end of the resultant product.
ModerateCAT 2001

Let b be a positive integer and a = b² − b. If b ≥ 4, then a² − 2a is divisible by:

  • (1) 15
  • (2) 20
  • (3) 24
  • (4) None of these
Show solution
(3) 24. a = b² − b, hence a² − 2a = (b² − b)² − 2(b² − b) = (b − 2)(b − 1) b (b + 1). These are 4 consecutive numbers and since b ≥ 4, these must be divisible by 4! or 24.
ModerateCAT 2002

For all integers n > 0, 7⁶ⁿ − 6⁶ⁿ is divisible by

  • (1) 13
  • (2) 549
  • (3) 127
  • (4) All of these
Show solution
(4) All of these. 7⁶ⁿ − 6⁶ⁿ is in the form of a³ − b³, and a³ − b³ is always divisible by a − b. So it must be divisible by 7² − 6² i.e., 13. 7⁶ⁿ − 6⁶ⁿ is also in the form of a² − b², so it must be divisible by (a + b) and (a − b) i.e., 7³ − 6³ and 7³ + 6³. ⇒ it is divisible by 343 − 216 = 127 and 343 + 216 = 559. Hence, all of these are correct.
ModerateCAT 2003

Let n (>1) be a composite integer such that √n is not an integer. Consider the following statements (a) n has a perfect integer−valued divisor which is greater than 1 and less than √n. (b) n has a perfect integer−valued divisor which is greater than √n but less than n. Then,

  • (1) Both A and B are false
  • (2) A is true but B is false
  • (3) A is false but B is true
  • (4) Both A and B are true
Show solution
(4) Both A and B are true. Consider a number n = 12, then root n = 3.46. Statement (a): we have a divisor 2 which is greater than 1 and less than 3.46. Statement (b): we have a divisor 4 which is greater than 3.46 but less than 10. Both statements (a) and (b) are true. We know if a number has even number of factors then it is not a perfect square. Rule: If 'N' is not a perfect square then there exists at least one number less than √N and another number greater than √N whose product is N. Hence, both.
HardCAT 2005

The digits of a three digit number A are written in the reverse order to form another three digit number B. If B > A and B − A is perfectly divisible by 7, then which of the following is necessarily true?

  • (1) 100 < A < 299
  • (2) 106 < A < 305
  • (3) 112 < A < 311
  • (4) 118 < A < 317
Show solution
(3) 112 < A < 311. Let A = abc. Then, B = cba. Given B > A, hence c > a. As B − A = (100c + 10b + a) − (100a + 10b + c). Hence, B − A = 100(c − a) + (a − c) = 99(c − a). Also (B − A) is divisible by 7. But 99 is not divisible by 7. Therefore (c − a) must be divisible by 7, i.e. (c − a) must be 7, since c and a are single digits. The possible values of (c, a) {with c > a} are (9, 2) and (8, 1). Thus we can write A as 2b9 or 1b8. As b can take values from 0 to 9, the smallest and largest possible value of A are 108 and 299.
ModerateCAT 2005

Let S be a set of positive integers such that every element n of S satisfies the conditions: (a) 1000 ≤ n ≤ 1200; (b) every digit in n is odd. Then how many elements of S are divisible by 3?

  • (1) 9
  • (2) 10
  • (3) 11
  • (4) 12
Show solution
(1) 9. All digits are odd and it is a 4-digit number in [1000, 1200], so it has the form 11bc with b, c ∈ {1, 3, 5, 7, 9}. Digit-sum = 1 + 1 + b + c = 2 + b + c must be divisible by 3, i.e. b + c ≡ 1 (mod 3). Since b, c are odd, b + c is even, so b + c ∈ {4, 10, 16}: b + c = 4 (2 ways), b + c = 10 (5 ways), b + c = 16 (2 ways) → 9 numbers.
HardCAT 2008

Suppose, the seed of any positive integer n is defined as follows: seed(n) = n, if n < 10; = seed(s(n)), otherwise, where s(n) indicates the sum of digits of n. i.e., seed(7) = 7, seed(248) = seed(2 + 4 + 8) = seed(14) = seed(1 + 4) = seed(5) = 5 etc. How many positive integers n, such that n < 500, will have seed(n) = 9?

  • (1) 39
  • (2) 72
  • (3) 81
  • (4) 55
Show solution
(4) 55. The seed(n) function gives the digit-sum (digital root) of any given number n. All the numbers n for which seed(n) = 9 will give multiples of 9. For all positive integers n, n < 500, there are 55 multiples of 9.
HardCAT 2018TITA

If N and x are positive integers such that Nᴺ = 2¹⁶⁰ and N² + 2ᴺ is an integral multiple of 2ˣ, then the largest possible x is

Show solution
10. Nᴺ = 2¹⁶⁰ = (2⁵)³² = 32³², so N = 32. Then N² + 2ᴺ = 32² + 2³² = 2¹⁰ + 2³² = 2¹⁰(1 + 2²²). Hence, the largest possible value of x is 10.
HardCAT 2018

If A = {6²ⁿ − 35n − 1}, and B = {35(n − 1)}, where n = 1, 2, 3,... then which of the following is true?

  • (1) Every member of A is in B and at least one member of B is not in A
  • (2) Neither every member of A is in B nor every member of B is in A
  • (3) Every member of B is in A
  • (4) At least one member of A is not in B
Show solution
(1). Given A = 6²ⁿ − 35n − 1 = 36ⁿ − 1 − 35n, which is divisible by 35. Hence A = 1225, 46650 etc., for n = 2, 3. Set B = 35, 70, 105 for n = 2, 3, 4 etc. Hence A misses some multiples while B has all the multiples of 35. So every member of set A will be in B, while every member of set B will not necessarily be in set A.
ModerateCAT 2020

How many of the integers 1, 2, … , 120, are divisible by none of 2, 5 and 7?

  • (1) 41
  • (2) 42
  • (3) 43
  • (4) 44
Show solution
(1) 41. Total integers = 1, 2, 3, ……. 120. Mul(2 or 5 or 7) = Mul(2) + Mul(5) + Mul(7) − Mul(2 & 5) − Mul(2 & 7) − Mul(5 & 7) + Mul(2 & 5 & 7) = 60 + 24 + 17 − 12 − 3 − 8 + 1 = 79. So, numbers which are not divisible by 2, 5 and 7 = 120 − 79 = 41.
ModerateCAT 2023 · Slot 1

Let n be the least positive integer such that 168 is a factor of 1134ⁿ. If m is the least positive integer such that 1134ⁿ is a factor of 168ᵐ, then m + n equals

  • (1) 24
  • (2) 12
  • (3) 9
  • (4) 15
Show solution
(4) 15. 168 = 2³ × 3¹ × 7¹ and 1134 = 2¹ × 3⁴ × 7¹. Since 168 is a factor of 1134ⁿ, the least value of n is 3. Now 1134ⁿ = 1134³ = 2³ × 3¹² × 7³ and 168ᵐ = (2³ × 3¹ × 7¹)ᵐ. Since 1134ⁿ is a factor of 168ᵐ, the least value of m is 12. Now m + n = 12 + 3 = 15.

CAT 2024 & 2025, recent

HardCAT 2025 · Slot 1 TITA

In a 3-digit number N, the digits are non-zero and distinct such that none of the digits is a perfect square, and only one of the digits is a prime number. Then, the number of factors of the minimum possible value of N is

Show solution
6. Allowed digits (non-zero, not perfect-square 1/4/9): 2, 3, 5, 6, 7, 8. Exactly one prime (2, 3, 5, 7) and two non-primes (6, 8) needed. Smallest N uses the smallest prime (2) with the two smallest non-primes (6, 8) → N = 268 = 2² × 67 → (2+1)(1+1) = 6 factors.
HardCAT 2025 · Slot 2

The number of divisors of (2⁶ × 3⁵ × 5³ × 7²), which are of the form (3r + 1), where r is a non-negative integer, is:

  • (A) 42
  • (B) 36
  • (C) 56
  • (D) 24
Show solution
(A) 42. A divisor ≡ 1 (mod 3) cannot contain any factor of 3, so the power of 3 is 0. We need 2ᵃ·5ᵇ·7ᶜ ≡ 1 (mod 3) with 0 ≤ a ≤ 6, 0 ≤ b ≤ 3, 0 ≤ c ≤ 2. Since 2 ≡ −1 and 5 ≡ −1 (mod 3), the product 2ᵃ·5ᵇ ≡ (−1)^(a+b), which is ≡ 1 when a+b is even; 7 ≡ 1 (mod 3) so 7ᶜ never affects it. Even (a+b): a even (4 choices: 0,2,4,6) with b even (2 choices: 0,2) = 8, plus a odd (3) with b odd (2) = 6, total 14. Times 3 choices for c = 14 × 3 = 42.