Free CAT library

Advanced Remainders: Binomial, Fermat & Cyclicity

Demolish complex remainder problems using the Binomial Theorem, negative remainders, and Fermat's Little Theorem.

1. The Story & Mental Model

Imagine dividing a massive pile of 3710037^{100} candies among 9 children. Obviously, you can't multiply 37 by itself 100 times. Instead, think of 37 as (36+1)(36 + 1).

Every time you hand out a batch of 36 candies, it divides perfectly among the 9 children, leaving exactly 1 candy leftover.

If you do this 100 times, the perfect batches of 36 are always eaten perfectly. All that's left is the 1×1…1001 \times 1 \dots 100 times. The remainder is just 1100=11^{100} = 1.

What if it was 3510035^{100} candies? 35=36−135 = 36 - 1. The remainder is (−1)100=+1(-1)^{100} = +1.

This is the essence of the Binomial Remainder Theorem: strip away the massive multiple of the divisor, and only raise the tiny 'leftover' (or deficit) to the massive power!

2. The CAT Question Blueprint

Exam setters use massive exponents to induce panic. The standard formats are:

  • Find the remainder of (ax+1)n/x(ax + 1)^n / x or (ax−1)n/x(ax - 1)^n / x. (Binomial).

  • Find the remainder when the base is completely unrelated to the divisor, but the divisor is prime. (Fermat's).

  • Algebraic remainders: Is an+bna^n + b^n divisible by a+ba + b? (Standard Identities).

3. Core Concepts, Formulae & Derivations

A. The Binomial Remainder Theorem

  • When (ax+k)n(ax + k)^n is divided by xx, the remainder is the remainder of kn/xk^n / x.

  • Specifically:

    • (ax+1)n÷x  ⟹  (ax + 1)^n \div x \implies Remainder is 11.

    • (ax−1)n÷x  ⟹  (ax - 1)^n \div x \implies Remainder is (−1)n(-1)^n. (If nn is even, R=1R=1. If nn is odd, R=−1R = -1. Remember, a remainder of −1-1 means the actual remainder is x−1x - 1).

B. Negative Remainders

A remainder must be positive, but during calculations, negative remainders are incredibly powerful.

  • What is 14(mod1)514 \pmod 15? It is 14. But it is also −1-1.

  • If you need (14)55(mod1)5(14)^{55} \pmod 15, it's much easier to calculate (−1)55=−1(-1)^{55} = -1.

  • Convert the final negative remainder back to positive: −1+15=14-1 + 15 = 14.

C. Fermat's Little Theorem

If pp is a prime number, and aa is any integer not divisible by pp, then:

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p

  • This means ap−1a^{p-1} divided by pp always leaves a remainder of 1.

  • E.g., 26÷72^{6} \div 7 leaves a remainder of 1.

D. Standard Algebraic Divisibility

  • an−bna^n - b^n is ALWAYS divisible by (a−b)(a - b) for all nn.

  • an−bna^n - b^n is divisible by (a+b)(a + b) ONLY when nn is EVEN.

  • an+bna^n + b^n is divisible by (a+b)(a + b) ONLY when nn is ODD.

  • an+bna^n + b^n is NEVER divisible by (a−b)(a - b).

4. Common Pitfalls & Speed Shortcuts

  • Pitfall: Forgetting to convert a negative remainder back to positive at the end of the problem. If you get a remainder of -4 when dividing by 13, the answer is NOT -4. It is 13−4=913 - 4 = 9.

  • Shortcut: To find the remainder of a massive power like 21002^{100} divided by 7, look for a power of 2 that is close to a multiple of 7. 23=82^3 = 8, and 8=7+18 = 7+1. Thus, rewrite 21002^{100} as (23)33×2=833×2=(7+1)33×2(2^3)^{33} \times 2 = 8^{33} \times 2 = (7+1)^{33} \times 2. The remainder is instantly 133×2=21^{33} \times 2 = 2.

Formulas

Binomial Remainder

(ax+k)n≡kn(modx)(ax + k)^n \equiv k^n \pmod x

Strip away the multiple of x.
Fermat's Little Theorem

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p

p must be prime, and a must not be a multiple of p.
Algebraic Divisibility

(an+bn) is divisible by (a+b) if n is odd(a^n + b^n) \text{ is divisible by } (a+b) \text{ if } n \text{ is odd}

Think of a^3 + b^3 = (a+b)(a^2 - ab + b^2).

Traps and tips

  • Final remainders MUST be positive. Convert negative remainders by adding the divisor.
  • Fermat's Little Theorem only works when the divisor is prime.
  • When using Binomial, try to make the leftover 'k' equal to 1 or -1 for easy exponentiation.

Solved examples

The $+1$ Binomial Strike

Find the remainder when 3710037^{100} is divided by 9.

Show solution

We look for a multiple of 9 close to 37.

The closest multiple is 36.

Rewrite the base: 37=36+1=(4×9)+137 = 36 + 1 = (4 \times 9) + 1.

Using the binomial remainder theorem:

(36+1)100(mod9)≡(1)100(mod9)(36 + 1)^{100} \pmod 9 \equiv (1)^{100} \pmod 9.

1100=11^{100} = 1.

The remainder is 1.

Takeaway: Always try to express the base as (Multiple of Divisor) +/- 1.

The Negative Phantom

Find the remainder when 249924^{99} is divided by 25.

Show solution

We look for a multiple of 25 close to 24.

The closest is 25 itself.

Rewrite the base: 24=25−124 = 25 - 1.

Using the binomial theorem:

(25−1)99(mod25)≡(−1)99(mod25)(25 - 1)^{99} \pmod{25} \equiv (-1)^{99} \pmod{25}.

Since 99 is an odd power, (−1)99=−1(-1)^{99} = -1.

So the remainder is -1.

However, remainders must be strictly positive.

To convert a negative remainder, add the divisor.

Positive Remainder = −1+25=24-1 + 25 = 24.

The final remainder is 24.

Takeaway: An odd power preserves the negative sign. Always add the divisor to a final negative remainder to get the actual answer.

Fermat's Prime Shortcut

What is the remainder when 31023^{102} is divided by 101?

Show solution

Notice that the divisor, 101, is a prime number.

This is a perfect candidate for Fermat's Little Theorem: ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p.

Here, a=3a = 3 and p=101p = 101.

According to the theorem, 3100≡1(mod101)3^{100} \equiv 1 \pmod{101}.

We need to find the remainder for 31023^{102}.

Split the exponent:

3102=3100×323^{102} = 3^{100} \times 3^2.

Substitute the remainder for the first part:

3102≡1×9(mod101)3^{102} \equiv 1 \times 9 \pmod{101}.

1×9=91 \times 9 = 9.

The remainder is 9.

Takeaway: Whenever dividing a massive power by a prime number p, immediately extract powers of (p-1) and replace them with 1.

Bridging the Gap

Find the remainder when 21002^{100} is divided by 7.

Show solution

The base is 2 and divisor is 7. 2 is not close to a multiple of 7.

We need to find a power of 2 that is close to a multiple of 7.

Let's check powers of 2: 21=2,22=4,23=82^1=2, 2^2=4, 2^3=8.

8 is exactly 7+17 + 1!

So we will rewrite 21002^{100} using the base 232^3.

Divide the power 100 by 3: 100=33×3+1100 = 33 \times 3 + 1.

2100=(23)33×212^{100} = (2^3)^{33} \times 2^1

=833×2= 8^{33} \times 2.

Now find the remainder when divided by 7:

833≡(7+1)33≡133≡1(mod7)8^{33} \equiv (7+1)^{33} \equiv 1^{33} \equiv 1 \pmod 7.

Substitute this back:

1×2=21 \times 2 = 2.

The remainder is 2.

Takeaway: If the base isn't close to a multiple of the divisor, raise the base to a small power until it hits a (Multiple +/- 1).

Algebraic Divisibility (Odd Sums)

Is 1741+244117^{41} + 24^{41} divisible by 41?

Show solution

This is of the form an+bna^n + b^n.

Here, a=17a = 17, b=24b = 24, and n=41n = 41.

The rule states that an+bna^n + b^n is divisible by (a+b)(a + b) if and only if nn is odd.

Since n=41n = 41 is odd, the expression is divisible by (17+24)(17 + 24).

17+24=4117 + 24 = 41.

Therefore, the expression is exactly divisible by 41. The remainder is 0.

Takeaway: a^n + b^n is divisible by a+b for odd n. This instantly solves seemingly impossible large-number addition remainders.

The Tower of Powers

Find the remainder when 32323232^{32^{32}} is divided by 7.

Show solution

First, let's simplify the base. 32÷7=432 \div 7 = 4 with a remainder of 4.

So 32≡4(mod7)32 \equiv 4 \pmod 7.

We need to find 4Power(mod7)4^{\text{Power}} \pmod 7, where Power =3232= 32^{32}.

Since 7 is prime, Fermat's Little Theorem says 46≡1(mod7)4^6 \equiv 1 \pmod 7.

The cycle repeats every 6th power. So we need to find what slot 323232^{32} lands in when divided by 6.

We need: 3232(mod6)32^{32} \pmod 6.

Let's calculate 3232(mod6)32^{32} \pmod 6:

32≡2(mod6)32 \equiv 2 \pmod 6.

So we need 232(mod6)2^{32} \pmod 6.

Let's check powers of 2 mod 6:

21=2(mod6)2^1 = 2 \pmod 6

22=4(mod6)2^2 = 4 \pmod 6

23=8≡2(mod6)2^3 = 8 \equiv 2 \pmod 6

24=16≡4(mod6)2^4 = 16 \equiv 4 \pmod 6

Even powers of 2 give a remainder of 4. Since 32 is even, 232≡4(mod6)2^{32} \equiv 4 \pmod 6.

So the Power 323232^{32} is of the form 6k+46k + 4.

Now go back to the original problem:

46k+4(mod7)≡(46)k×44(mod7)4^{6k+4} \pmod 7 \equiv (4^6)^k \times 4^4 \pmod 7.

By Fermat, 46≡1(mod7)4^6 \equiv 1 \pmod 7.

So we just need 44(mod7)4^4 \pmod 7.

44=2564^4 = 256.

256/7=36256 / 7 = 36 remainder 4.

Alternatively, for 444^4: (16)×(16)≡2×2=4(mod7)(16) \times (16) \equiv 2 \times 2 = 4 \pmod 7.

The final remainder is 4.

Takeaway: For tower powers A^(B^C) mod p, use Fermat to find the cyclicity (p-1) of the base A. Then, find the remainder of the exponent B^C when divided by (p-1).

Practice questions

Question 1 · CAT Level

What is the remainder when 97!97! is divided by the prime number 101101?

  1. A

    17

  2. B

    34

  3. C

    67

  4. D

    84

Show answer and explanation

Answer: (A) 17

By Wilson’s Theorem, for any prime pp, (p−1)!≡−1(modp)(p-1)! \equiv -1 \pmod p. Here p=101p = 101, so 100!≡−1(mod101)100! \equiv -1 \pmod{101}.

Expanding the factorial from 97!97!:

100!=97!×98×99×100≡97!×(−3)×(−2)×(−1)(mod101)100! = 97! \times 98 \times 99 \times 100 \equiv 97! \times (-3) \times (-2) \times (-1) \pmod{101}.

This simplifies to 100!≡−6×97!(mod101)100! \equiv -6 \times 97! \pmod{101}.

Equating with Wilson’s result gives −6×97!≡−1  ⟹  6×97!≡1(mod101)-6 \times 97! \equiv -1 \implies 6 \times 97! \equiv 1 \pmod{101}.

To find the modular inverse of 66 modulo 101101, observe that 101+1=102101 + 1 = 102, and 102=6×17102 = 6 \times 17.

Thus 6×17≡102≡1(mod101)6 \times 17 \equiv 102 \equiv 1 \pmod{101}.

Multiplying both sides by 1717 yields 97!≡17(mod101)97! \equiv 17 \pmod{101}.

Question 2 · CAT Level

Find the remainder when 310003^{1000} is divided by 7777.

  1. A

    43

  2. B

    55

  3. C

    67

  4. D

    71

Show answer and explanation

Answer: (C) 67

Factorise the modulus 77=7×1177 = 7 \times 11. We evaluate the remainder modulo 77 and modulo 1111 using Fermat’s Little Theorem.

Modulo 77: by Fermat’s theorem, 36≡1(mod7)3^6 \equiv 1 \pmod 7. Since 1000=6(166)+41000 = 6(166) + 4, 31000≡34=81≡4(mod7)3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7.

Modulo 1111: by Fermat’s theorem, 310≡1(mod11)3^{10} \equiv 1 \pmod{11}. Since 1000=10(100)1000 = 10(100), 31000≡1100≡1(mod11)3^{1000} \equiv 1^{100} \equiv 1 \pmod{11}.

Now combine using the Chinese Remainder Theorem: N≡1(mod11)  ⟹  N=11k+1N \equiv 1 \pmod{11} \implies N = 11k + 1.

Substituting into modulo 77: 11k+1≡4k+1≡4(mod7)  ⟹  4k≡3≡24(mod7)  ⟹  k≡6(mod7)11k + 1 \equiv 4k + 1 \equiv 4 \pmod 7 \implies 4k \equiv 3 \equiv 24 \pmod 7 \implies k \equiv 6 \pmod 7.

Taking the smallest non-negative integer k=6k = 6 gives N=11(6)+1=67N = 11(6) + 1 = 67.

Since 0≤67<770 \le 67 < 77, the remainder when 310003^{1000} is divided by 7777 is 6767.

Question 3 · CAT Level

What is the remainder when 31023^{102} is divided by 102102?

  1. A

    9

  2. B

    15

  3. C

    21

  4. D

    27

Show answer and explanation

Answer: (B) 15

Notice that the base 33 and divisor 102102 share a common factor 33: 102=3×34102 = 3 \times 34.

Divide both the dividend and divisor by 33: we need to compute 3101(mod34)3^{101} \pmod{34}, and then multiply the result by 33.

For the reduced modulus 34=2×1734 = 2 \times 17, gcd⁡(3,34)=1\gcd(3, 34) = 1.

Euler’s totient is ϕ(34)=34(1−12)(1−117)=16\phi(34) = 34\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{17}\right) = 16.

By Euler’s Totient Theorem, 316≡1(mod34)3^{16} \equiv 1 \pmod{34}.

Reducing the exponent: 101=16(6)+5101 = 16(6) + 5, so 3101≡35=243(mod34)3^{101} \equiv 3^5 = 243 \pmod{34}.

Since 243=34×7+5243 = 34 \times 7 + 5, we have 3101≡5(mod34)3^{101} \equiv 5 \pmod{34}.

Multiplying the common factor 33 back in: 3×5=153 \times 5 = 15. Thus the remainder is 1515.

Question 4 · CAT Level

What is the remainder when the power tower 37383937^{38^{39}} is divided by 1313?

  1. A

    3

  2. B

    7

  3. C

    9

  4. D

    11

Show answer and explanation

Answer: (C) 9

Because 1313 is prime and gcd⁡(37,13)=1\gcd(37, 13) = 1, by Fermat’s Little Theorem 3712≡1(mod13)37^{12} \equiv 1 \pmod{13}.

Therefore, we need to evaluate the exponent modulo 1212: E=3839(mod12)E = 38^{39} \pmod{12}.

Since 38≡2(mod12)38 \equiv 2 \pmod{12}, we have 3839≡239(mod12)38^{39} \equiv 2^{39} \pmod{12}.

Examining powers of 22 modulo 1212: 21=2,22=4,23=8,24=4,25=8,…2^1=2, 2^2=4, 2^3=8, 2^4=4, 2^5=8, \dots; for all k≥2k \ge 2, 2k≡82^k \equiv 8 when kk is odd.

Since the exponent 3939 is odd, 239≡8(mod12)2^{39} \equiv 8 \pmod{12}, meaning E=12m+8E = 12m + 8.

Now reduce the base: 37≡−2(mod13)37 \equiv -2 \pmod{13}.

Thus 373839≡(−2)8=256(mod13)37^{38^{39}} \equiv (-2)^8 = 256 \pmod{13}.

Dividing 256256 by 1313: 256=13×19+9≡9(mod13)256 = 13 \times 19 + 9 \equiv 9 \pmod{13}, giving a remainder of 99.

Question 5 · CAT Level

What is the remainder when 1399+1599+1799+199913^{99} + 15^{99} + 17^{99} + 19^{99} is divided by 128128?

  1. A

    0

  2. B

    32

  3. C

    64

  4. D

    96

Show answer and explanation

Answer: (C) 64

Group the terms symmetrically around 1616: (16−3)99+(16+3)99(16 - 3)^{99} + (16 + 3)^{99} and (16−1)99+(16+1)99(16 - 1)^{99} + (16 + 1)^{99}.

By binomial expansion, (16−x)99+(16+x)99=2[(991)(16)x98+(993)(163)x96+… ](16-x)^{99} + (16+x)^{99} = 2 \left[ \binom{99}{1}(16)x^{98} + \binom{99}{3}(16^3)x^{96} + \dots \right].

Since 163=409616^3 = 4096 is a multiple of 128128, all terms from the second onward vanish modulo 128128.

Thus each pair simplifies to 2×99×16×x98=32×99×x98(mod128)2 \times 99 \times 16 \times x^{98} = 32 \times 99 \times x^{98} \pmod{128}.

Summing both pairs: S≡32×99×(398+198)(mod128)S \equiv 32 \times 99 \times (3^{98} + 1^{98}) \pmod{128}.

Notice that 32=9=8+13^2 = 9 = 8 + 1, so 398=(8+1)49≡1+49(8)≡1(mod4)3^{98} = (8+1)^{49} \equiv 1 + 49(8) \equiv 1 \pmod 4, meaning 398+1≡2(mod4)3^{98} + 1 \equiv 2 \pmod 4.

Writing 398+1=4k+23^{98} + 1 = 4k + 2, we get S≡32×99×(4k+2)=64×99(2k+1)(mod128)S \equiv 32 \times 99 \times (4k + 2) = 64 \times 99(2k + 1) \pmod{128}.

Since 99(2k+1)99(2k+1) is odd, 64×odd≡64(mod128)64 \times \text{odd} \equiv 64 \pmod{128}, so the remainder is 6464.

Study this concept with interactive practice in PrepSoc.

Open the concept library