0
0

Remainder & Modular Arithmetic (Basic)

Introduction

Modular arithmetic helps us find remainders easily - even for very large numbers. Instead of dividing completely, we just focus on what remainder a number leaves when divided by another number. This idea appears in many aptitude problems like remainder, last-digit, and cyclicity questions.

Pattern: Remainder & Modular Arithmetic (Basic)

Pattern

The key concept: a ≡ b (mod m) means both a and b leave the same remainder when divided by m.

  • Definition: a ≡ b (mod m) ⇔ m divides (a - b).
  • Addition & Subtraction: (a ± b) mod m = [(a mod m) ± (b mod m)] mod m.
  • Multiplication: (a × b) mod m = [(a mod m) × (b mod m)] mod m.
  • Power rule: ak mod m → keep reducing after each multiplication step to avoid large numbers.
  • Cycles: For repeated powers, the pattern of remainders repeats after some time. Use this cycle to simplify large exponents.
  • Negative Remainders: If you get a negative remainder, add the divisor (m) until it becomes positive.

Step-by-Step Example

Question

Find the remainder when 7100 is divided by 13.

Solution

  1. Step 1: What we are finding:

    We need the remainder of 7100 ÷ 13, i.e., 7100 mod 13.

  2. Step 2: Look for a pattern in powers of 7 mod 13:

    7¹ ≡ 7 (mod 13) 7² = 49 → 49 ÷ 13 = 3 remainder 10 → 7² ≡ 10 (mod 13) 7³ = 7²×7 = 10×7 = 70 → 70 ÷ 13 = 5 remainder 5 → 7³ ≡ 5 (mod 13) 7⁴ = 5×7 = 35 → 35 ÷ 13 = 2 remainder 9 → 7⁴ ≡ 9 (mod 13)

  3. Step 3: Check for repeating cycle:

    If we continue, after 12 powers, 7¹² ≡ 1 (mod 13). So the powers of 7 repeat every 12 steps.

  4. Step 4: Simplify exponent using the cycle:

    100 ÷ 12 → remainder 4 → 7¹⁰⁰ ≡ 7⁴ (mod 13)

  5. Step 5: Use the earlier result:

    From Step 2, 7⁴ ≡ 9 (mod 13)

  6. Final Answer:

    Remainder = 9

  7. Quick Check:

    You can verify by smaller exponent reduction: 7¹² ≡ 1, so 7¹⁰⁰ = (7¹²)⁸ × 7⁴ ≡ 1⁸ × 7⁴ ≡ 9 mod 13 ✅

Quick Variations

1. Find remainders of large numbers using cycles (like 2100 mod 5).

2. Handle negative numbers (e.g., -3 mod 5 = 2).

3. Solve equations like a·x ≡ b (mod m) by trying small values or using modular inverses.

Trick to Always Use

  • Step 1: Reduce numbers modulo m as soon as possible.
  • Step 2: Look for repeating patterns in powers to simplify large exponents.
  • Step 3: For simple equations, test small values or find modular inverses when possible.
  • Step 4: Always convert negative remainders to positive by adding m.

Summary

Summary

  • Modular arithmetic helps solve remainder problems quickly by reducing numbers under the modulus.
  • Use rules for addition, subtraction, multiplication, and powers to simplify expressions modulo m.
  • Recognise that a ≡ b (mod m) means both leave the same remainder when divided by m.
  • Use cycles (repeating patterns) for large exponents and convert negative remainders to positive by adding m.

Example to remember:
7¹² ≡ 1 (mod 13), so 7¹⁰⁰ ≡ 7⁴ ≡ 9 (mod 13).

Practice

(1/5)
1. Find the remainder when 25 is divided by 7.
easy
A. 3
B. 4
C. 5
D. 6

Solution

  1. Step 1: Understand the division:

    We want the remainder r when 25 is written as 25 = 7×q + r with 0 ≤ r < 7.

  2. Step 2: Find the largest multiple of 7 less than 25:

    7 × 3 = 21, and 7 × 4 = 28 (too big). So use 7 × 3 = 21.

  3. Step 3: Subtract to get remainder:

    25 - 21 = 4 → remainder = 4.

  4. Final Answer:

    Remainder = 4 → Option B.

  5. Quick Check:

    25 = 7×3 + 4, and 0 ≤ 4 < 7, so remainder 4 is correct. ✅
Hint: Subtract the largest multiple of the divisor (7) that doesn't exceed the number.
Common Mistakes: Mixing up quotient and remainder or choosing a multiple that is too large.
2. Find the remainder when 48 is divided by 9.
easy
A. 3
B. 1
C. 5
D. 6

Solution

  1. Step 1: Quick division check:

    Find the nearest multiple of 9 below 48. 9 × 5 = 45 and 9 × 6 = 54 (too big).

  2. Step 2: Subtract to get remainder:

    48 - 45 = 3 → remainder = 3.

  3. Alternative (digit-sum):

    Sum of digits 4 + 8 = 12; 12 mod 9 = 3, which gives the same remainder.

  4. Final Answer:

    Remainder = 3 → Option A.

  5. Quick Check:

    48 = 9×5 + 3 and 0 ≤ 3 < 9, so remainder 3 is correct. ✅
Hint: Use nearest multiple or digit-sum trick for mod 9 problems.
Common Mistakes: Forgetting the remainder must be less than the divisor (9).
3. Find the remainder when 7² + 5² is divided by 6.
easy
A. 1
B. 3
C. 2
D. 0

Solution

  1. Step 1: Compute each square (or reduce first):

    7² = 49 and 5² = 25, so the sum = 49 + 25 = 74.

  2. Step 2: Find remainder on division by 6:

    6 × 12 = 72, 74 - 72 = 2 → remainder = 2.

  3. Modular shortcut (faster):

    7 ≡ 1 (mod 6) so 7² ≡ 1² = 1; 5 ≡ 5 (mod 6) and 5² ≡ 25 ≡ 1 (mod 6); sum ≡ 1+1 = 2 (mod 6).

  4. Final Answer:

    Remainder = 2 → Option C.

  5. Quick Check:

    74 = 6×12 + 2 and remainder 2 is less than 6, so correct. ✅
Hint: Reduce each term modulo m before adding: (a² + b²) mod m = [(a mod m)² + (b mod m)²] mod m.
Common Mistakes: Computing large numbers fully instead of reducing modulo early.
4. Find the remainder when 2³ × 3² is divided by 5.
medium
A. 2
B. 3
C. 4
D. 1

Solution

  1. Step 1: Compute powers separately and reduce as you go:

    2³ = 8 and 3² = 9. We can reduce these modulo 5 first: 8 mod 5 = 3, 9 mod 5 = 4.

  2. Step 2: Multiply reduced values and reduce again:

    3 × 4 = 12; 12 mod 5 = 2 → remainder = 2.

  3. Direct check:

    2³×3² = 8×9 = 72; 72 ÷ 5 leaves remainder 2 (since 5×14 = 70).

  4. Final Answer:

    Remainder = 2 → Option A.

  5. Quick Check:

    72 = 5×14 + 2, remainder 2 is correct. ✅
Hint: Reduce each factor modulo the divisor before multiplying to keep numbers small.
Common Mistakes: Multiplying large numbers first and risking arithmetic errors instead of reducing early.
5. Find the remainder when 7¹⁰ is divided by 12.
medium
A. 3
B. 7
C. 9
D. 1

Solution

  1. Step 1: Look for a small cycle in powers of 7 modulo 12:

    Compute a few powers: 7¹ ≡ 7 (mod 12). 7² = 49; 49 mod 12 = 1 (because 12×4=48).

  2. Step 2: Use the cycle:

    Since 7² ≡ 1 (mod 12), higher even powers repeat 1. So 7¹⁰ = (7²)⁵ ≡ 1⁵ ≡ 1 (mod 12).

  3. Final Answer:

    Remainder = 1 → Option D.

  4. Quick Check:

    The cycle shows 7² ≡ 1, so any 7^{even} ≡ 1; 10 is even → remainder 1. ✅
Hint: Find the smallest power where remainder becomes 1 or repeats, then reduce exponent modulo cycle length.
Common Mistakes: Trying to compute 7¹⁰ directly instead of using the repeating pattern of powers.

Mock Test

Ready for a challenge?

Take a 10-minute AI-powered test with 10 questions (Easy-Medium-Hard mix) and get instant SWOT analysis of your performance!

10 Questions
5 Minutes