Remainder Theorem — SSC CGL Study Notes

\( N = d \times q + r \)  (Dividend = Divisor × Quotient + Remainder), and the remainder is always smaller than the divisor.

Shorthand used everywhere below: "\( N \bmod d \)" means "the remainder when \( N \) is divided by \( d \)", and \( a \equiv b \) (mod \( d \)) means \( a \) and \( b \) leave the same remainder by \( d \).

\( (A + B) \bmod d = (r_A + r_B) \bmod d \),   \( (A - B) \bmod d = (r_A - r_B) \bmod d \),   \( (A \times B) \bmod d = (r_A \times r_B) \bmod d \).

Any term that is a multiple of \( d \) contributes 0. A remainder may be taken negative for speed: 49 by 50 is \( -1 \), 47 by 50 is \( -3 \). Turn a negative answer positive by adding \( d \).

\( (d + 1)^{n} \bmod d = 1 \) for every \( n \).

\( (d - 1)^{n} \bmod d = 1 \) if \( n \) is even, and \( d - 1 \) (that is, \( -1 \)) if \( n \) is odd.

Reason: \( (d \pm 1)^{n} \) expands to a multiple of \( d \) plus \( (\pm 1)^{n} \).

Reduce the base first: \( a^{n} \bmod d = (a \bmod d)^{n} \bmod d \). Then compute \( a, a^{2}, a^{3}, \ldots \) by \( d \) until you hit remainder 1 (or \( -1 \)). If \( a^{k} \equiv 1 \), the remainders repeat with cycle length \( k \), so reduce the exponent: \( a^{n} \equiv a^{(n \bmod k)} \). If you find \( a^{k} \equiv -1 \) instead, then \( a^{2k} \equiv 1 \) — reduce by \( 2k \) and remember a leftover \( a^{k} \) is \( -1 \).

Find the remainder of each term, then count. If every term leaves \( r \), the sum leaves (number of terms × \( r \)) mod \( d \). If the base is \( d - 1 \), odd powers leave \( -1 \) and even powers \( +1 \), so consecutive terms cancel in pairs. If the remainders run in a cycle, add one full cycle and count the cycles.

If \( n \bmod d = r \), then replace \( n \) by \( r \) in any expression: \( (kn + c) \bmod d = (kr + c) \bmod d \), \( n^{2} \bmod d = r^{2} \bmod d \), \( (n^{2} + 5n + 8) \bmod d = (r^{2} + 5r + 8) \bmod d \).

If \( f \) is a factor of \( d \), then \( N \bmod f = r \bmod f \) — only the old remainder needs dividing. Going the other way (to a multiple of \( d \)) leaves several possibilities: remainder 5 by 8 means 5, 13 or 21 by 24.

If \( N \) leaves \( r \) and \( kN \) leaves \( r' \) by the same \( d \), then \( d \) divides \( k \times r - r' \). Similarly, if two numbers leave \( r_1, r_2 \) and their sum leaves \( s \), then \( d \) divides \( r_1 + r_2 - s \). In every case, \( d \) is bigger than every remainder that appears — that bound is what picks the answer from the divisors.

In successive division each quotient becomes the next dividend. To recover the number, work backwards: \( N = d_1\,(d_2\,(d_3 q + r_3) + r_2) + r_1 \). For the least such number take the final quotient \( q = 0 \).

Key link: successive remainders \( r_1, r_2 \) by \( d_1, d_2 \) mean \( N \bmod (d_1 d_2) = r_1 + d_1 r_2 \).

If \( N \) leaves \( r_1 \) by \( a \) and \( r_2 \) by \( b \) with \( a, b \) co-prime, the solutions repeat every \( a \times b \): find the first solution by listing one family and testing the other condition, then add multiples of \( ab \). From the family you get the least three-digit member, the largest three-digit member, a count in a range, or the remainder by a third divisor.

\( a^{n} - b^{n} \) is always divisible by \( a - b \).   \( a^{n} + b^{n} \) is divisible by \( a + b \) when \( n \) is odd.   \( a^{n} - b^{n} \) is divisible by \( a + b \) as well when \( n \) is even.   \( a^{k} - 1 \) divides \( a^{n} - 1 \) when \( k \) divides \( n \).

Products of consecutive numbers: \( k \) consecutive numbers are divisible by \( k! \). For odd \( n \): \( n^{2} - 1 \) is a multiple of 8, \( n^{3} - n \) of 24. For every \( n \): \( n^{3} - n \) is a multiple of 6 and \( n^{5} - n \) of 30.

When a polynomial \( f(x) \) is divided by \( (x - a) \), the remainder is \( f(a) \) — put the root of the divisor into the polynomial. For \( (ax - b) \) the root is \( \dfrac{b}{a} \); for \( (x + 2) \) it is \( -2 \). "Exactly divisible" means remainder 0, and divisibility by a quadratic \( (x - p)(x - q) \) means \( f(p) = 0 \) and \( f(q) = 0 \) — two equations for two unknowns.

What to subtract for exact divisibility: the remainder \( f(a) \). What to add: \( -f(a) \).

By 9 or 3: \( 10 \equiv 1 \), so use the digit sum. By 11: \( 10 \equiv -1 \), so use the alternating digit sum from the right. By 8: \( 1000 \equiv 0 \), so only the last three digits matter. By 7, 11, 13: \( 1001 = 7 \times 11 \times 13 \), so any block of six equal digits vanishes.

Factorials: \( n! \) is a multiple of \( d \) as soon as \( n! \) contains all the prime factors of \( d \) — for \( d = 5 \) from \( 5! \), for \( d = 24 \) from \( 4! \), but for \( d = 25 \) only from \( 10! \). Only the earlier terms of a factorial sum survive.

Power towers: \( a^{b^{c}} \) is read from the top; find the cycle of \( a \) and reduce the exponent \( b^{c} \) modulo the cycle length (often via \( b \equiv \pm 1 \)).