Prelims · 8 Mental Ability · 8.1 Number system and simplification
8.1.11 Remainder theorems: cyclicity, Fermat, Wilson and negative remainders
Replace each number by its remainder (or a small negative remainder), find a power that leaves 1 or −1, and the remainder of even a huge expression drops out in two lines.
- APPSC Group 2 · Prelims
- Standard level
- 6 min read
- Free
Core facts
- Division: dividend = divisor × quotient + remainder, with 0 ≤ remainder < divisor.
- Sum and product rules: the remainder of a sum (or product) = the remainder of the sum (or product) of the remainders.
- Negative remainder: a number just below the divisor can be used as a negative: 98 on 100 is −2. Convert back by adding the divisor.
- Cyclicity: remainders of powers aⁿ on m repeat; find the first power leaving 1.
- Fermat's little theorem: if p is prime and p does not divide a, then a^(p − 1) leaves 1 on p.
- Wilson's theorem: if p is prime, (p − 1)! leaves p − 1 (that is, −1) on p.
- Euler's theorem (for any m): if a and m are co-prime, a^φ(m) leaves 1 on m (φ as in MAB-NS-10).
- Algebra: aⁿ − bⁿ is divisible by a − b; by a + b too when n is even. aⁿ + bⁿ is divisible by a + b when n is odd.
Example 1. Remainder when 47 × 53 × 61 is divided by 9. Solution. Remainders 2, 8, 7. 2 × 8 × 7 = 112, which leaves 4. Answer: 4
Example 2. Remainder when 98 × 99 is divided by 100. Solution. (−2) × (−1) = 2. Answer: 2
Example 3. Remainder when 2¹⁰⁰ is divided by 7. Solution. 2³ = 8 leaves 1. 2¹⁰⁰ = (2³)³³ × 2. Answer: 2
Explained
Type 1: Fermat for a prime divisor.
Example 4. Remainder when 5⁶² is divided by 13. (a) 1 (b) 5 (c) 12 (d) 8 Solution. 13 is prime, so 5¹² leaves 1. 62 = 12 × 5 + 2, so the remainder is that of 5² = 25, which is 12. Answer: (c) 12
- Faster: 5² = 25 leaves −1, so 5⁴ leaves 1; 5⁶² = (5⁴)¹⁵ × 5² → −1, that is 12.
Example 5. Remainder when 3²⁰⁰ is divided by 11. Solution. Fermat: 3¹⁰ leaves 1 (in fact 3⁵ = 243 = 22 × 11 + 1 already does). 200 is a multiple of 5. Answer: 1
Type 2: Wilson for factorials.
Example 6. Remainders when (i) 22! and (ii) 21! are divided by 23. Solution. (i) 23 is prime, so 22! leaves −1, that is 22. (ii) 22! = 22 × 21!, and 22 leaves −1. So (−1) × (21!) leaves −1, meaning 21! leaves 1. Answer: (i) 22 (ii) 1
Type 3: negative remainders with large powers.
Example 7. Remainder when 2²⁰³ is divided by 17. Solution. 2⁴ = 16 leaves −1, so 2⁸ leaves 1. 203 = 8 × 25 + 3, so the remainder is that of 2³. Answer: 8
Example 8. Which of these divides 29³⁶ − 1: 28, 30, both, or neither? Solution. aⁿ − 1 is divisible by a − 1 = 28 always, and by a + 1 = 30 because 36 is even. Answer: both
Type 4: numbers formed by writing integers in a row. Use the digit sum for 3 and 9, and the last digits for 2, 4, 8.
Example 9. N = 123456789101112…3940 (1 to 40 written in a row). Find the remainders when N is divided by 9 and by 8. Solution. Digit sum leaves the same remainder on 9 as 1 + 2 + … + 40 = 820, and 820 leaves 1. For 8, use the last three digits, 940, which leaves 4. Answer: 1 and 4
Type 5: division-sum relations.
Example 10. In a division sum the divisor is 12 times the quotient and 4 times the remainder. The remainder is 18. Find the dividend. Solution. Divisor = 4 × 18 = 72; quotient = 72 ÷ 12 = 6. Dividend = 72 × 6 + 18. Answer: 450
Speed tips.
- Look for a base that is 1 more or 1 less than the divisor: 37 on 36 is 1, 35 on 36 is −1.
- For aⁿ + bⁿ or aⁿ − bⁿ with a + b or a − b equal to the divisor, the remainder is 0 without any arithmetic.
Common traps
- ✗ "98 × 99 on 100 leaves −2 × −1 = −2." ✓ (−2)(−1) = +2.
- ✗ "Fermat applies to any divisor: 2⁸ leaves 1 on 9." ✓ Fermat needs a prime; on 9, 2⁶ leaves 1 (Euler, φ(9) = 6), and 2⁸ leaves 4.
- ✗ "21! on 23 leaves 22 by Wilson." ✓ Wilson gives 22! → 22; then 21! → 1.
- ✗ "17²³ + 23²³ on 40: work out the powers." ✓ Odd power and 17 + 23 = 40: remainder 0.
- ✗ "A negative remainder is the final answer." ✓ Add the divisor: −1 on 13 is 12.
Quick revision
- Remainder of sum/product = sum/product of remainders.
- Use negative remainders for numbers just below the divisor.
- Fermat: a^(p−1) → 1 on prime p (p ∤ a).
- Wilson: (p − 1)! → p − 1 on prime p; (p − 2)! → 1.
- Euler: a^φ(m) → 1 on m for co-prime a, m.
- aⁿ − bⁿ ÷ (a − b) always; ÷ (a + b) for even n.
- aⁿ + bⁿ ÷ (a + b) for odd n.
- Last two digits = remainder on 100; 7⁴ = 2,401.
- Split a composite divisor into co-prime parts and combine.
- Concatenated numbers: digit sum for 3, 9; last digits for 2, 4, 8.
Go deeper: Deeper (beyond what APPSC Group 2 usually asks)
Deeper Advanced
Example 11. Last two digits of 7²⁰²⁷. (a) 07 (b) 43 (c) 49 (d) 01 Solution. 7⁴ = 2,401 leaves 1 on 100. 2027 = 4 × 506 + 3, so the last two digits are those of 7³ = 343. Answer: (b) 43
Example 12. Remainder when 17²³ + 23²³ is divided by 40. Solution. The power is odd and 17 + 23 = 40, so the sum is divisible by 40. Answer: 0
Example 13. Remainder when 3⁵⁰ is divided by 35. Solution. Split 35 = 5 × 7. On 5: 3⁴ leaves 1, so 3⁵⁰ leaves 3² = 9 → 4. On 7: 3⁶ leaves 1, so 3⁵⁰ leaves 3² → 2. The number below 35 leaving 4 on 5 and 2 on 7: 9. Answer: 9
- Short cut: both cycles (4 and 6) divide 12, so 3¹² leaves 1 on 35; 3⁵⁰ = (3¹²)⁴ × 3² → 9.
Example 14. Remainder when 7⁵⁰ is divided by 20. Solution. 7 and 20 are co-prime; 7⁴ = 2,401 leaves 1 on 20. 7⁵⁰ = (7⁴)¹² × 7² → 49 → 9. Answer: 9
Example 15. Remainder when 10¹ + 10² + … + 10¹⁰⁰ is divided by 6. Solution. Every power of 10 leaves 4 on 6. 100 terms leave 400, and 400 leaves 4. Answer: 4
- Concatenated numbers of a given length: some questions fix the number of digits (for example, "a 99-digit number formed by writing 1, 2, 3, … in a row"). First find the last integer written (MAB-NS-14 shows how), then apply Type 4.
Practise this topic. Questions on Number system & number puzzles, with answers explained.
All Number system and simplification notes · APPSC Group 2 syllabus · APPSC G2 Prelims Mock 1 with answers · Start free
Medha AI writes its own notes and checks them against the sources listed. Medha AI is an independent preparation service. It is not affiliated with, endorsed by or connected to APPSC, TSPSC, MPSC, UPSC or any other commission or government body.