◆ QA · Number System

Remainders , formulas + CAT PYQs

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

13CAT PYQs

Number Systemchapter

Formulas PYQs (13)↩ 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ⁱ

Practice questions generated · up to 100

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

Remainders, CAT PYQs

Remainders

ModerateCAT 1998

A is the set of positive integers such that when divided by 2, 3, 4, 5, 6 leaves the remainders 1, 2, 3, 4, 5 respectively. How many integers between 0 and 100 belong to set A?

(1) 0
(2) 1
(3) 2
(4) None of these

Show solution

(2) 1. Divisor − remainder = 1 in every case, so the number is of the form (LCM − 1). LCM(2,3,4,5,6) = 60, so numbers are 60n − 1: 59, 119, … Only 59 lies between 0 and 100. One number.

ModerateCAT 1999

The remainder when 7⁸⁴ is divided by 342 is:

(1) 0
(2) 1
(3) 49
(4) 341

Show solution

(2) 1. Note 342 = 343 − 1 = 7³ − 1. So 7⁸⁴ = (7³)²⁸ = 343²⁸ = (342 + 1)²⁸ ≡ 1²⁸ = 1 (mod 342). Remainder 1.

ModerateCAT 2000

Let N = 1421 × 1423 × 1425. What is the remainder when N is divided by 12?

(1) 0
(2) 9
(3) 3
(4) 6

Show solution

(3) 3. 1416 is a multiple of 12, so N = (1416+5)(1416+7)(1416+9). Remainder = (5 × 7 × 9) mod 12 = 315 mod 12 = 3.

HardCAT 2000

The integers 34041 and 32506, when divided by a three-digit integer n, leave the same remainder. What is the value of n?

(1) 289
(2) 367
(3) 453
(4) 307

Show solution

(4) 307. If both leave the same remainder, n divides their difference: 34041 − 32506 = 1535 = 5 × 307. The three-digit divisor is 307.

HardCAT 2002

On dividing a number by 3, 4 and 7, the remainders are 2, 1 and 4 respectively. If the same number is divided by 84 then the remainder is:

(1) 80
(2) 76
(3) 53
(4) None of these

Show solution

(3) 53. Build up: number ≡ 4 (mod 7) → 7x+4; ≡ 1 (mod 4) → 4(7x+4)+1; ≡ 2 (mod 3) → 3[4(7x+4)+1]+2 = 84x + 53. So mod 84 the remainder is 53.

EasyCAT 2004

What is the remainder when 4⁹⁶ is divided by 6?

(1) 0
(2) 2
(3) 3
(4) 4

Show solution

(4) 4. Any positive power of 4 leaves remainder 4 when divided by 6 (4¹=4, 4²=16≡4, …). So 4⁹⁶ ≡ 4 (mod 6).

ModerateCAT 2004

What is the sum of all two-digit numbers that give a remainder of 3 when they are divided by 7?

(1) 666
(2) 676
(3) 683
(4) 777

Show solution

(2) 676. Such numbers are 7k + 3: the two-digit ones run 10, 17, …, 94 (k = 1 to 13), 13 terms. Sum = 13/2 × (10 + 94) = 13 × 52 = 676.

ModerateCAT 2004

The remainder, when (15²³ + 23²³) is divided by 19, is

(1) 4
(2) 15
(3) 0
(4) 18

Show solution

(3) 0. 15²³ + 23²³ is aⁿ + bⁿ with odd n, so it is divisible by a + b = 38 = 2 × 19. Since 19 | 38, the remainder is 0.

ModerateCAT 2005

If x = (16³ + 17³ + 18³ + 19³), then x divided by 70 leaves a remainder of

(1) 0
(2) 1
(3) 69
(4) 35

Show solution

(1) 0. a³ + b³ + c³ + d³ is divisible by a + b + c + d when the terms pair appropriately; here 16 + 17 + 18 + 19 = 70. So x is divisible by 70, remainder 0.

ModerateCAT 2002

The remainder when 2²⁵⁶ is divided by 17 is:

(1) 7
(2) 13
(3) 11
(4) 1

Show solution

(4) 1. 2²⁵⁶ = (2⁴)⁶⁴ = 16⁶⁴ = (17 − 1)⁶⁴ ≡ (−1)⁶⁴ = 1 (mod 17). Remainder 1.

CAT 2024 & 2025, recent

ModerateCAT 2024 · Slot 1

When 10¹⁰⁰ is divided by 7, the remainder is

(A) 2
(B) 4
(C) 1
(D) 6

Show solution

(B) 4. 10 ≡ 3 (mod 7); powers of 3 cycle with period 6. 100 = 6·16 + 4, so 10¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7).

ModerateCAT 2024 · Slot 2

When 3³³³ is divided by 11, the remainder is

(A) 5
(B) 10
(C) 1
(D) 6

Show solution

(A) 5. Powers of 3 mod 11 cycle with period 5: 3, 9, 5, 4, 1. 333 ≡ 3 (mod 5), so 3³³³ ≡ 3³ = 27 ≡ 5 (mod 11).

ModerateCAT 2024 · Slot 3

If 10⁶⁸ is divided by 13, the remainder is

(A) 5
(B) 8
(C) 9
(D) 4

Show solution