Remainders and Modular Arithmetic

Remainder questions are a placement favourite because they look scary but fall to a few modular rules. They show up in TCS NQT and Cognizant as "find the remainder when a huge power is divided by n".

Core rules (work modulo n)

• (a + b) mod n = (a mod n + b mod n) mod n
• (a × b) mod n = (a mod n × b mod n) mod n
• Negative remainder: if a ≡ n−1, treat it as −1 to simplify powers.
• Fermat's little theorem: if p is prime and gcd(a, p) = 1, then a^(p−1) ≡ 1 (mod p).

Power method: reduce the base mod n, find a small power that gives 1 (or −1), then use the exponent.
Example: 2^10 mod 7. Since 2³ = 8 ≡ 1, write 2^10 = (2³)³ × 2 ≡ 1 × 2 = 2. (Check: 1024 = 7×146 + 2.) ✓

Expression	Reduce to	Remainder
2^10 mod 7	2³ ≡ 1	2
7^100 mod 5	7 ≡ 2, 2⁴ ≡ 1	1
3^101 mod 4	3 ≡ −1	3

Exam Tricks & Tips

• 🎯 Reduce the base first: 43 mod 7 = 1, so 43^n ≡ 1 for any n.
• 🎯 Use −1: if base ≡ −1 (mod n), an even power gives +1 and an odd power gives −1 (i.e. n−1).
• 🎯 For prime n, Fermat instantly cuts the exponent: a^(p−1) ≡ 1.
• 🎯 Split the modulus into coprime parts and combine (e.g. mod 15 via mod 3 and mod 5).
• 🎯 Remainder of a sum/product = do each part mod n, then combine — never multiply the giants out.
• ❌ Don't forget to convert a negative remainder to positive: −2 mod 7 is 5, not −2.

Expected exam pattern: remainder of a large power, remainder of a factorial expression, "last two digits" (mod 100). 1 to 2 questions, ~1 minute each.

Quick recap: Reduce base mod n, hunt for a power giving 1 or −1, apply the exponent, and always report a positive remainder.

Q1. (a × b) mod n = ?
A1. ((a mod n) × (b mod n)) mod n.

Q2. Remainder of 2^10 ÷ 7?
A2. 2³ ≡ 1, so 2^10 ≡ 1×2 = 2.

Q3. What is −2 mod 7 as a positive remainder?
A3. 5.

Q4. State Fermat's little theorem.
A4. If p is prime and gcd(a,p)=1, then a^(p−1) ≡ 1 (mod p).

Q5. Remainder of 7^100 ÷ 5?
A5. 7 ≡ 2 (mod 5), and 2⁴ ≡ 1, so 2^100 = (2⁴)^25 ≡ 1.

Q6. Remainder of 3^101 ÷ 4?
A6. 3 ≡ −1 (mod 4); odd power → −1 ≡ 3.

Q7. How to handle a base that reduces to 1?
A7. Any power of it is ≡ 1, so the remainder is 1.

Q8. How does base ≡ −1 behave under powers?
A8. Even power → +1, odd power → n−1.

Q9. Remainder of (17 × 23) ÷ 5?
A9. 17≡2, 23≡3; 2×3=6 ≡ 1.

Q10. Remainder of 15! ÷ 17?
A10. By Wilson's theorem (p−1)! ≡ −1 (mod p): 16! ≡ −1, and 16!=16×15!, 16≡−1, so 15! ≡ 1 (mod 17).

Q11. How do you find the last two digits of a number?
A11. Compute it modulo 100.

Q12. Why reduce the base before taking a big power?
A12. It keeps the arithmetic tiny while giving the same remainder.

Remainder questions scare people because the numbers are huge — "find the remainder when 7^100 is divided by 5". The trick is that remainders add, subtract and multiply just like ordinary numbers, so you never handle the giant number at all.

What this topic tests: reducing large expressions modulo n, using negative remainders, and applying Fermat/Euler-style cyclicity for powers.

The method

Beginner — the congruence idea

Write a ≡ r (mod n) meaning "a leaves remainder r on division by n". The core fact: you may replace any number by its remainder before multiplying or adding.
Remainder of 17 × 23 mod 5 = (2 × 3) mod 5 = 6 mod 5 = 1. You never multiplied 391.

Intermediate — negative remainders (the biggest time-saver)

If a number is just below a multiple of n, use a negative remainder. 24 ≡ −1 (mod 5). So 24^100 ≡ (−1)^100 = 1. Likewise 99 ≡ −1 (mod 100), 26 ≡ −1 (mod 27). Turning a remainder into ±1 collapses any power instantly.

Advanced — powers and cyclicity

Remainders of powers cycle. To find 7^100 mod 5: 7 ≡ 2, and 2^1,2^2,2^3,2^4 ≡ 2,4,3,1 then repeat with period 4. 100 mod 4 = 0 → take the last of the cycle → 1.
Two named shortcuts:

• Fermat's little theorem: if p is prime and a not divisible by p, a^(p−1) ≡ 1 (mod p). So 7^4 ≡ 1 (mod 5) directly.
• Chinese-remainder splitting: for a composite modulus like 35, find the remainder mod 5 and mod 7 separately, then combine.

Worked example

Remainder when 43^197 is divided by 7. 43 ≡ 1 (mod 7) because 42 is a multiple of 7. So 43^197 ≡ 1^197 = 1. The exponent 197 never mattered once the base reduced to 1.

Harder: 2^100 mod 7. 2^3 = 8 ≡ 1 (mod 7), period 3. 100 mod 3 = 1 → 2^1 = 2.

Where it appears

TCS NQT "advanced" quant, Amazon and Goldman Sachs first rounds, and inside cyclicity/unit-digit and calendar (day-of-week) problems everywhere.

Speed tricks and shortcuts

• Always look for ±1 first: reduce the base to 1 or −1 mod n and the power dies.
• Cycle length of powers mod n is at most n−1 (often much less); find the small cycle, then take exponent mod cycle-length.
• Mnemonic: "Reduce first, power later."
• (a^n − b^n) is always divisible by (a − b); it is divisible by (a + b) when n is even.

Key formulas

• (a + b) mod m = [(a mod m) + (b mod m)] mod m; same for product.
• Fermat's little theorem: a^(p−1) ≡ 1 (mod p) for prime p, gcd(a,p)=1.
• Euler: a^φ(n) ≡ 1 (mod n) when gcd(a,n)=1; φ(p) = p−1.
• Cyclicity of remainders repeats; find the pattern of powers mod m.
• Chinese remainder theorem combines coprime moduli.
• Wilson: (p−1)! ≡ −1 (mod p) for prime p.

Usage: reduce each factor mod m first, then use Fermat/Euler for large exponents.

Worked Example

Problem: Find the remainder when 2^100 is divided by 7.

Solution: Reduce the powers of 2 modulo 7 and look for a repeating cycle:

• 2^1 ≡ 2
• 2^2 ≡ 4
• 2^3 ≡ 8 ≡ 1 (mod 7)

Once we hit 1, the pattern of remainders repeats every 3 powers: (2, 4, 1, 2, 4, 1, …). So the remainder of 2^n depends only on n mod 3.

Compute 100 mod 3: 100 = 3 × 33 + 1, so 100 ≡ 1 (mod 3).

Therefore 2^100 ≡ 2^1 ≡ 2 (mod 7).

A cleaner way to see it: 2^100 = (2^3)^33 × 2^1 = 8^33 × 2 ≡ 1^33 × 2 ≡ 2 (mod 7).

Answer: 2.