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 candies among 9 children. Obviously, you can't multiply 37 by itself 100 times. Instead, think of 37 as .
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 times. The remainder is just .
What if it was candies? . The remainder is .
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 or . (Binomial).
-
Find the remainder when the base is completely unrelated to the divisor, but the divisor is prime. (Fermat's).
-
Algebraic remainders: Is divisible by ? (Standard Identities).
3. Core Concepts, Formulae & Derivations
A. The Binomial Remainder Theorem
-
When is divided by , the remainder is the remainder of .
-
Specifically:
-
Remainder is .
-
Remainder is . (If is even, . If is odd, . Remember, a remainder of means the actual remainder is ).
-
B. Negative Remainders
A remainder must be positive, but during calculations, negative remainders are incredibly powerful.
-
What is ? It is 14. But it is also .
-
If you need , it's much easier to calculate .
-
Convert the final negative remainder back to positive: .
C. Fermat's Little Theorem
If is a prime number, and is any integer not divisible by , then:
-
This means divided by always leaves a remainder of 1.
-
E.g., leaves a remainder of 1.
D. Standard Algebraic Divisibility
-
is ALWAYS divisible by for all .
-
is divisible by ONLY when is EVEN.
-
is divisible by ONLY when is ODD.
-
is NEVER divisible by .
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 .
-
Shortcut: To find the remainder of a massive power like divided by 7, look for a power of 2 that is close to a multiple of 7. , and . Thus, rewrite as . The remainder is instantly .
Formulas
| Binomial Remainder | |
|---|---|
| Fermat's Little Theorem | |
| Algebraic Divisibility |
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 is divided by 9.
Show solution
We look for a multiple of 9 close to 37.
The closest multiple is 36.
Rewrite the base: .
Using the binomial remainder theorem:
.
.
The remainder is 1.
Takeaway: Always try to express the base as (Multiple of Divisor) +/- 1.
The Negative Phantom
Find the remainder when is divided by 25.
Show solution
We look for a multiple of 25 close to 24.
The closest is 25 itself.
Rewrite the base: .
Using the binomial theorem:
.
Since 99 is an odd power, .
So the remainder is -1.
However, remainders must be strictly positive.
To convert a negative remainder, add the divisor.
Positive Remainder = .
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 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: .
Here, and .
According to the theorem, .
We need to find the remainder for .
Split the exponent:
.
Substitute the remainder for the first part:
.
.
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 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: .
8 is exactly !
So we will rewrite using the base .
Divide the power 100 by 3: .
.
Now find the remainder when divided by 7:
.
Substitute this back:
.
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 divisible by 41?
Show solution
This is of the form .
Here, , , and .
The rule states that is divisible by if and only if is odd.
Since is odd, the expression is divisible by .
.
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 is divided by 7.
Show solution
First, let's simplify the base. with a remainder of 4.
So .
We need to find , where Power .
Since 7 is prime, Fermat's Little Theorem says .
The cycle repeats every 6th power. So we need to find what slot lands in when divided by 6.
We need: .
Let's calculate :
.
So we need .
Let's check powers of 2 mod 6:
Even powers of 2 give a remainder of 4. Since 32 is even, .
So the Power is of the form .
Now go back to the original problem:
.
By Fermat, .
So we just need .
.
remainder 4.
Alternatively, for : .
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 is divided by the prime number ?
Show answer and explanation
Answer: (A) 17
By Wilson’s Theorem, for any prime , . Here , so .
Expanding the factorial from :
.
This simplifies to .
Equating with Wilson’s result gives .
To find the modular inverse of modulo , observe that , and .
Thus .
Multiplying both sides by yields .
Question 2 · CAT Level
Find the remainder when is divided by .
Show answer and explanation
Answer: (C) 67
Factorise the modulus . We evaluate the remainder modulo and modulo using Fermat’s Little Theorem.
Modulo : by Fermat’s theorem, . Since , .
Modulo : by Fermat’s theorem, . Since , .
Now combine using the Chinese Remainder Theorem: .
Substituting into modulo : .
Taking the smallest non-negative integer gives .
Since , the remainder when is divided by is .
Question 3 · CAT Level
What is the remainder when is divided by ?
Show answer and explanation
Answer: (B) 15
Notice that the base and divisor share a common factor : .
Divide both the dividend and divisor by : we need to compute , and then multiply the result by .
For the reduced modulus , .
Euler’s totient is .
By Euler’s Totient Theorem, .
Reducing the exponent: , so .
Since , we have .
Multiplying the common factor back in: . Thus the remainder is .
Question 4 · CAT Level
What is the remainder when the power tower is divided by ?
Show answer and explanation
Answer: (C) 9
Because is prime and , by Fermat’s Little Theorem .
Therefore, we need to evaluate the exponent modulo : .
Since , we have .
Examining powers of modulo : ; for all , when is odd.
Since the exponent is odd, , meaning .
Now reduce the base: .
Thus .
Dividing by : , giving a remainder of .
Question 5 · CAT Level
What is the remainder when is divided by ?
Show answer and explanation
Answer: (C) 64
Group the terms symmetrically around : and .
By binomial expansion, .
Since is a multiple of , all terms from the second onward vanish modulo .
Thus each pair simplifies to .
Summing both pairs: .
Notice that , so , meaning .
Writing , we get .
Since is odd, , so the remainder is .
Study this concept with interactive practice in PrepSoc.
Open the concept library