Basics of Remainder Theorem - Hemant Malhotra


  • Director at ElitesGrid | CAT 2016 - QA : 99.94, LR-DI - 99.70% / XAT 2017 - QA : 99.975


    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?


Log in to reply
 

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