Basic concepts of Remainders  Kamal Lohia

What is the remainder when 2007 is divided by divided by 7?
It is simple; just divide 2007 by 7 to get the remainder as 5.
Did anybody use any shortcut in this?
I'll tell you later :)
Another simple one:
What is the remainder when 2008 is divided by 7?
Now it is smarter to use the earlier known data from previous question.
If 2007 = 7a + 5
Then certainly 2008 = 2007 + 1 = 7a + 5 + 1 = 7a + 6.
Ok. Next one.
What is the remainder when 2007 × 2008 is divided by 7?
It is simply (5 × 6) = 2 mod 7.
Most of you use it some knowingly and some unknowingly too.
Funda is simple: Remainders of product of some numbers is obtained by product of individual remainders of the number with same divisor.
As 2007 = 7a + 5 and 2008 = 7a + 6
So 2007 × 2008 = (7a + 5)(7a + 6) = (7a)^{2 }+ (5 + 6)7a + 5 × 6 = 5 × 6 mod 7 = 2 mod 7.
Question was simple but important learning is as said above that "Remainder of Product of some number depends on Product of their individual Remainders with same divisor."
One more thing to tell (for those who are unaware of the 'alien' phrase MOD):
When I say 31 = 3 mod 7, that mean 31 is a number of the form 7a + 3 OR in other words, we can also say 31 leaves remainder 3 when divided by 7. So just to avoid this long sentence every time, we use this internationally used term 'mod'. I hope it'll trouble you no more throughout the session.
Li'l advanced:
What is the remainder when (2007 × 2007 × 2007.... 2007 times) (2008 × 2008 × 2008....2008 times) is divided by 7?
It is equivalent to (2007^{2007}) (2008^{2008}) mod 7 = (5^{2007}) (6^{2008}) mod 7.
Now observe that 5 mod 7 = 2 mod 7 and also 6 mod 7 = 1 mod 7.
Remember that term before 'mod' doesn't always give the remainder. It tell us only the form of the number. e.g. 5 mod 7 = 7a + 5 = 7a + 7  2 = 7(a + 1)  2 = 2 mod 7.
Hope you got it. Now observe one more thing that we can also write:
5 mod 7 = 2 mod 7 = 9 mod 7 = 16 mod 7 and also
5 mod 7 = 12 mod 7 = 19 mod 7 = 26 mod 7.
That means you can add/subtract the divisor any number of times from the number before 'mod' and it'll not change the form of the number.
You'll realize it's use later in the session.
Back to problem, we need to find {(2) ^{2007}} × {(1) ^{2008}} mod 7 = (2^{2007}) mod 7.
Further we see that 2^{3 }= 8 = 1 mod 7.
So (2^{2007}) mod 7 = (2^{3})^{669 }mod 7 = 1 mod 7 = 6 mod 7.
What is the remainder when 2007^{2008 ^ 2009 }is divided by 7?
We have seen from previous question that 2007 = 2 mod 7
So 2007^{ 2008^2009 }= (2)^{2008^2009 }mod 7 = (2^{2008^2009}) mod 7.
Also we saw that 2^{3 }= 1 mod 7. So we need to see whether the power of 2 (i.e. 2008^{2009 }here) is divisible by 3 or not.
That means we have a sub question in the original question that to find the remainder of 2008^{2009 }by 3.
Now 2008^{2009 }= 1^{2009 }mod 3 = 1 mod 3 (as 2008 = 1 mod 3)
Using this info in previous part, we get 2007^{2008^2009 }= (2^{{3k+1}}) mod 7 = 2 × (2^{3})^{k }mod 7 = 2 mod 7
Please read it slowly to grasp the logic completely.
EULER's Theorem and Euler's Totient Function
Now we know what remainder is and how to find it. But many of you might be thinking that in earlier questions we found 2^{3}= 1 mod 7 manually. What if the number is much larger and divisor is also larger number so that just by seeing, we cannot say anything specific.
So for your comfort, EULER made a theorem which says
M^{phi(N) }= 1 mod N
where HCF(M, N) = 1 and phi(N) = Euler's Totient Function = number of numbers less than N and coprime to N.
For those who don't know how to find phi(N), again EULER comes to rescue. So cheers. :)
If N = (a^{p}) × (b^{q}) × (c^{r})....where a, b, c are distinct primes and p, q, r are their respective powers
Then phi(N) = N(1  1/a)(1  1/b)(1  1/c)....
How many numbers less than 101 are coprime to 100?
It is simply phi(100) = 100(1  1/2)(1  1/5) = 40.
How many numbers less than 2100 are multiples of 3 but not multiple of 2, 5 and 7?
It is simply phi(700) = 700(1  1/2)(1  1/5)(1  1/7) = 240. Can you think why??
How many numbers less than 1200 are not divisible by 15 but divisible by 12?
It means number should be divisible by 3 and 4 but not by 5. So it is 1200(1/3)(1/4)(4/5) = 80.
Try to grasp what I have done.
This is a very simple logic that "Out of every three consecutive numbers, exactly one is divisible by 3 and two are not". Similarly "Out of every four consecutive numbers, exactly one is multiple of 4 and three are not" and so on. So just use it. But remember, there is one condition to abide by. If I am considering divisibility or nondivisibility by 2, 3, 5 (say), then my total number should be multiple of / divisible by 2, 3 and 5. Otherwise, you won't get the integral answer. And never try to be over smart by rounding offs or taking some nearest integer or something else.
how many of first 100 numbers are multiple of 2 and 5 but not of 3
First take a number nearest to 100 which is multiple of 2, 5 as well as 3 i.e. 90.
So till 90, we get the required numbers as (1/2)(1/5)(2/3)(90) = 6.
And after that we have 100 i.e. 1 more. So answer will be 7.
Another type of questions:
Find the sum of all the numbers less than 101 which are coprime to 100.
As we used the symmetry pattern of numbers in previous problem, that out of every 'n' consecutive numbers exactly 1 is divisible by n and remaining (n  1) are not. Similarly, here, when I remove the multiple of 2 or 5 from first 100 numbers, the remaining coprime numbers also depicting a pattern. Can you identify this?
See and try to learn the logic:
Among first 100 natural numbers, what is the pattern besides that each number is obtained by adding 1 to previous one?
There is one more (which is applicable to basically in all APs) , that sum of first and last is same as sum of second and secondlast and so on.
Similarly, when we have only 'coprime to 100' numbers left with us, which are 40 in number as calculated in F1, they also appear in such pattern that "sum of First and last is same as sum of second and secondlast and so on" And each of this sum is equal to 100.
Alternately, you can think of any two numbers less than 100 whose sum is 100.
x + y = 100.
So if x is multiple of 2, then y is also.
If x is not multiple of 2, then y also can't be multiple of 2.
Similarly, for 5 also.
That means if x is not multiple of 2 as well as 5 i.e. 2 is coprime to 100, then y is also coprime to 100.
That means for every coprime number less than 100, there is another which adds up to the previous one and make the sum 100.
So, answer for this question becomes 20 × 100 = 2000.
Similar one...
Find the sum of the numbers which are less than 2100 and are multiples of 3 but not multiple of 2, 5 and 7?
With same logic, it is 120*2100 = 252000.
Find the sum of the numbers which are less than 1200 and are not divisible by 15 but divisible by 12?
It's not a magic trick anymore. Answer is 40*1200 = 48000.
For how many values of n, phi (n) is odd? For example if n = 2, phi (2) = 1 is odd.
There are no more of such values. :)
Remainder Theorems
Fermat’s Theorem: M^{p }– M is divisible by p where p is a prime number and HCF(M, p) = 1
i.e. M^{p }= M mod p
For example: 2^{7 }– 2 is divisible by 7 or 2^{7 }= 2 mod 7.
Fermat’s Little Theorem: M^{p  1 }= 1 mod p where p is a prime number and HCF(M, p) = 1.
In later years, Euler generalize it for nonprimes also as
Euler’s Theorem: M^{phi(N) }= 1 mod N where phi(N) is Euler’s Totient function and HCF(M, N) = 1
We discussed Euler’s Totient Function already.
Let's use this to find remainders.
Find the remainder when 53^{54 }is divided by 19.
That’s easy one.
As HCF(53, 19) = 1, we can use Euler’s theorem or Fermat’s theorem as 19 is a prime number.
So we know that 53^{18 }= 1 mod 19
i.e. (53^{18}) (53^{18}) (53^{18}) = 53^{54 }= (1)(1)(1) mod 19 = 1 mod 19.
What should be added to 21^{22 }so that it is divisible by 23?
we know that 21^{22 }= 1 mod 23 as 23 is a prime number and HCF(21, 23) = 1. (Fermat’s Theorem)
So we must add 22 to the number to make it divisible by 23.
What are the last two digits of 79^{121}?
Don't worry, last two digits of a number is it's remainder only when it is divided by 100. That means you are to find the remainder of the number with 100.
As 100 and 79 are coprime, we can use Euler's th. Also phi(100) = 40.
So 79^{40 }= 1 mod 100
and 79^{121 }= 79 mod 100.
What if Number and divisor are not coprime i.e. HCF(M, N) is not equal to 1?
No issues: Just take the HCF of the number and divisor our and fond remainder of remaining number with remaining divisor.
Final answer will be HCF times the remainder obtained by remaining number and remaining divisor.
Find the remainder when 2^{32 }is divided by 32.
Don’t get bewildered by the trap. Answer is zero. :D
Find the remainder when 3^{12 }is divided by 12.
Now HCF of number and divisor is 3.
So the required remainder will be 3*[3^{11 }mod 4] = 3(1) mod 12 = 9 mod 12.
MOD  We talked something about the phrase/operation earlier also. Let’s repeat them and try to be more familiar with it. When I say 31 = 3 mod 7, that mean 31 is a number of the form 7a + 3 OR in other words, we can also say 31 leaves remainder 3 when divided by 7. So just to avoid this long sentence every time, we use this internationally used term 'mod'.
Remember that term before 'mod' doesn't always give the remainder. It tell us only the form of the number e.g. 5 mod 7 = 7a + 5 = 7a + 7  2 = 7(a + 1)  2 = 2 mod 7.
Hope you got it. Now observe one more thing that we can also write:
5 mod 7 = 2 mod 7 = 9 mod 7 = 16 mod 7 and also 5 mod 7 = 12 mod 7 = 19 mod 7 = 26 mod 7.
That means you can add/subtract the divisor any number of times from the number before 'mod' and it'll not change the form of the number.
Also if we say that 21N = 7 mod 8
That means 7*3N = 7*1 mod 8
Or 3N = 1 mod 8
Or 3N = (1 + 8 ) mod 8 = 9 mod 8 = 3*3 mod 8
That means N = 3 mod 8.
Read every step carefully.
Now let’s use this in remainder problems
If 20N is divisible by 7, find the remainder when N + 20 is divided by 7.
It’s simple to get that N = 0 mod 7
So N + 20 = (0 + 20) mod 7 = 20 mod 7 = (20 – 7 – 7) mod 7 = 6 mod 7.
If 37N = 5 mod 41, find the remainder when N is divided by 41.
37N = 5 mod 41
(37  41) N = 4N = 5 mod 41
4N = 5 mod 41 = (5 + 41) mod 41 = 36 mod 41 = 4*9 mod 41
N = 9 mod 41.
Solve one more to get hold of concept.
Find the smallest natural number N such that 13N = 17 mod 19.
13N = 17 mod 19
(13  19)N = (17  19) mod 19
6N = 2 mod 19
3N = 1 mod 19 = (1  19) mod 19 = 18 mod 19 = 3(6) mod 19
N = 6 mod 19 = 13 mod 19.
Do 5 more problems on this.
Find smallest N such that
i. 31N = 5 mod 17
II. 23 N = 15 mod 19
III. N(N+1) = 2 mod 20
iv. 14N = 3 mod 23
v. 213N = 102 mod 315
Solutions:
i. 31N = 5 mod 17
3N = 12 mod 17
N = 4 mod 17.
ii. 23N = 15 mod 19
(23  19)N = (15+19+19+19) mod 19
4N = 72 mod 19
N = 18 mod 19.
iii. N(N+1) = 2 mod 20
N(N+1) = 1(1 + 1) mod 20
N = 1 mod 20
BUT also, N(N+1) = (2 + 20 + 20) mod 20 = 6(6 + 1) mod 20
So N = 6 mod 20 is also possible.
Also, N(N + 1) = (2 + 180) mod 20 = 13(13 + 1) mod 20
So N = 13mod 20 is also possible.
Similarly N(N + 1) = (2 + 340)mod20 = 18(18 + 1) mod 20
So N = 18 mod 20 also possible.
That means there four possible values of N i.e. 1, 6, 13, 18 mod 20. But smallest is of course 1.
iv. 14N = 3 mod 23
9N = 3 mod 23
3N = 1 mod 23 = 24 mod 23
N = 8 mod 23 = 15 mod 23.
v. 213N = 102 mod 315
102N = 102 mod 315
N = 1 mod 315
N = 314 mod 315
We will do a better problem now.
Find the remainder when 39^{39 }is divided by 41.
Using Euler’s we know that 39^{40 }= 1 mod 41 as HCF(39, 41) = 1
Let’s say 39^{39 }= x mod 41.
39^{40 }= 39 × 39^{39 }= 1 mod 41
39x = 1 mod 41
2x = 40 mod 41
x = 20 mod 41.Next type of problems: If divisor is composed of more than one prime number, then we can break it into its coprime factors and find the individual remainders and then combine them.
Find the remainder when 2^{77 }is divided by 77.
You can directly use phi(77) = 60. But then it’ll be lengthy to find the remainder of 2^{17 }with 77.
So it’s better to find the remainder individually with 7 and 11 and then combine them.
Now 2^{77 }= [(2^{6})^{12}][2^{5}] = 2^{5 }mod 7 = 4 mod 7. (as phi(7) = 6 and HCF(2, 7) = 1)
And 2^{77 }= [(2^{10})^{7}][2^{7}] = 2^{7 }mod 11 = 4 mod 11. (as phi(11) = 10 and HCF(2, 11) = 1)
Now comes the big problem: HOW TO COMBINE THESE REMAINDERS TO GET THE REMAINDER WITH 77.
There are three different methods you can do that.
First is COMMON TERM FINDING method
Write the sequence of numbers 4 mod 7 i.e. 4, 11, 18, 25, 32, 39, …… and
4 mod 11 i.e. 4, 7, 18, 29, ……………
AND we are to just find the smallest common number which is there in both the sequences. 18 it is.
Second is USING EQUATIONS
Write the equation for remainder R = 7a + 4 = 11b – 4
i.e. 7a = 11b – 8 = 7b – 7 + 4b – 1
As LHS is divisible by 7, RHS must be.
So we need to find the smallest b such that 4b – 1 is divisible by 7 and voila... b = 2 satisfies.
That means R = 11*2 – 4 = 18.
Third is imported one CHINESE REMAINDER THEOREM
First step: The two divisors, to be combined, should be coprime
Second step: Write an equation using the two divisors such that the difference between the integral multiple of two divisors is 1.
So in this case we get 11 × 2 – 7 × 3 = 1
Now remainder is obtained by multiplying an extra term with each term of LHS i.e.remainder of the other divisor.
So it becomes [11 × 2 × 4 – 7 × 3 × (4)] mod 77 = (88 + 84) mod 77 = (11 + 7) mod 77 = 18 mod 77.
How many four digit numbers exist such that when divided by 7, 9 and 11 one gets the remainders of 2, 3 and 4 respectively.
7a + 2 = 7a + 2  350 = 7a  348 9b + 3 = 9b + 3  351 = 9b  348 11c + 4 = 11c + 4  352 = 11c  348 So N = 7 × 9 × 11d  348 = 693d  348 = 693d + 345
Here remainders from the three numbers have difference of 1. So I just need to found their multiple with gap of 1 as above and job is done.
And it is also not time consuming as multiple of 11 should give digit sum 1 as it had to be one more than multiple of 9 and multiple of nine will always give digital sum 9 or 0. So 11 (digital sum 2) should be multiplied with a number with digital sum 5 i.e. 5, 14, 23, 32, 41, ...etc. Automatically number one less than this will be multiple of 9. So I just need to check whether number one more less than this multiple of 7 or not.....
General divisibility rules
a^{n }+ b^{n }is divisible by a + b if n is an odd natural number.
a^{n }– b^{n }is divisible by a + b if n is an even natural number.
a^{n }– b^{n }is divisible by a – b if n is any natural number.
a^{n }+ b^{n }+ c^{n }+ … is always divisible by (a + b + c + …) if a, b, c, …are in AP and n is an odd natural number.P(x) is divisible by (x  a) iff P(a) = 0
P(x) gives remainder P(a) when divided by (x  a)
Any (p  1) digit repunit number is always divisible by p where p is a prime number greater than 5.
I can go on forever with this. But I’ll have to stop now. :)

None of the article has explanations to the concept . You are stating the concept . There is no answer to why ? But only shortcuts which has no meaning .

@SiddharthJain Hi Siddharth, there are enough of articles that deal with the concepts and the articles like this are mostly meant for practice and fine tuning the methods. So it is a pre requisite to build the base before solving similar articles. If you are looking for remainder theorem concepts you can read https://www.mbatious.com/topic/61/remaindertheorem (might help)