Division Algorithm
A Remainder ($R$) is the left-over quantity when integer dividend $A$ is divided by divisor $D$: $A = D \cdot Q + R$ where $0 \le R < D$.
Modular Clock Model
Think of division by $D$ as a clock face with $D$ hours ($0$ to $D-1$). Every multiple of $D$ completes full revolutions and resets to zero!
- • $26 \pmod 7 \implies 3$ full loops of 7 ($21$) + $5$ steps $\implies R = 5$.
- • Negative Remainder: $5$ steps forward is identical to $-2$ steps backward ($5 + |-2| = 7$).
- • Multiplicative Congruence: $\text{Rem}(A \times B) = \text{Rem}(\text{Rem}(A) \times \text{Rem}(B))$.
Remainder theorems (Euler, Fermat, Wilson, Binomial) are high-yield questions in CAT quant section and SNAP/NMAT speed rounds:
Euler's Totient Theorem
When $\gcd(a,n) = 1$. Here $\phi(n) = n(1 - 1/p_1)(1 - 1/p_2)\dots$
Fermat's Little Theorem
When $p$ is prime and $\gcd(a,p) = 1$. Special case of Euler's theorem!
Wilson's Theorem
For any prime $p$. Example: $6! \equiv -1 \equiv 6 \pmod 7$.
Binomial Remainder Rules ($(a \pm 1)^n / a$)
Rule A: $(a+1)^n / a$
$\text{Remainder} = \mathbf{1}$ (for all $n$)Rule B: $(a-1)^n / a$ (Even $n$)
$\text{Remainder} = \mathbf{1}$ (since $(-1)^{\text{even}} = +1$)Rule C: $(a-1)^n / a$ (Odd $n$)
$\text{Remainder} = -1 \equiv \mathbf{a - 1}$SHORTCUT RULES & POWER CYCLICITY
Power Remainder Pattern
Used when power exponents can be reduced into repeating cyclic remainders.
Common Factor Rescaling Rule
Cancel common factor $k$ to simplify division, then multiply the resulting remainder by $k$!
SOLVED EXAMPLES (LEVEL 0 TO HARD)
Q: Find the remainder when $67^{67} + 67$ is divided by 68.
Step 1: $67 \equiv -1 \pmod{68}$.
Step 2: $67^{67} \equiv (-1)^{67} \equiv -1 \pmod{68}$.
Step 3: Expression $\equiv -1 + 67 = 66 \pmod{68}$.
Q: What is the remainder when $2^{100}$ is divided by 101? (Note: 101 is prime).
Step 1: Identify prime $p = 101$ and $a = 2$. Check $\gcd(2, 101) = 1$.
Step 2: Apply Fermat's Little Theorem: $a^{p-1} \equiv 1 \pmod p$.
Step 3: $2^{101-1} = 2^{100} \equiv 1 \pmod{101} \implies \text{Remainder = 1}$.
Q: Find the remainder when $32^{32^{32}}$ is divided by 7.
Step 1: Reduce base: $32 \equiv 4 \pmod 7$. Expression $= 4^{32^{32}} \pmod 7$.
Step 2: By Fermat's Theorem on divisor 7: $4^6 \equiv 1 \pmod 7$. Power cycle $= 6$.
Step 3: Find power exponent modulo 6: $32^{32} \pmod 6 \implies (-4)^{32} \equiv 4^{32} \pmod 6$. Since $4^k \pmod 6 = 4$ for all $k \ge 1 \implies \text{Exponent} \equiv 4 \pmod 6$.
Step 4: Remainder $= 4^4 \pmod 7 = 256 \pmod 7 = \mathbf{4}$.
Mistake 1
Forgetting Factor Multiplication Back
Cancelling a factor $k$ to simplify division but forgetting to multiply the final remainder by $k$.
Mistake 2
Using Fermat on Non-Primes
Applying $a^{p-1} \equiv 1$ when $p$ is composite. For composite divisors, use Euler's Totient $\phi(n)$.
Mistake 3
Negative Remainder Unadjusted
Leaving answer as negative (e.g. $-3$). Always convert to positive remainder: $-3 + \text{Divisor}$.
1. What is the remainder when $2^{33}$ is divided by 9?
Answer: $2^3 = 8 \equiv -1 \pmod 9 \implies (2^3)^{11} = (-1)^{11} = -1 \equiv 8 \pmod 9$. Remainder = 8.
2. Find the remainder when $100!$ is divided by 101.
Answer: 101 is prime. By Wilson's Theorem, $(101-1)! = 100! \equiv -1 \equiv 100 \pmod{101}$. Remainder = 100.
3. Find the remainder when $7^{84}$ is divided by 342.
Answer: $7^3 = 343 \equiv 1 \pmod{342} \implies (7^3)^{28} = 1^{28} = 1$. Remainder = 1.
FREQUENTLY ASKED QUESTIONS
❓ What is Fermat's Little Theorem for remainders?
If p is a prime number and gcd(a, p) = 1, then a^(p-1) leaves a remainder of 1 when divided by p, i.e., a^(p-1) ≡ 1 (mod p).
❓ What is Euler's Totient Function φ(n)?
Euler's Totient function φ(n) counts the number of integers up to n that are co-prime to n. For n = p1^a * p2^b, φ(n) = n * (1 - 1/p1) * (1 - 1/p2).
❓ How does the Negative Remainder concept work?
A negative remainder -k is equivalent to a positive remainder (Divisor - k). For example, 26 divided by 7 gives remainder 5 or -2. (5 + |-2| = 7).