Remainder theorem is a very important topic in number system and can be learnt easily. We will try to learn some interesting concepts regarding remainders with examples. Here we go!
Definition of remainder
If a and d are natural numbers, with d # 0, it can be proved that there exist unique integers q and r, such that a = qd + r and 0 ≤ r < d. The number q is called the quotient, while r is called the remainder. Dividend = Divisor × Quotient + Remainder. |
if r = 0 then we say that a is perfectly divisible by d or d is a factor of a. For example, we say 8 is a factor of 40 because 40 leaves a remainder 0 with 8.
By definition remainder cannot be negative. |
Now just to give an example, 17 = 3 * 5 + 2, which means 17 when divided by 5 will give 2 as remainder. Well that was simple!
Find Remainder[ (12 * 13 * 14) / 5 ]
Remainder [ (12 * 13 * 14) / 5 ]
= Remainder [2184/5] = 4. But this method is not the right one for us :)
In order to find the remainder of an expression find the individual remainder and replace each term with the respective remainders. Eg: Remainder[(100 + 30 * 4 - 8) / 7] = Remainder[(Remainder[100/7] + Remainder[30/7] * Remainder[4/7] - Remainder[8/7] ) / 7 ] = Remainder[(2 + 2 * 4 - 1)/7] = Remainder[9/7] = 2 |
In the above case 12, 13 and 14 will give remainders 2, 3 and 4 respectively when divided by 5. So replace them with the respective remainders in the expression and find the remainder again.
Remainder [ (12 * 13 * 14) / 5 ] = Remainder[(2 * 3 * 4) / 5] = Remainder[ 24 / 5 ] = 4.
Note:
One common mistake while dealing with remainders is when we have common factors in both dividend and divisor. Example, what is the remainder when 15 is divided by 9
15 / 9 is same as 5 / 3, remainder 2. Correct? No 15/9 will give a remainder of 6.
Where we slipped?
Always remember that if we find remainder after cancelling common terms make sure we multiply the remainder obtained with the common factors we removed.
In previous case we will get correct answer (6) when we multiply the remainder obtained (2) with the common factor we removed (3).
What is the remainder of 1421 * 1423 * 1425 when divided by 12 ? ( CAT 2000 )
1421, 1423 and 1425 gives 5, 7 and 9 as remainders respectively when divided by 12.
Remainder [ (1421 * 1423 * 1425 ) / 12 ] = Remainder [ (5 * 7 * 9) ] / 12, gives a remainder of 3.
Find the reminder when 1! + 2! + 3! + . . . . .. . .. 99! + 100! is divided by the product of first 7 natural numbers
From 7! the remainder will be zero. Why ? because 7! is nothing but product of first 7 natural numbers and all factorial after that will have 7! as one of the factor. so we are concerned only factorials till 7!, i.e, 1! + 2! + 3! + 4! + 5! + 6!
1! + 2! + 3! + 4! + 5! + 6! = 873 and as 7! > 873 our remainder will be 873
What is the remainder when 64^{999 }is divided by 7? (GMAT Type Question)
Many of us get intimidated with such numbers, always remember that the key to crack quant is a strong hold of basic concepts.
Remainder [64^{999 }/ 7 ] = Remainder[ 64 * 64 * …. 64 (999 times) / 7 ]
Remainder[64/7] = 1, hence Remainder [64^{999 }/ 7 ] = Remainder [ 1 ^{999 }/ 7 ] = 1
What is the remainder when 444^{444}^{ ^ 444} is divided by 7 ? (GMAT Type Question)
Remainder[444/7] = 3
Remainder[ 444 ^{444 ^ 444 }/ 7 ] = Remainder [ 3 ^{444 ^ 444 }/ 7 ]
= Remainder [ ( 3^{2 }) ^{222 ^ 444 }/ 7 ] = Remainder [ 2^{222 ^ 444 }/ 7 ] ( As Remainder [ 3^{2 }/ 7 ] = 2 )
= Remainder [ ( 2^{3} ) ^{74 ^ 444 }/ 7] = Remainder [ 1 ^{74 ^ 444 }/ 7 ] = 1 ( As Remainder [ 2^{3 }/ 7 ] = 1 )
Concept of negative remainder
We saw earlier that by definition remainder cannot be negative. But considering negative remainder is a very useful exam trick.
For example,
What is the remainder when 2^{11} divided by 3?
The easiest method for this one will be using the concept of negative remainders.
Here 2 when divided by 3 gives a remainder of -1. (Say)
2 = 3 * 1 + (-1), remainder is -1, which is theoretically incorrect but let’s cheat!
So we are asked to find (-1) * (-1) * … 11 times divided by 3.
Which is Remainder[-1/3] = -1.
Whenever you are getting negative number as a remainder, make it positive by adding the divisor to the negative remainder. |
Here required answer is 3 + (-1) = 2.
Remainder when (41 * 42) is divided by 43
Use negative remainder concept,
Remainder [ 41 * 42 / 13 ] = Remainder[(-2) * (-1) / 43 ]( as 41 = 43 * 1 – 2 and 42 = 43 * 1 – 1)
= Remainder [ 2 /43 ] = 2 (here we got a positive remainder itself, so no need of correction)
Some useful concepts while dealing with remainder are given below.
Remainder[(ax + 1)^{n }/ a] = 1 for all values of n. |
Find the remainder when 100^{99 }is divided by 11
Remainder[100^{99 }/ 11 ] = Remainder[(11* 9 + 1)^{99 }/ 11] = 1.
Remainder[(ax - 1)^{n }/ a ] = 1 when n is even Remainder[(ax - 1)^{n }/ a ] = (a-1) when n is odd. |
Find the remainder when 21^{875 }is divided by 17.
Remainder[21 / 17] = 4, so we need to find Remainder[4^{875}/ 17]
4^{2 }= 16 = (17 – 1), we can write the expression as Remainder[(4^{2})^{437 }* 4 / 17]
= Remainder[(17 – 1)^{437 }* 4 / 17] = Remainder[(17-1) * 4 / 17] = Remainder[64 / 17] = 13.
Remainder[(a^{n }+ b^{n}) / (a + b) ] = 0 when n is odd. |
Remainder[(2^{101 }+ 3^{101}) / 5 ] = 0
What is the remainder when 15^{23 }+ 23^{23 }is divided by 19 ? ( CAT 2004 )
15^{23 }+ 23^{23 }is divisible by 15 + 23 = 38 ( as 23 is odd).
So Rem[(15^{23 }+ 23^{23})/19] = 0
Remainder[(a^{n }+ b^{n} + c^{n} + ...) / (a + b + c + ...) ] = 0 if ( a + b + c + ... are in Arithmetic progression and n is odd |
What is the remainder when 16^{3 }+ 17^{3 }+ 18^{3 }+ 19^{3} is divided by 70 ? ( CAT 2005 )
Apply the above funda. Here n =3 ( odd ), 16 + 17 + 18 + 19 = 70 and 16,17,18 and 19 are in AP. Remainder is 0
Remainder[(a^{n }- b^{n}) / (a + b) ] = 0 when n is even. |
Remainder[(5^{100 }– 2^{100}) / 7] = 0
Remainder [(a^{n }- b^{n}) / (a - b) ] = 0 |
Now we can say Remainder[(101^{75 }– 76^{75}) / 25] = 0 in no time..!
The remainder when f(x) = a + bx + cx^{2}+ dx^{3}+ … is divided by (x-a) is f(a) |
Rem [(3x^{2 }+ 4x + 1) / (x-2)] = f(2) = 3 * 2^{2 }+ 4 * 2 + 1 = 21
Divide and Conquer
We will now learn another important concept, divisibility check of numbers. These concepts will be used extensively during prime factorization, while calculating HCF/LCM and also in finding remainders. Here we will just focus on how we can easily check whether a given number is divisible by some common divisors or not.
We will start with the most important one in the list
Any digit repeated ( P - 1 ) times is divisible by P, where P is a prime > 5 |
Find the remainder when 7777.... (100 digits) is divided by 13
We know Remainder[777... 96 digits ( 12 * 8 ) / 13 ] = 0
so Remainder [ 777... 100 digits / 13 ] = Remainder [ 7777 ( remaining 4 digits) / 13 ] = 3
Now we will see some other rules which most of you are already famililar with
Divisible by 2: If the last digit is divisible by 2.
12, 142, 68…
Divisible by 4: If the last 2 digits are divisible by 4.
724, Last 2 digits (24) gives a number divisible by 4.
Divisible by 8: If the last 3 digits are divisible by 8.
1040, Last 3 digits (040) gives a number divisible by 8.
Got the pattern ?
A number is divisible by 2^{n }if the last n digits are divisible by 2^{n} |
Divisible by 3: Sum of digits of the number is divisible by 3.
15672, sum of digits = 1+5+6+7+2 = 21 = 3 * 7, hence divisible by 3.
Divisible by 9: If the sum of the digits is divisible by 9
972036, sum of the digits = 9 + 7 + 2 + 0 + 3 + 6 = 27, divisible by 9.
Why this is true ? Let the number be ab, where a and b are the digits. We know ab = 10a + b = 9a + (a+b). So ab is divisible by 3 (or 9) if (a+b) is divisible by 3 (or 9) :)
Divisible by 33, 333, 3333… & 99, 999, 9999…
To check a given number is divisible by 333…3 (n digits) just see whether the sum of digits taken n at a time from right to left is divisible by 333…3 (n digits). If yes then the original number is also divisible by 33…3 (n digits) Same can be applied for checking the divisibility of a given number with 99…9 (n digits). Check if the sum of digits taken n at a time from right is divisible by 999…9 (n digits). If yes then the original number is also divisible by 99…9 (n digits) |
It is easy to understand through examples.
Is 627 divisible by 33 ?
Take 2 digits from right at a time, and get the sum.
27 + 06 = 33, hence divisible by 33
Is 22977 divisible by 333 ?
Take 3 digits from right at a time and find the sum.
977 + 022 = 999, hence divisible by 333
Is 6435 divisible by 99 ?
35 + 64 = 99. As per the above rule, 6435 is divisible by 99.
How much time you need to tell whether the number 1000000998 is divisible by 999 ?
Divisible by 5: If the last digit is 5 or 0.
E.g. 625, 310 etc…
Divisible by 25: If the last two digits are divisible by 25
Eg: 125, 50 etc..
Divisible by 125: If the last three digits are divisible by 125
Eg: 1250, 3500 etc..
A number is divisible by 5^{n }if the last n digits are divisible by 5^{n} |
Divisible by 7: Subtract twice the unit digit from the remaining number.
If the result is divisible by 7, the original number is.
14238, 1423 - 2 * 8 = 1407 = 201 * 7, hence divisible by 7
Divisible by 11: If the difference between the sum of digits at the odd place and the sum of digits at the even place is zero or divisible by 11.
1639, (9+6) - (3+1) = 11, divisible by 11
What is the remainder when 10^{5 }- 560 is divided by 11 ?
10^{5 }- 560 = 99440
(0 + 4 + 9 ) - ( 4 + 9 ) = 0 => divisible by 11. so Remainder[(10^{5 }- 560) / 11] = 0
Divisible by 101: Mark off the number in groups of two digits starting from the right, and add the two-digit groups together with alternating signs. If the sum is divisible by 101 then the original number is also divisible by 101.
Eg: 4512276, (76 + 51) - (22 + 4) = 101, hence divisible by 101.
Divisible by 1001: Mark off the number in groups of three digits starting from the right, and add the three-digit groups together with alternating signs. If the sum is divisible by 1001 then the original number is also divisible by 1001.
Eg: 9533524, (524 + 9 ) - 533 = 0, hence divisible by 1001.
Divisible by 10^{n }+ 1 : Mark off the number in groups of n digits starting from the right, and add the n-digit groups together with alternating signs. If the sum is divisible by 10^{n} + 1 then the original number is also divisible by 10^{n} + 1. |
Divisible by 13: If the difference of the number of its thousands and the remainder of its division by 1000 is divisible by 13.
2184, 2 - 184 = -182, so divisible by 13.
Divisible by 111: Add the digits in block of 3 from right to left. The numer is divisible by 101 if the sum is a multiple of 111 or is zero.
12659328 = 328 + 659 + 12 = 999 = 111 * 9, divisible by 111
To check divisibility by a number, check divisibility by highest power of each of its prime factors. |
Eg: To check for the divisibility by 24, check for divisibility by 2^{3} and 3 as 24 = 2^{3} * 3
72 is divisible by 24 as 72 is divisible by 8 and 3.
Another important one for you is a generic method
To test for divisibility by a number ( say D ), where D ends in 1, 3, 7, or 9 : Step 1: Find any multiple of D ending in 9. (If D ends in 1, 3, 7, or 9, then multiply by 9, 3, 7, or 1 respectively) Step 2: Find m by adding 1 and divide by 10 Step 3: Then a number N = 10t + q is divisible by D if and only if mq + t is divisible by D. |
Eg: Find the remainder when 1054 is divided by 17
Step 1 : 17 * 7 = 119
Step 2 : m = (119 + 1) / 10 = 12
1054 = 10 * 105 + 4, t = 105 and q =4
mq + t = 48 + 105 = 153 = 17 * 9, Remainder[1054/17] = 0
OK! So we got some neat tricks. But how are we going to engage them to find the remainders. Again, we will learn from some examples.
What is the remainder when 2111756 is divided by 8 ?
We know the divisibility check for 8. Just find the remainder of the number formed from the last three digits with 8. That is our answer.
Remainder [ 2111756 / 8 ] = Remainder [ 756 / 8 ] = 4
What is the remainder when 2345987572219134 is divided by 9 ?
We know the sum of the digits should be a multiple of 9. Here just find the remainder of the sum of the digits with 9.
Remainder [ 2345987572219136 / 9 ] = Remainder [ sum of the digits / 9 ] = 2
Cyclic property of remainders
Sometimes it is easy to find the remainder by using the cyclic property of remainders, remainders forming a pattern.
As a thumb rule if we divide p^{n }with q, the remainder will follow a pattern. |
For example,
Remainder [ 2^{1 }/ 3 ] = 2, Remainder [ 2^{2} / 3 ] = 1, Remainder [ 2^{3 }/ 3 ] = 2, Remainder [ 2^{4 }/ 3 ] = 1 and so on.
Pattern repeats in cycles of 2. Remainder [ 2^{n }/ 3 ] = 2 when n is odd and 1 when n is even.
With this information, we can find Remainder [ 2^{3276 }/ 3 ] = 1 very quickly.
One more, Remainder [ 9^{1} / 11 ] = 9, Remainder [ 9^{2} / 11 ] = 4, Remainder [ 9^{3} / 11 ] = 3 , Remainder [ 9^{4} / 11 ] = 5
Remainder [ 9^{5} / 11 ] = 1, Remainder [ 9^{6} / 11 ] = 9, Remainder [ 9^{7} / 11 ] = 4, Remainder [ 9^{8} / 11 ] = 3
Pattern repeats in cycles of 5. So if we are asked to find Remainder [ 9^{100 }/ 11 ]， we know it is 1. (100 is in the form 5n and we know remainder for 5 is 1.. cool right ?)
Note:
Remainder [9^{3}/11] = Remainder [Remainder [9^{2}/11] * Remainder [9^{2}/11] ) / 11] = Remainder [ 4 * 9 / 11] = 3.
This funda comes very handy in scenarios like this. Like we dont have to solve Rem [9^{8 }/11] because we already know Rem[9^{4 }/11] as 5..
Rem [9^{8 }/11] = Remainder [ 9^{4 }* 9^{4 }/11 ] = Remainder [ (5 * 5) / 11 ] = 3
Also, Remainder [9^{7 }/11] = Remainder [9^{3 }* 9^{4 }/ 11 ] = Remainder [ ( 3 * 5 ) / 11 ] = 4 ( as Rem [9^{3 }/11] = 3 and Rem [9^{4 }/11] = 5 )
What is the remainder when 7^{100 }is divided by 4?
Remainder[ 7^{1 }/ 4 ] = 3, Remainder[ 7^{2 }/ 4 ] = 1, Remainder[ 7^{3 }/ 4 ] = 3, Remainder[ 7^{4 }/ 4 ] = 1 and so on...
Pattern repeats in cycles of 2. Remainder [ 7^{n }/ 4 ] is 3 when n is odd and is 1 when n is even.
7^{100 }when divided by 4 gives a remainder of 1.
(Same can be solved using other methods also)
Find the remainder when 3^{99^99} is divided by 7
Find the pattern of remainder when 3^{n }is divided by 7.
Remainder [ 3^{1 }/ 7 ] = 3, Remainder [ 3^{2 }/ 7 ] = 2
Remainder [ 3^{3 }/ 7 ] = 6 (Don’t calculate Rem[3^{3}/7] we already have Rem[3^{1}/7] & Rem[3^{2}/7])
Remainder [ 3^{4 }/ 7 ] = 4 (using Rem[3^{2}/7])
Remainder [ 3^{5 }/ 7 ] = 5 (using Rem[3^{3}/7] and Rem[3^{2}/7] )
Remainder [ 3^{6 }/ 7 ] = 1 (using Rem[3^{3}/7])
Remainder [ 3^{7 }/ 7 ] = 3 (using Rem[3^{3}/7] and Rem[3^{4}/7] )
Remainder [ 3^{8 }/ 7 ] = 2 (using Rem[3^{4}/7])
Pattern repeats in cycles of 6. (We can do this easily from Euler’s theorem, as φ(7) = 6, hence Remainder [3^{6}/7] = 1. Explained just to get the idea of patterns in remainders)
Now our task is to find Remainder [ 99^{99}/ 6 ]
Remainder [99^{99}/6] = Remainder [3^{99}/6]
Remainder [ 3^{1} / 6 ] = 3, Remainder [ 3^{2} /6 ] = 3, Remainder [ 3^{3} / 6 ] = 3 and so on..!
Hence 99^{99 }can be written as 6n + 3.
Remainder [ 3^{99^99 }/ 7 ] = Remainder [ 3^{(6n + 3)}/ 7 ]
we have found out the pattern of 3 divided by 7 repeats in cycles of 6. So we need to find the Remainder [ 3^{3} / 7 ] to get the answer which is equal to 6
Euler’s Remainder Theorem
We say two numbers ( say a and b ) are co-prime to each other when HCF(a,b) = 1, i.e, no divisor divide both of them completely at the same time.
Eg: 21 and 8 are co primes because they don't have any common factors except 1
In number theory, Euler's totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. |
Take n = 9, then 1, 2, 4, 5, 7 and 8, are relatively prime to 9. Therefore, φ(9) = 6.
How to find Euler’s totient?
Say n = P_{1}^{a }x P_{2}^{b }x P_{3}^{c }x ... ( where P_{1} P_{2}, P_{3} ... are prime factors of n ) φ(n) = n x (1 - 1/P_{1}) x (1 - 1/P_{2}) x (1 - 1/P_{3}) x .... If n is prime then φ(n) = n - 1 |
φ(100) = 100 x (1-1 / 2) x (1- 1 / 5) = 100 x 1 / 2 x 4 / 5 = 40
φ(9) = 9 x (1 – 1/3) = 6
Euler’s Remainder theorem states that for co prime numbers M and N, Remainder [M^{φ}^{(N) }/ N] = 1 Always check whether the numbers are co primes are not. Euler’s theorem is applicable only for co prime numbers |
What is the remainder when 21^{865 }is divided by 17
Remainder[21/17] = 4
Remainder [ 21^{865}/ 17 ] = Remainder [ 4^{865}/ 17 ]
4 and 17 are co prime numbers. ( A prime number is always coprime to any other number)
φ(17) = 17 x ( 1 – 1 / 17) = 16.
So Euler’s theorem says Remainder [ 4^{16}/ 17 ] = 1
To use this result in the given problem we need to write 865 in 16n + r form.
865 = 16 * 54 + 1, so 4^{865 }can be written as 4^{16 * 54 }x 4
Remainder[4^{865}/17] = Remainder[ 4^{16*54}/17] * Remainder[4/17] = 1 * 4 = 4
What is the remainder when 99^{999999 }is divided by 23
Remainder[99/23] = 7
Remainder[99^{999999}/23] = Remainder[7^{999999}/23]
7 and 23 are co prime numbers
Here 23 is prime, so φ(23) = 22
So by applying Euler's theorem we can say that Remainder[7^{22}/23] = 1
In order to use this result in our problem we need to write 999999 in 22n + r form. Before rushing into dividing 999999 by 22, just think whether we have any better way to do that. We know, 999999 = 22n + r , 0 ≤ r < 22. 999999 is divisible by 11 and so is 22. which means r is also a multiple of 11. Only numbers which are less than 22 and is a multiple of 11 is 11 and 0. But as 999999 is odd and 22n is even, r should be odd. so r = 11. Saved our time right ? ;)
999999 = 22n + 11
Remainder[7^{999999}/23] = Remainder[7^{22n}/23] * Remainder[7^{11}/23] = 1 * Remainder[7^{11}/23] = Remainder[7^{2 }* ^{5 }* 7/23]
= Remainder[ 3^{5} * 7/23] ( as Remainder[7^{2}/23] = 3 )
= Remainder[3^{3 }* 3^{2 }* 7/23] = Remainder[4 * 9 * 7/23] = Remainder[28 * 9/23] = Remainder[45/23] = 22
Find the remainder when 97 ^{97 ^ 97 }is divided by 11
Remainder [97/11] = 9
So, Remainder [97^{97^97}/11] = Remainder [9^{ 97^97}/11]
From Euler’s theorem, Remainder [9^{10}/11] = 1
97 and 10 are again co primes. So φ(10) = 10 (1-1/2) (1-1/5) = 4
Remainder [97^{4}/11] = 1
97 = 4n + 1, So Remainder [97^{97}/11] = Remainder [97/10] = 7
Means 97^{97 }can be written as 10n + 7
Now our original question,
Remainder [9^{97^97}/11] = Remainder [9^{10n+7}/11] = Remainder [9^{7}/11] = 4 :)
Fermat’s little theorem
Euler’s theorem says that if p is a prime numberand a and p are co-primes then a^{φ}^{(p) }/ p always gives a remainder of 1.
Now we know for any prime number p, φ(p) = p - 1
Remainder of a^{( p – 1 )}/ p is 1, which is Fermat’s little theorem |
We can derive other useful results like
- Remainder of a^{p }/ p is a.
- (a^{p }– a) is always divisible by a.
Wilson’s theorem
Remainder[(p-1)! / p ] = (p-1), if p is a prime number. |
We can also derive some useful results like
- Remainder of [(p-1)! + 1] / p is zero.
- Remainder of (p-2)! / p is 1.
Example:
Remainder of [22!/23] = 22
Remainder of [21!/23] = 1
I hope the explanations are clear are correct. Please let me know if any concepts regarding remainders are missed out or incase of any errors.. Happy learning :)
Comments
Very useful Sir. thank you
Very useful Sir. thank you very much.
Really helpful.
Really helpful.
Superb Article ! Very Helpful
Superb Article ! Very Helpful !! Thankyou :)
Can any 1 plz help me.. When
Can any 1 plz help me.. When x is divided by 13 it gives 12 as d remainder,what is the remainder whem x^13 is divided by 13 ?
remainder will be 12 itself.
remainder will be 12 itself.
as the euler number of 13 is 12 , (x^12)/13 will give remainder as 1. And whats remaining will be x/13 and it will give you remainder = 12 as said in question.
thank you for the article..
thank you for the article...
please check the examples given in wilsons theoram ( 51 is not prime) and the remainder of 50!/51 is zero.
also the remainder in 49!/51 is also zero.
Corrected. Thanks :)
Corrected. Thanks :)
The example used for
The example used for divisibility by 7, seems wrong.14328 is not divisible by 7.An alternate approach for divisibility by 7( or13) can be as follows :Let the number be abcdefghi, make the set of three digits from left to right, if the difference between the sum of even sets and odd sets is 0 or multiple of 7 (or 13 ) , then the number is divisible by 7 else not.eg : (ghi + abc ) - ( def + 000 ) = 7n or 0.let the number be 29088276We make the group of three as said above : 029,088,276N1= 029 + 276 = 305N2=88D = N1 - N2 = 305 - 88 = 217.We can see that D is divisible by 7. Hence the original number is divisible by 7.
Hi Hitesh, the method is
Hi Hitesh, the method is correct but a typo created the confusion ( used 1423 instead of 1432). Thanks for pointing out!
From combining wilson's
From combining wilson's theorem and Euler's theorem you can also find a new result that,
if p is prime number and n>p, then
(p-1)!n!+1 will give a remainder of 2 when divided by p
Remainder[(P-1)!n!+1]/P is 2 for all values of n except 1 for which the remainder will be zero.
Nicely explained to
Nicely explained to understand for anyone
Satadal
How do we solve (42^442) /
How do we solve (42^442) / 100 and (9876543298765432...82 digits) / 34 ?