Results 1 to 3 of 3

Math Help - Finding the remainder

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    95

    Finding the remainder

    Hi , is there any trick to find the remainder when a number is raised to a large power and we need to find the mod of it?
    E.g what is :
    1086^1183 mod 47?
    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,806
    Thanks
    697
    Hello, pranay!

    I have a very primtive approach . . .


    Is there any trick to find the remainder when a number is raised to a large power
    and we need to find the mod of it?

    Example: .What is: 1086^1183 (mod 47) ?

    Note that: .1086 ≡ 5 (mod 47)

    We have: .5^{1183} (mod 47)


    Theorem .If p is a prime, then: .a^{p-1} ≡ 1 (mod p)

    . . Hence: .5^{46} ≡ 1 (mod 47)


    Since 1183 .= .46(25) + 33, .

    . . 5^{1183} .= .5^{46(25) + 33} .= .(5^46)^25 * 5^33

    . . . . . . . . . . .1^25 * 5^33 (mod 47) . .5^33 (mod 47)


    This is the primitive part.
    We can evaluate 5^33 by cranking out certain powers of 5 (mod 47).

    . . 5^1 . . 5 (mod 47)
    . . 5^2 . .25
    . . 5^4 . .14
    . . 5^8 . . 8
    - 5^16 . .17
    - 5^32 . . 7


    Hence: .5^33 .= .(5^32)(5^1) . .(7)(5) (mod 47) . .35 (mod 47)


    Therefore: . 1086^1183 . . 35 (mod 47)

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    95
    Thanks a ton for that
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding the remainder
    Posted in the Number Theory Forum
    Replies: 12
    Last Post: July 16th 2010, 03:34 AM
  2. finding remainder
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 7th 2009, 10:57 AM
  3. finding the remainder
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 1st 2009, 03:16 AM
  4. finding P(x) and the remainder
    Posted in the Algebra Forum
    Replies: 4
    Last Post: January 14th 2009, 02:02 AM
  5. finding the remainder by mod
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 2nd 2008, 07:31 AM

Search Tags


/mathhelpforum @mathhelpforum