# Basics of Remainder Theorem - Hemant Malhotra

• N=D * Q+R
N- number
D-divisor
Q-quotient
R-remainder

N 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^4

b) 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 6

d) 5^1=5
5^2=25(5)
so unit digit will always be 5

e) 6^1=6
6^2=36 (6)
unit digit will always be 6

f) 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 repeat

h) 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 1

example- find unit digit of 3^20
we know that unit digit of 3^4=1
3^20=(3^4)^5=1 as unit digit

let here we wana find unit digit of 9^2021
9^odd=9
9^even=1
2021 is odd so unit digit =9

Some 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 3

find 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 1

example
3^40 is divided by 10
3^4=81 we know
so (81)^10 mod 10
(1)^10 mod 10 =1
so remainder 1

example
(241)^241 mod 10
241 mod 10=1
(1)^241 mod 10 = 1

Fermat Theorem :

Let a and p be co-prime
Then a^(p-1) mod p = 1 ( p is prime)
5^40 mod 41 =1

Find 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 = 1

Find 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 remainder

NEGATIVE 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 50-56=-6
and remainder in this case will be 7-6=1

Find remainder when 89 is divided by 10
(89) mod10
89 mod 10=-1
-1=10-1=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 × (1-1/x) ×(1-1/y) ×(1-1/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 * (1-1/2)(1-1/5)
=100 * 1/2 * 4/5 = 40
E(100) = 40
means 7^40 mod 100=1
so 7^41=7 * 7^40 mod 100 =7

Find 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 = 9

Some important concepts:

x^2 – y^2 = (x-y)(x+y)
x^3 – y^3 = (x-y)(x^2+xy+y^2)
x^4 - y^4 = (x-y)(x+y)(x^2+y^2)

so check for odd and even powers

1. x^n – y^n is always divisible by (x-y)
example- 5^3-3^3=125-9=116 which is divisible by (5-3)=2

2. x^n-y^n is divisible by (x+y) when n is even number
example-5^4-3^4=625-81=544 which is div by (5-3)=2

3. x^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?

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.