Skip to content
Login
Quantitative Aptitude

Divisibility & Remainders

Surface Area & Volume3 / 51Simplification & Surds
Read
Practice

Concepts (2)

Remainder Theorem finds the leftover after division. Cyclicity predicts patterns of remainders/unit digits for powers. Master modular arithmetic and negative remainders for speed.

Core Formula

1. Euclid's Division Lemma: Dividend = Divisor × Quotient + Remainder Where 0 ≤ Remainder < Divisor.

2. Modular Arithmetic: a ≡ b (mod m) means a and b have the same remainder when divided by m. This is read as 'a is congruent to b modulo m'.

3. Properties of Remainders:

  • Addition: (A + B) % M = ( (A % M) + (B % M) ) % M
  • Multiplication: (A × B) % M = ( (A % M) × (B % M) ) % M
  • Powers: (A^N) % M = ( (A % M)^N ) % M

4. Negative Remainder Concept: Sometimes, it's faster to use a negative remainder. If R is the positive remainder of N % M, then R - M is a negative remainder. For example, 2 % 7 is 2, but it can also be thought of as -5 (since 2-7 = -5). The final answer must always be positive.

5. Cyclicity: When a number is raised to successive powers, the unit digit (or the remainder when divided by a specific number) often follows a repeating pattern or cycle. Identifying this cycle length helps reduce large exponents.

Worked Example 1

Q: What is the remainder when 17 × 23 is divided by 7?

Step-by-step Solution:

  1. Find the remainder of each number when divided by 7:
    • 17 % 7 = 3
    • 23 % 7 = 2
  2. Multiply these remainders:
    • 3 × 2 = 6
  3. Find the remainder of this product when divided by 7:
    • 6 % 7 = 6
    • Answer: The remainder is 6.

Worked Example 2

Q: The remainder when 2^100 is divided by 3 is:

Step-by-step Solution (using Negative Remainder):

  1. Find the remainder of the base (2) when divided by 3:
    • 2 % 3 = -1 (using negative remainder for speed)
  2. Apply this remainder to the power:
    • (-1)^100 % 3
  3. Calculate the result:
    • 1 % 3 = 1
    • Answer: The remainder is 1.

Alternative Solution (using Cyclicity):

  1. Find the pattern of remainders for powers of 2 when divided by 3:
    • 2^1 % 3 = 2
    • 2^2 % 3 = 4 % 3 = 1
    • 2^3 % 3 = 8 % 3 = 2
    • The cycle of remainders is (2, 1) with a length of 2.
  2. Divide the exponent (100) by the cycle length (2):
    • 100 ÷ 2 = 50 with a remainder of 0.
  3. A remainder of 0 means it's the last element in the cycle (or the element corresponding to the cycle length). In this case, it's the same as 2^2 % 3.
    • 2^2 % 3 = 1
    • Answer: The remainder is 1.

Shortcuts & Tricks

  1. Negative Remainders: Crucial for speed. If A % M = R, then A % M can also be R - M. Use the remainder (positive or negative) that is numerically smaller or simplifies calculations (e.g., 2 % 3 = -1 is better than 2).
  2. Cyclicity for Powers: For a^N % M, find the cycle length of a^k % M. Then, reduce N modulo the cycle length. If N % cycle_length = r, the answer is a^r % M. If r=0, use a^(cycle_length) % M.
  3. Fermat's Little Theorem (for prime divisors): If p is a prime number and a is not a multiple of p, then a^(p-1) ≡ 1 (mod p). This means you can reduce the exponent N modulo (p-1) when M is a prime. E.g., 2^100 % 3: p=3, p-1=2. 100 % 2 = 0. So 2^100 % 3 = 2^2 % 3 = 1.

Common Mistakes

  1. Incorrectly Applying Remainder Properties: Students sometimes forget to take the modulo at each step when dealing with large intermediate products or sums, leading to numbers that are too large to handle.
  2. Miscalculating Cycle Length: Errors in finding the repeating pattern or the length of the cycle for powers can lead to incorrect exponent reduction.
  3. Forgetting Final Positive Remainder: While negative remainders are great for intermediate steps, the final answer must always be a positive remainder (between 0 and Divisor-1). If you get a negative result, add the divisor to it.

Derivation (brief)

Modular arithmetic properties stem directly from the definition a = qm + r. For addition: Let A = q1*M + r1 and B = q2*M + r2. Then A+B = (q1+q2)M + (r1+r2). So, (A+B) % M = (r1+r2) % M = ((A%M) + (B%M)) % M. For multiplication: A*B = (q1*M + r1)(q2*M + r2) = q1q2M^2 + q1Mr2 + q2Mr1 + r1r2 = M(q1q2M + q1r2 + q2r1) + r1r2. So, (A*B) % M = (r1r2) % M = ((A%M) * (B%M)) % M.

Advanced Examples

Q: The remainder when (7^1 + 7^2 + 7^3 + ... + 7^100) is divided by 6 is:

Step-by-step Solution:

  1. Find the remainder of the base (7) when divided by 6:
    • 7 % 6 = 1
  2. Apply this remainder to each term in the sum:
    • Since 7 ≡ 1 (mod 6), then 7^k ≡ 1^k (mod 6) for any power k.
    • So, 7^1 % 6 = 1, 7^2 % 6 = 1, 7^3 % 6 = 1, and so on, up to 7^100 % 6 = 1.
  3. The sum of remainders becomes:
    • (1 + 1 + 1 + ... + 1) (100 times)
  4. Find the remainder of this sum when divided by 6:
    • 100 % 6
    • 100 = 16 × 6 + 4
    • 100 % 6 = 4
    • Answer: The remainder is 4.

Variation Types

  1. Remainder with Factorials: For N! % M, if M ≤ N, then N! % M = 0. If M > N, calculate directly. For sums like (1! + 2! + ... + 100!) % 12, calculate terms until k! % 12 = 0 (e.g., 4! = 24, so 24 % 12 = 0). All subsequent factorials will also be 0 modulo 12. Sum only the non-zero terms.
  2. Large Numbers & Unit Digits: Finding the unit digit is equivalent to finding the remainder when divided by 10. Use cyclicity of unit digits (e.g., 2^1=2, 2^2=4, 2^3=8, 2^4=16(6), 2^5=32(2). Cycle length 4 for powers of 2).
  3. Euler's Totient Theorem: A generalization of Fermat's Little Theorem. If gcd(a, m) = 1, then a^φ(m) ≡ 1 (mod m), where φ(m) is Euler's totient function (counts positive integers up to m that are relatively prime to m). For m = p1^k1 * p2^k2 * ..., φ(m) = m * (1 - 1/p1) * (1 - 1/p2) * .... This is powerful for a^N % M where M is composite.

Time-Saving Methods

  1. Reduce Base First: Always reduce the base A modulo M before doing any power calculations: (A^N) % M = ((A % M)^N) % M. This prevents dealing with huge numbers.
  2. Look for ±1 Remainders: If A % M results in 1 or -1 (or M-1), the calculation for powers becomes trivial. E.g., (M-1)^N % M is 1 if N is even, and M-1 (or -1) if N is odd.
  3. Apply Euler's/Fermat's Theorem: For a^N % M, if gcd(a, M)=1:
    • If M is prime, use N % (M-1) as the new exponent.
    • If M is composite, use N % φ(M) as the new exponent. Remember to add φ(M) to the exponent if the reduced exponent is 0 to avoid a^0 unless N is a multiple of φ(M) and N>0 (then a^φ(M) is the correct term). This is a bit advanced for basic SSC CGL but highly effective.
☆☆☆☆☆Depth 0/5
Start Lesson

These are shortcuts to see if a number is divisible by another without full division. For 2, check if the last digit is even. For 3, add all digits; if the sum is divisible by 3, the number is too.

These are shortcuts to see if a number is divisible by another without full division. For 2, check if the last digit is even. For 3, add all digits; if the sum is divisible by 3, the number is too. For 4, check if the last two digits are divisible by 4. For 9, the sum of digits must be divisible by 9. Example: For 126, 1+2+6 = 9. Since 9 is divisible by 3 and 9, 126 is divisible by both.

☆☆☆☆☆Depth 0/5
Start Lesson

Ready to practice? Start an interactive lesson.

Start Lesson: Remainder Theorem & Cyclicity