◆ QA · Number System

HCF & LCM , formulas + CAT PYQs

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

8CAT PYQs
Number Systemchapter
Formulas PYQs (8)↩ 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ⁱ
8 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.

HCF & LCM, CAT PYQs

HCF & LCM

EasyCAT 1999

4. For two positive integers a and b define the function h(a, b) as the greatest common factor (GCF) of a, b. Let A be a set of n positive integers. G(A), the GCF of the elements of set A is computed by repeatedly using the function h. The minimum number of times h is required to be used to compute G is:

  • (1) ½ n
  • (2) (n − 1)
  • (3) n
  • (4) None of these
Show solution
(2) (n − 1). Each application of h combines two values into one. To reduce n values to a single GCF, you need one fewer operation than values: n − 1.
HardCAT 2001

2. A farmer has decided to build a wire fence along one straight side of his property. For this, he planned to place several fence-posts at 6 m intervals, with posts fixed at both ends of the side. After he bought the posts and wire, he found that the number of posts he had bought was 5 less than required. However, he discovered that the number of posts he had bought would be just sufficient if he spaced them 8 m apart. What is the length of the side of his property and how many posts did he buy?

  • (1) 100 m, 15
  • (2) 100 m, 16
  • (3) 120 m, 15
  • (4) 120 m, 16
Show solution
(4) 120 m, 16. The length must be a common multiple of 6 and 8. With length 120 m: posts at 8 m spacing = 120/8 + 1 = 16; at 6 m spacing = 120/6 + 1 = 21, which is 5 more. So length 120 m, 16 posts bought.
ModerateCAT 2001

6. A red light flashes 3 times per minute and a green light flashes 5 times in two minutes at regular intervals. If both lights start flashing at the same time, how many times do they flash together in each hour?

  • (1) 30
  • (2) 24
  • (3) 20
  • (4) 60
Show solution
(1) 30. Red interval = 60/3 = 20 s; green interval = 120/5 = 24 s. They coincide every LCM(20, 24) = 120 s. In 3600 s there are 3600/120 = 30 coincidences.
HardCAT 2002

8. There are three pieces of cake weighing 9/2 lbs, 27/4 lbs and 35/5 lbs. Pieces of the cake are equally divided and distributed in such a manner that every guest in the party gets one single piece of cake. Further the weight of the pieces of the cake is as heavy as possible. What is the largest number of guest to whom we can distribute the cake?

  • (1) 54
  • (2) 20
  • (3) 72
  • (4) None of these
Show solution
(4) None of these (= 41). The heaviest equal piece = HCF of the fractions = HCF(numerators)/LCM(denominators). (Note: the book's worked solution treats the third weight as 36/5.) LCM of denominators 2, 4, 5 = 20; HCF of numerators 9, 27, 36 = 9, so heaviest part = 9/20. Then (9/2) = (90/20) = 10 × (9/20), (27/4) = (135/20) = 15 × (9/20), (36/5) = (144/20) = 16 × (9/20). Maximum guests = 10 + 15 + 16 = 41.
HardCAT 2002

9. In a book store, each of the word of the glowsign board "MODERN BOOK STORES" is visible after 5/2, 17/4 and 41/8 seconds respectively. Each of them is put off for 1 second. Find the time after which one person can see a completely visible glowsign board.

  • (1) 73.5 seconds
  • (2) 79.4 seconds
  • (3) 68.2 seconds
  • (4) None of these
Show solution
(1) 73.5 seconds. Effective cycle of each word (visible time + 1 s off): MODERN = 5/2 + 1 = 7/2, BOOK = 17/4 + 1 = 21/4, STORES = 41/8 + 1 = 49/8. All flash together at LCM(7/2, 21/4, 49/8) = LCM(7,21,49)/HCF(2,4,8) = 147/2 = 73.5 s.
HardCAT 2022 · Slot 1TITA

12. Let A be the largest positive integer that divides all the numbers of the form 3ᵏ + 4ᵏ + 5ᵏ, and B be the largest positive integer that divides all the numbers of the form 4ᵏ + 3(4ᵏ) + 4ᵏ⁺², where k is any positive integer. Then (A + B) equals:

Show solution
82. For A: k = 1 → 12, k = 2 → 50, k = 3 → 216; HCF(12, 50, 216) = 2, so A = 2. For B: 4ᵏ + 3·4ᵏ + 4ᵏ·16 = 4ᵏ(1 + 3 + 16) = 4ᵏ·20; the largest common divisor over all k is 4 × 20 = 80, so B = 80. A + B = 82.
HardCAT 2022 · Slot 3TITA

14. A school has less than 5000 students and if the students are divided equally into teams of either 9 or 10 or 12 or 25 each, exactly 4 are always left out. However, if they are divided into teams of 11 each, no one is left out. The maximum number of teams of 12 each that can be formed out of the students in the school is:

Show solution
150. LCM(9, 10, 12, 25) = 900, so students = 900k + 4. With 900k + 4 < 5000, k = 1…5. Also it must be divisible by 11; only k = 2 works → 1804 students. Teams of 12 = ⌊1800/12⌋ = 150.
HardCAT 2023 · Slot 2

15. For any natural numbers m, n and k, such that k divides both m + 2n and 3m + 4n, k must be a common divisor of:

  • (1) m and n
  • (2) m and 2n
  • (3) 2m and 3n
  • (4) 2m and n
Show solution
(2) m and 2n. Let m + 2n = λ₁k ...(1) and 3m + 4n = λ₂k ...(2), where λ₁ & λ₂ are natural numbers. Solving (1) & (2): m = (2λ₂ − λ₁)k and 2n = (3λ₁ − λ₂)k. So m and 2n are common divisors, i.e. k divides both m and 2n.