Remainder theorem is one of the most important and frequently tested topics in quantitative aptitude and number theory for competitive exams. It is asked in almost every major exam including SSC CGL, SSC CHSL, Bank PO, Bank Clerk, Railway RRB, CAT and UPSC CSAT. This topic is also important for AMCAT, eLitmus, TCS NQT and all campus placement aptitude tests. A strong understanding of remainder theorem concept, negative remainder method, Fermat theorem, Euler theorem, Wilson theorem and Chinese remainder theorem is essential for scoring well in these exams. In this post we cover everything from basic positive and negative remainder concept, division shortcuts for 2 3 4 5 6 7 8 9 and 11, simplification of complex remainder problems, Fermat theorem, Euler theorem, Wilson theorem, Chinese remainder theorem and algebraic remainder theorem — all explained with solved examples.
Remainder Theorem:
i.e. Sum of numerical values (ignoring sign) of positive remainder and negative remainder is equal to value of divisor.
Ex:- A number when divided by 13 gives – 4 as negative remainder. What will be the actual or positive remainder.
Sol:- actual remainder = 13 – 4 = +9
Ex:- A number when divided by 13 gives +4 as positive remainder. What will be the negative remainder.
Sol:- Negative remainder numerical value = 13 – 4 = 9
∴ Negative remainder = – 9
⟶ negative remainder is used as a concept to make calcultation easier otherwise positive remainder is the valid remainder
● Remainer of any number is less than the divisor.
Ex:- Remaninder of 5 can be 0, 1, 2, 3, or 4 not 5 or more than 5
Remainder of 7 can be 0, 1, 2, 3, 4, 5, or 6 not 7 or more than 7.
● Divide a number by 10 and find its remainder which will give its unit digit (last digit)
● Divide a number by 100 and find its remainder which will give its last two digits.
If remainder is single digit add ‘0’ before it.
● Given a fraction \(\frac{a}{b}\), if we simplify it by a factor of k i.e. \(\frac{{\frac{a}{k}}}{{\frac{b}{k}}} = \frac{c}{d}\) and remainder of \(\frac{c}{d}\) comes out to be R then remainder of \(\frac{a}{b}\) will be k.R
(Q). Find the remainder of \(\frac{{596}}{{15}}\) .
Sol:- By quick observation we find that 600 is divisible by 15 and 596 is near to 600.
∴ remainder = -4 = 15-4 = 11 Answer
(Q). Find the remainder of \(\frac{{674}}{{68}}\)
Sol:- By quick observation we find that 680 is divisible by 68 and is also near to 674
∴ remainder = -6 = 68 – 6 = 62 Answer
(Q). Find the remainder of
\(\frac{{14979 \times 455 \times 53 \times 72 \times 29}}{{100}}\)
⟶ Division by 2 ⟹ If Uₔ is even then 0
If Uₔ is odd then 1
⟶ Division by 3 ⟹ discard all digits which are multiple of 3 or their sum is multiple of 3 and take the remainder of sum of remaining digits.
Ex:- Find the remainder of \(\frac{{87005309476}}{3}\)
Sol:-
Ex:- Find the remainder of \(\frac{{9876545321}}{3}\)
Sol:-
⟶ Division by 4 ⟹ Take remainder of last two digits
Ex:- \(\frac{{98370568973}}{4}\)
Remainder = Remainder of \(\frac{{73}}{4}\) = 1 Answer
⟶ Division by 5 ⟹ If last digit is 0 or 5 then remainder is 0 else divide last digit by 5 and take remainder
Ex:- (\frac{{98370568973}}{5}\)
Sol:- Uₔ = 3 ∴ Remainder = \(\frac{3}{5}\) = 3 Answer
⟶ Division by 6 ⟹ Multiply the sum of all digits except unit digit by 4, then add the unit digit to this sum and divide this sum by 6 and take remainder.
Ex:- \(\frac{{98037568973}}{6}\)
Sol:- Remainder of \(\frac{{(9 + 8 + 0 + 3 + 7 + 5 + 6 + 8 + 9 + 7) \times 4 + 3}}{6}\)
\(\frac{{ – 1}}{6}\)
= – 1
= 6 – 1
= 5 Answer
Ex:- Find the remainder of \(\frac{{375263908216}}{6}\)
Sol:-
⟶ Division by 4 ⟹ ● Break the number into groups of three from right and calculate remainder of these each term.
● Take the alternating sum of remainders
● Find the remainder of this alternating sum to get the final result.
Ex:- Find remainder when 88643258169436 is divided by 7.
Sol:-
= 4 – (-1) + (-1) – (+1) + 2 = 5 Answer
⟶ Division by 6 ⟹ Take remainder of last three digits that will give the result
Ex:- Find remainder when 8843258169436 is divided by 8
Sol:- Required remainder = remainder of \(\frac{{436}}{8}\) = 4 Answer
⟶ Division by 9 ⟹ Discard all digit which are 9 and also discard all digits of which sum is a multiple of 9 and take sum of remaining digits. Find the remainder of this sum to get the final result.
Ex:- Find remainder when 8843258169442 divided by 9.
Sol:-
⟶ Division by 11 ⟹ Remainder of differece of sum of digits at alternating place
Ex:- Find remainder of 8843258169447 when divided by 11.
Sol:-
Fermat’s Theorem:-
\(\frac{{{a^{p – 1}}}}{p}\) where p is a prime number & (a, p) are co-prime then remainder is 1
Chinese Remainder Theorem:-
\(\frac{N}{{x \times y}}\) where (x,y) are co-prime
then \(\begin{array}{l}
{\mathop{\rm Re}\nolimits} m\left( {\frac{N}{x}} \right) \to a\\
\& {\mathop{\rm Re}\nolimits} m\left( {\frac{N}{y}} \right) \to b
\end{array}\)
The final remainder is smallest number which when divided by x, it leaves remainder a and when divided by y it leaves remainder b.
(Q). Find the last two digit of \({49^{49}}\)
Sol:- Last two digit = Remainder of \(\frac{{{{49}^{49}}}}{{100}}\)
Wilson Theorem:-
\({\mathop{\rm Re}\nolimits} m\frac{{\left( {p – 1} \right)!}}{p} = p – 1\) where p is a prime number
Ex:- Find remainder of \(\frac{{28!}}{{29}}\)
Sol:- Remainder = 28 Answer
Euler Theorem:-
⟶ way to find Euler totient function
● If n is a prime number ⟹ Φ(n) = n – 1
● If n is a power of a prime number ⟹ Φ(pᵏ) = pᵏ – pᵏ⁻¹
● multiplicative property ⟹ If a and b are co-prime, then Φ(a.b) = Φ(a).Φ(b)
● Φ(1) = 1
Ex:-
Φ(1) = 1
Φ(2) = 2 – 1 = 1
Φ(3) = 3 – 1 = 2
Φ(4) = Φ(2²) = 2² – 2 = 2
Φ(4) = Φ(2×2) = Φ(2)×Φ(2) = 1 × 1 = 1 ❌ Wrong
Φ(5) = 5 – 1 = 4
Φ(6) = Φ(2 × 3) = Φ(2) : Φ(3) = (2 – 1)(3 – 1) = 2
Φ(3⁵) = 3⁵ – 3⁴ = 162
Ex:- Find the remainder when 3¹⁰⁰ is divided by 7.
Sol:-
Φ(7) = 7 – 1 = 6
by Euler’s theorem
\(\frac{{{3^{\varphi (7)}}}}{7}\) ⟶ Remainder = 1
\(\frac{{{3^6}}}{7}\) ⟹ Remainder = 1
We need to find remainder of \(\frac{{{3^{100}}}}{7}\)
Ex:- Find the remainder when 7²⁰ is divided by 21.
Sol:-
Φ(21) = Φ(3×7) = (3 – 1)(7 – 1) = 12
∴ \(\frac{{{7^{12}}}}{{21}}\) ⟹ Remainder = 1
To find: Remainder of \(\frac{{{7^{20}}}}{{21}}\)
(Q). Find the remainder when \({32^{{{32}^{32}}}}\) is div
ided by 7.
Sol:-
Φ(7) = 7 – 1 = 6
7 and 32 are co-prime
∴ by Euler’s theorem
\(\frac{{{{32}^{\varphi (n)}}}}{7}\) ⟶ 1 (Remainder)
\(\frac{{{{32}^6}}}{7}\) ⟶ 1
To find: \(\frac{{{{32}^{{{32}^{32}}}}}}{7}\) ⟶ Remainder
So we need to write 32³² as 6Q + R
i.e. we need to find remainder when 32³² is divided by 6.
(Q). Find the remainder when \({27^{{{28}^{29}}}}\) is div
ided by 16.
Sol:-
27 & 16 are co-prime.
Φ(16) = 2⁴ – 2³ = 8
∴ by Euler’s theorem
\(\frac{{{{27}^8}}}{{16}}\) ⟶ 1 (Remainder)
To find: \(\frac{{{{27}^{{{28}^{29}}}}}}{16}\) ⟶ Remainder
So we need to write 28²⁹ in the form 8Q + R & for this find remainder R when 28²⁹ is divided by 8.
● Algebric Remainder Theorem:-
put denominator = 0
ax + b = 0
x = \(\frac{{ – b}}{a}\) ⟶ put this value in numerator which will give remainder as a result.
Ex:- Find remainder when 2x² + 3x + 5 is divided by x – 5.
Sol:-
x – 5 = 0 ⟹ x = 5
put this value in expression:
2×(5)² + 3×5 + 5 = 70 Answer
Ex:- Is (x – 4) a factor of polynomial x² – 3x – 4
Sol:-
put x = 4 in polynomial
4×4 – 3×4 – 4 = 0
Since result is 0 ⟹ (x – 4) is a factor of given polynomial. Answer
● Concept:- 10ⁿ is divided by 6, we always get remainder 4, where n is a natural number.
Ex:- Find the remainder when 10¹ + 10² + 10³ + …………… + 10¹⁰⁰ is divided by 6.
Sol:-
\(\frac{{{{10}^1} + {{10}^2} + {{10}^3} + {{10}^4} + {{……….10}^{100}}}}{6}\)
=\(\frac{{4 \times 100}}{6} = \frac{{4 \times 4}}{6}\) = 4 Answer
● Concept:- If a number is formed by repeating any digit 6 times or a multiple of 6 times then the number is divisible by 3, 7, 11, 13, 37, 39.
Ex:-
111111 ⟶ divisible by 3, 7, 11, 13, 37, 39
999999 ⟶ divisible by 3, 7, 11, 13, 37, 39
(Q). Find the remainder when 5555……..262 times is divided by 37.
Sol:-
\(\frac{{262}}{6} \Rightarrow {\mathop{\rm Re}\nolimits} mainder = 4\)
∴ Remainder of \(\frac{{555…….262times}}{{37}} = {\mathop{\rm Re}\nolimits} m.Of\frac{{5555}}{{37}}\) = 5 Answer
(Q). Find the remainder when 9999…….674 times is divided by 13.
Sol:-