Remainders and Divisibility

The remainder theorem is to number theory what the percentage formula is to arithmetic — a single compact rule that unlocks an entire category of SSC CGL questions about large powers and complex divisions.

Definition: When a number N is divided by a divisor d, the remainder r satisfies: N = d × q + r, where q is the quotient and 0 ≤ r < d.

---

Basic Remainder Concepts

Notation: N mod d, or N % d, or "remainder when N ÷ d."

Key observations:

• The remainder is always non-negative and strictly less than d
• If N is perfectly divisible by d, the remainder is 0
• The remainder of N ÷ 1 is always 0 (every integer is divisible by 1)

Real-world example: If 100 students are to sit in rows of 9: 100 = 9 × 11 + 1. The remainder 1 means one student is left over after filling 11 complete rows. This models N = 100, d = 9, q = 11, r = 1.

---

Modular Arithmetic: The Core Rules

These rules allow you to break a huge computation into smaller, manageable ones.

Rule 1 — Addition mod d:
(a + b) mod d = [(a mod d) + (b mod d)] mod d

Example: (47 + 38) mod 5
= [(47 mod 5) + (38 mod 5)] mod 5
= [2 + 3] mod 5
= 5 mod 5 = 0

Verify: 47 + 38 = 85; 85 ÷ 5 = 17 remainder 0 ✓

Rule 2 — Multiplication mod d:
(a × b) mod d = [(a mod d) × (b mod d)] mod d

Example: (23 × 17) mod 4
= [(23 mod 4) × (17 mod 4)] mod 4
= [3 × 1] mod 4
= 3 mod 4 = 3

Verify: 23 × 17 = 391; 391 = 97 × 4 + 3, remainder 3 ✓

Rule 3 — Powers mod d (derived from Rule 2):
aⁿ mod d = (a mod d)ⁿ mod d

This is the key to all large-power remainder questions.

---

Why These Rules Work (Intuition)

Think of numbers on a clock-face. A 12-hour clock uses mod 12. If it is 10 o'clock now, and 5 hours pass, the clock shows (10 + 5) mod 12 = 3 — not 15. The "modulus" wraps numbers around just like a circular track.

Real-world example: Weekday calculation. If today is Thursday (day 4, counting Mon=1), what day is it 100 days from now? (4 + 100) mod 7 = 104 mod 7 = 104 − 14×7 = 104 − 98 = 6 → Saturday.

---

Euler's Totient Theorem

Definition: Euler's Totient function φ(n) counts the number of integers from 1 to n that are co-prime to n.

Euler's Theorem: If gcd(a, n) = 1 (a and n are co-prime), then:
a^φ(n) ≡ 1 (mod n)

This means a^φ(n) leaves remainder 1 when divided by n.

Computing φ(n):

• If n = p (prime): φ(p) = p − 1
• If n = p^k: φ(p^k) = p^k − p^(k-1) = p^(k-1)(p−1)
• If n = p × q (distinct primes): φ(pq) = (p−1)(q−1)

Example: Find remainder when 3^100 is divided by 7.

• gcd(3, 7) = 1 ✓
• φ(7) = 7 − 1 = 6
• 3^6 ≡ 1 (mod 7)
• 100 = 6 × 16 + 4
• 3^100 = (3^6)^16 × 3^4 ≡ 1^16 × 81 ≡ 81 mod 7
• 81 = 11 × 7 + 4 → remainder 4

---

Fermat's Little Theorem

Definition: For a prime p and any integer a where p does not divide a:
a^(p−1) ≡ 1 (mod p)

This is actually a special case of Euler's Theorem (since φ(p) = p−1 for prime p).

Example: Find remainder when 2^10 is divided by 11.

• 11 is prime; gcd(2, 11) = 1
• By Fermat: 2^(11−1) = 2^10 ≡ 1 (mod 11)
• Remainder = 1

Why it matters for SSC: When the divisor is prime, Fermat's theorem gives the cycle length instantly without computing powers manually.

---

Finding Remainders of Large Powers: Step-by-Step Method

For questions like "Find remainder when 7^50 ÷ 5":

Method 1 — Euler/Fermat:

• gcd(7, 5) = 1; φ(5) = 4 (since 5 is prime)
• 7^4 ≡ 1 (mod 5)
• 50 = 4 × 12 + 2
• 7^50 = (7^4)^12 × 7^2 ≡ 1^12 × 49 ≡ 49 mod 5
• 49 = 9 × 5 + 4 → remainder 4

Method 2 — Cyclicity (see next lesson): Build the pattern of remainders manually for 7^1, 7^2, 7^3, 7^4 and find when it repeats.

Both methods must give the same answer.

---

Special Remainder Shortcuts

Shortcut 1: (N + d) has the same remainder as N when divided by d.
Example: Remainder of 17 ÷ 5 = remainder of (17 − 15) = 2 ÷ 5 = 2.

Shortcut 2: If N ≡ r₁ (mod d) and M ≡ r₂ (mod d), then:

• N + M ≡ r₁ + r₂ (mod d)
• N × M ≡ r₁ × r₂ (mod d)

Shortcut 3: Negative remainders. Sometimes it is easier to use negative equivalents.

• 17 mod 9: direct → 17 − 9 = 8 → remainder 8
• Alternative: 17 ≡ 17 − 18 = −1 (mod 9). Negative remainder −1 means actual remainder = 9 − 1 = 8 ✓
• Negative remainders are powerful for bases just below the modulus.

---

Worked Example

Question: Find the remainder when 2^100 is divided by 3.

Solution:

Step 1: Note gcd(2, 3) = 1. φ(3) = 2.

Step 2: By Euler: 2^2 ≡ 1 (mod 3). So the cycle length is 2.

Step 3: 100 = 2 × 50, with no remainder. So 2^100 = (2^2)^50 ≡ 1^50 = 1 (mod 3).

Conclusion: Remainder = 1.

Quick verification: 2^1 mod 3 = 2; 2^2 mod 3 = 1; 2^3 mod 3 = 2; 2^4 mod 3 = 1 → cycle is (2, 1). 100 is even → remainder 1 ✓

---

When you need the remainder of 7^100 divided by 5, computing 7^100 directly is impossible by hand — but the cyclicity method turns it into a 4-step problem that takes 20 seconds.

---

What is Cyclicity?

Definition: Cyclicity (in the context of remainders) is the property that the remainders of successive powers of a number repeat in a fixed cycle when divided by a given divisor.

This happens because there are only a finite number of possible remainders (0 through d−1) when dividing by d. Once a remainder repeats, the entire cycle repeats from that point.

---

The Cyclicity Method: Step by Step

Step 1: Compute successive powers of the base, taking the remainder at each step.

Step 2: Identify when the remainder first repeats (typically when it returns to the remainder of base^1).

Step 3: Note the cycle length (period of repetition).

Step 4: Divide the exponent by the cycle length. The remainder of this division tells you which position in the cycle the answer falls on.

---

Detailed Worked Example: 7^50 ÷ 5

Step 1 — Compute remainders of 7^n (mod 5):

• 7^1 = 7 → 7 mod 5 = 2
• 7^2 = 49 → 49 mod 5 = 4 (or use 2² mod 5 = 4)
• 7^3 = 343 → 343 mod 5 = 3 (or 4 × 2 mod 5 = 8 mod 5 = 3)
• 7^4 = 2401 → 2401 mod 5 = 1 (or 3 × 2 mod 5 = 6 mod 5 = 1)
• 7^5 → 1 × 2 mod 5 = 2 — cycle restarts!

Cycle: 2, 4, 3, 1 — length 4

Step 2 — Find position of 7^50 in cycle:
50 mod 4 = 2 (since 50 = 4 × 12 + 2)

Step 3 — The answer is the 2nd value in the cycle: 4

Conclusion: Remainder of 7^50 ÷ 5 = 4

Quick shortcut check: 7 ≡ 2 (mod 5), so 7^50 ≡ 2^50 (mod 5). 50 mod 4 = 2 → 2^2 = 4. ✓

---

Why the Cycle Starts Again

The reason cycles are guaranteed: once a remainder r₀ appears twice, the next remainders are determined only by r₀ (via the multiplication rule), so the sequence must repeat exactly.

The cycle length divides φ(d) (Euler's totient). This is why Euler's Theorem guarantees a cycle of length at most φ(d).

---

Common Cycle Lengths

Real-world application: The last-digit cycle is cyclicity mod 10. Finding the last digit of 3^47: cycle is (3,9,7,1), period 4. 47 mod 4 = 3. Third element in cycle = 7. The last digit of 3^47 is 7.

---

Wilson's Theorem

Statement: For any prime number p:
(p − 1)! ≡ −1 (mod p)

Equivalently: (p−1)! leaves remainder (p−1) when divided by p.

Example: p = 7. Wilson says 6! ≡ −1 ≡ 6 (mod 7).
Verify: 6! = 720. 720 ÷ 7 = 102 remainder 6. ✓

SSC Application:
Find remainder when 6! is divided by 7.
Answer by Wilson: 720 mod 7 = 6 (i.e., 7−1).

Find remainder when 10! is divided by 11.
11 is prime; Wilson gives 10! ≡ −1 ≡ 10 (mod 11). Remainder = 10.

Converse: If (n−1)! ≡ −1 (mod n), then n is prime. This can be used to verify primality but is impractical for large n by hand.

---

Chinese Remainder Theorem (CRT) — Concept

Definition: The Chinese Remainder Theorem states that if you know the remainders of a number N when divided by several pairwise co-prime moduli, you can uniquely determine N (modulo the product of those moduli).

Practical SSC Form:

"A number N leaves remainder 3 when divided by 5, and remainder 2 when divided by 7. Find the smallest such N."

Method:

• N ≡ 3 (mod 5): N can be 3, 8, 13, 18, 23, 28, 33, 38…
• N ≡ 2 (mod 7): N can be 2, 9, 16, 23, 30, 37… wait, let's list mod 7 residue 2: 2, 9, 16, 23, 30, 37…
• Check N = 23: 23 mod 5 = 3 ✓; 23 mod 7 = 2 ✓. N = 23.

The general solution: N = 23 + k × LCM(5,7) = 23 + 35k. Smallest positive N = 23.

---

Worked Example: Full Cyclicity Problem

Question: Find the remainder when 13^51 is divided by 7.

Solution:

Step 1: Reduce base first. 13 mod 7 = 6 (since 13 = 7×1 + 6). So 13^51 ≡ 6^51 (mod 7).

Step 2: Note 6 ≡ −1 (mod 7). So 6^51 ≡ (−1)^51 = −1 ≡ 6 (mod 7).

Conclusion: Remainder = 6.

(This shows the power of recognising a base that is "−1" relative to the modulus.)

---

Worked Example: Wilson's Theorem Application

Question: Find the remainder when 14! is divided by 17.

Solution:

Step 1: 17 is prime; Wilson says 16! ≡ −1 ≡ 16 (mod 17).

Step 2: 16! = 16 × 15 × 14!. So 16 × 15 × (14!) ≡ 16 (mod 17).

Step 3: 16 ≡ −1 (mod 17) and 15 ≡ −2 (mod 17).
(−1)(−2)(14!) ≡ 16 ≡ −1 (mod 17)
2 × 14! ≡ −1 (mod 17)
14! ≡ −1 × (2^−1 mod 17) (mod 17)

Step 4: Find 2^−1 mod 17: 2 × 9 = 18 ≡ 1 (mod 17), so 2^−1 = 9.
14! ≡ −9 ≡ 17 − 9 = 8 (mod 17).

Conclusion: Remainder = 8.

---

The binomial identity (a + 1)^n = multiple of a + 1 is one of the most elegant shortcuts in number theory — once you see it, an entire class of large-power remainder questions collapses into a single step.

---

The Core Principle: Binomial Expansion Shortcut

Why it works: By the Binomial Theorem, (kd + r)^n expands as:
(kd)^n + n(kd)^(n−1)·r + … + n·(kd)·r^(n−1) + r^n

Every term except the last contains kd as a factor, so every term except the last is divisible by d. This means:
(kd + r)^n ≡ r^n (mod d)

Special case r = 1:
(kd + 1)^n ≡ 1^n = 1 (mod d) — always remainder 1, regardless of n.

Special case r = −1 (i.e., kd − 1):
(kd − 1)^n ≡ (−1)^n (mod d)

• If n is even: remainder = 1
• If n is odd: remainder = d − 1

---

The Primary Worked Example: 17^35 ÷ 16

Question: Find the remainder when 17^35 is divided by 16.

Solution:

Step 1: Notice that 17 = 16 + 1. So here d = 16, k = 1, r = 1, n = 35.

Step 2: By the binomial rule: (16 + 1)^35 ≡ 1^35 = 1 (mod 16).

Conclusion: Remainder = 1.

Intuitive check: 17 ≡ 1 (mod 16). So 17^35 ≡ 1^35 = 1 (mod 16). ✓

This takes under 10 seconds once you spot the pattern.

---

The Companion Rule: (kd − 1)^n

Rule: (kd − 1)^n mod d:

• n even → remainder = 1
• n odd → remainder = d − 1

Derivation: kd − 1 ≡ −1 (mod d). So (kd−1)^n ≡ (−1)^n (mod d). When n is even, (−1)^n = 1 → remainder 1. When n is odd, (−1)^n = −1 ≡ d−1 (mod d) → remainder d−1.

---

Extended Examples

Example A: Find the remainder when 19^41 is divided by 18.

• 19 = 18 + 1, so 19 ≡ 1 (mod 18)
• 19^41 ≡ 1^41 = 1 (mod 18)
• Remainder = 1

Example B: Find the remainder when 35^99 is divided by 36.

• 35 = 36 − 1, so 35 ≡ −1 (mod 36)
• 99 is odd → (−1)^99 = −1 ≡ 35 (mod 36)
• Remainder = 35

Example C: Find the remainder when 35^100 is divided by 36.

• 35 ≡ −1 (mod 36); 100 is even → (−1)^100 = 1
• Remainder = 1

Example D: Find the remainder when 31^26 is divided by 32.

• 31 = 32 − 1 ≡ −1 (mod 32); 26 is even
• Remainder = 1

---

More General Binomial Reduction

When r ≠ 1 or −1, the binomial rule still reduces the problem:

Example E: Find the remainder when 23^3 is divided by 10.

• 23 = 20 + 3. So 23^3 ≡ 3^3 = 27 ≡ 7 (mod 10).
• Remainder = 7

Example F: Find the remainder when 52^10 is divided by 7.

• 52 = 49 + 3 = 7×7 + 3. So 52 ≡ 3 (mod 7).
• 52^10 ≡ 3^10 (mod 7).
• By Fermat: 3^6 ≡ 1 (mod 7) (since 7 is prime).
• 3^10 = 3^6 × 3^4 ≡ 1 × 81 mod 7 = 81 mod 7 = 4 (81 = 11×7 + 4).
• Remainder = 4

---

Combining Techniques: A Harder Example

Question: Find the remainder when 2^200 is divided by 15.

Solution:

Step 1: Note gcd(2, 15) = 1. φ(15) = φ(3)×φ(5) = 2×4 = 8.
By Euler: 2^8 ≡ 1 (mod 15).

Step 2: 200 = 8 × 25. So 2^200 = (2^8)^25 ≡ 1^25 = 1 (mod 15).

Conclusion: Remainder = 1.

Quick verify: 2^4 = 16 ≡ 1 (mod 15). So cycle length is actually 4 (not 8 — Euler gives maximum, actual can be shorter). 200 = 4 × 50 → 2^200 ≡ 1^50 = 1 (mod 15). ✓

---

Summary of Pattern-Based Shortcuts

---

Worked Practice Set

Question 1: Remainder when 101^99 ÷ 100.

• 101 = 100 + 1 → remainder = 1

Question 2: Remainder when 99^99 ÷ 100.

• 99 = 100 − 1; 99 is odd → remainder = 99

Question 3: Remainder when 99^100 ÷ 100.

• 99 = 100 − 1; 100 is even → remainder = 1

Question 4: Remainder when 37^2 ÷ 13.

• 37 = 3×13 − 2 → 37 ≡ −2 (mod 13)
• 37^2 ≡ (−2)^2 = 4 → remainder = 4

---

Quick-revision notes for Remainders and Divisibility — the must-know points for SSC CGL Tier-I/II.

• The remainder theorem: dividend = divisor × quotient + remainder (0 ≤ remainder < divisor).
• For large-power remainders, use cyclicity of last digits or modular arithmetic.
• Remainder of a product = product of individual remainders (mod the divisor), then reduced.
• Fermat/Euler ideas: for prime p, a^(p−1) ≡ 1 (mod p) when gcd(a,p)=1 — speeds up big-power remainders.
• Negative-remainder shortcut: if a ≡ −1 (mod n), then aᵏ ≡ (−1)ᵏ.
• Successive division problems chain each remainder into the next division.

Cover the answer, recall, then check. 7 cards on the must-know Remainders and Divisibility facts for SSC CGL.

Q1. State the division algorithm (remainder theorem).
A1. Dividend = (Divisor × Quotient) + Remainder, with 0 ≤ Remainder < Divisor.

Q2. Remainder when 17 × 23 is divided by 5?
A2. 1 — 17≡2, 23≡3 (mod 5); 2×3 = 6 ≡ 1.

Q3. What is the remainder of 2¹⁰ divided by 3?
A3. 1 — 2 ≡ −1 (mod 3), so 2¹⁰ ≡ (−1)¹⁰ = 1.

Q4. How do you find the remainder of a product?
A4. Take the product of the individual remainders modulo the divisor, then reduce.

Q5. If a number leaves remainder 3 on division by 7, what is the smallest such positive number?
A5. 3 (or 10, 17, …).

Q6. Remainder of 100 divided by 9?
A6. 1 — digit sum 1+0+0 = 1.

Q7. Fermat's little theorem states what for a prime p?
A7. a^(p−1) ≡ 1 (mod p) when a is not divisible by p.