Basics of Remainder Theorem  Hemant Malhotra

hemant_malhotra
Director at ElitesGrid  CAT 2016  QA : 99.94, LRDI  99.70% / XAT 2017  QA : 99.975
N=D * Q+R
N number
Ddivisor
Qquotient
RremainderN mod a=r means when number N is divided by a remainder is r ..
FUNDA 1 we have to look for pattern
a) 2^1=2
2^2=4
2^3=8
2^4=16 (unit digit6)
2^5=32(unit digit 2 )
means same repetition start after 2^4b) 3^1=3
3^2=9
3^3=27(7)
3^4=81(1)
after that same cycle will go on
so 3^4k=1 (k=1,2,3,.....)c) 4^1=4
4^2=16=6
4^3=64=(4)
so here odd power will give 4 and even power will give 6d) 5^1=5
5^2=25(5)
so unit digit will always be 5e) 6^1=6
6^2=36 (6)
unit digit will always be 6f) 7^1=7
7^2=49(9)
7^3=243(3)
7^4=1 (unit digit )
7^4k = 1 (after that cycle will repeat)g) 8^1=8
8^2=64(4)
8^3=512(2)
8^4=4096=(6)
8^5=32768(8)
so after 4 same 8 will repeath) 9^1=9
9^2=81=(1)
9^3=9 (unit)
so odd power will give 9 as unit digit and even power will give 1example find unit digit of 3^20
we know that unit digit of 3^4=1
3^20=(3^4)^5=1 as unit digitlet here we wana find unit digit of 9^2021
9^odd=9
9^even=1
2021 is odd so unit digit =9Some basic things u should know
find remainder when 23 * 24 * 25 is divided by 7
NOTE 23 mod 7=2
24 mod7=3
25 mod 7=4
so 2 * 3 * 4 = 24 mod7=3 so remainder is 3find remainder when (81)^3 is divided by 10
81 * 81 * 81 mod 10=81 mod10 * 81 mod10 * 81mod10
=1 * 1 * 1 = 1
so there is no need to check for same number every time
we always try to covert number in such number whose unit digit is 1example
3^40 is divided by 10
3^4=81 we know
so (81)^10 mod 10
(1)^10 mod 10 =1
so remainder 1example
(241)^241 mod 10
241 mod 10=1
(1)^241 mod 10 = 1Fermat Theorem :
Let a and p be coprime
Then a^(p1) mod p = 1 ( p is prime)
5^40 mod 41 =1Find remainder when 36^96 is divided by 31
Chinese Remainder Theorem:
N=x * y where a and b are prime to each other so hcf=1
and A is a number such that
A mod a = r1
A mod b = r2
then remainder of A/N = ar2x + br1y
where ax + by = 1Find remainder when 3^101 divided by 77
so 77 = 7 * 11
so let a=7 and b=11
so 3^101 mod 7=5
3^100 mod 11=3
so choose minimum value of a and b which satisfy this equation
7a + 5 = 11b + 3
a=6 and b=4 so 47 is the remainderNEGATIVE REMAINDER concept (A very useful concept )
Find negative remainder when 50 is divided by 7
so just check multiple of 7 which is larger than 50
which is 56 so negative remainder is 5056=6
and remainder in this case will be 76=1Find remainder when 89 is divided by 10
(89) mod10
89 mod 10=1
1=101=9 so remainder is 9 i hope its clear now this is very useful for larger numbers )Eulers Theorem :
Let a and m be coprime. Then a^E(m) = 1 when divided by m
Let m = x^a × y^b × z^c …
Where x,y,z ... are prime numbers.
Then E(m) = m × (11/x) ×(11/y) ×(11/z) ...Eg: 7^41 mod 100
here 7 and 100 are coprime to each other (( hcf is 1 ))
so we could apply this theorem here
100 = 2^2 * 5^2
E(100)=100 * (11/2)(11/5)
=100 * 1/2 * 4/5 = 40
E(100) = 40
means 7^40 mod 100=1
so 7^41=7 * 7^40 mod 100 =7Find remainder when 5^102 divided 16
5 and 16 are coprime
so 16=2^4
so E(16)=16*1/2=8
E(16)=8
5^96 mod 16=1
so 5^6 mod 16=
9^3 mod 16
81 * 9 mod 16 = 9Some important concepts:
x^2 – y^2 = (xy)(x+y)
x^3 – y^3 = (xy)(x^2+xy+y^2)
x^4  y^4 = (xy)(x+y)(x^2+y^2)so check for odd and even powers
x^n – y^n is always divisible by (xy)
example 5^33^3=1259=116 which is divisible by (53)=2x^ny^n is divisible by (x+y) when n is even number
example5^43^4=62581=544 which is div by (53)=2x^n+y^n is divisible by (x+y) when n is odd
Practice Questions:
Q1) Find remainder when 5^30 is divided by 31
Q2) Find Remainder when 5^120,7^180,9^150 is divided by 31
Q3) Find remainder when 36 ^94 is divided by 31.
Q4) Find the remainder of (18^n) divided by 7, where n = 22^10.
Q5) Find the remainder of 14^n ÷ 11 where n = 17^22.
Q6) What is the remainder when 7^7^7^7^7^7^7.......infinity is divided by 13?