Results 1 to 5 of 5

Math Help - remainder problem

  1. #1
    Member
    Joined
    Jun 2009
    Posts
    77

    remainder problem

    what is the remainder in the given problem
    \frac{2^{1990}}{1990}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2008
    Posts
    13
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by jashansinghal View Post
    what is the remainder in the given problem
    \frac{2^{1990}}{1990}


    \frac{2^{1990}}{1990} is equivalent to  2^{1990} mod 1990

    and
     1990_{10} \, = \, 11111000110_2

    Using the exponentiation algorithm mod 1990 at each step.

    Spoiler:
    1024
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2009
    Posts
    77
    i dont know what is mod and how do we solve it
    can u give step by step method
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by jashansinghal View Post
    i dont know what is mod and how do we solve it
    can u give step by step method

    For information about mod, modulus, & mod operator: use Google
    There are hundreds of essays on the subject far better than anything I could do.
    For the Exponentiaion Algorithm or Russian Peasant Algorithm, Russian Peasant Multiplication also check Google.
    (NOTE: Lee Lady, professor Hawaii University, has some excellent essays.)

    You need to be careful as you interpret the following note.
    The base you are working with is the number 2: as in 2^1990
    It is very easy to mistake the base 2 with the binary exponent value.
    If your problem were 3^1990, the following would be much more clear.
    ][
    the binary representation of decimal 1990 is: 11111000110
    Code:
     
    10 9 8 7 6 5 4 3 2 1 0 <-exponent value
     1 1 1 1 1 0 0 0 1 1 0 <-bit value
    2^0 = 1 x 0 = 0
    2^1 = 2 x 1 = 2 !
    2^2 = 4 x 1 = 4 !
    2^3 = 8 x 0 = 0
    2^4 = 16 x 0 = 0
    2^5 = 32 x 0 = 0
    2^6 = 64 x 1 = 64 !
    2^7 = 128 x 1 = 128 !
    2^8 = 256 x 1 = 256 !
    2^9 = 512 x 1 = 512 !
    2^{10}=1024 x 1 = 1024 !
    -----------------======
    the sum..........= 1990
    Take note of the exclamation marks.
    (see positional notation, number systems, binary, decimal)


    2^2 = 4
    2^2 mod (1990) = 4

    2^4 = 16
    2^4 mod (1990) = 16

    2^8 = 256
    2^8 mod (1990) = 256

    2^{16} = 65536
    2^{16} mod (1990) = 1856
    Here's how:
     \frac{65536}{1990} \, = \, 32.93266332
    using only the integer part of the division or 32.

    65536 - 32 x 1990 = 1856. 1856 is the remainder.
    thus
    2^{16} mod (1990) = 1856

    2^{32} = 4294967296

     \frac{4294967296}{1990} = 2158275.023

    ignore decimal part
    4294967296 - 2158275 * 1990 = 46
    2^{32} mod (1990) = 46
    :::
    Now, the short cut:
    -----------------------
    This should be obvious: 2^{32} = (2^{16})^2
    -----------------------
    2^{16} mod (1990) = 1856 (from above)
    1856 x 1856 = 3444736

     \frac{3444736}{1990} = 1731.023116

    3444736 - 1731 x 1990 = 46
    restated:
    2^{32} mod (1990) \equiv (2^{16})^2 mod (1990) \equiv 1856^2 mod (1990) \equiv 46


    2^{64} mod (1990) \equiv (2^{32})^2 mod (1990) \equiv 46^2 mod (1990) \equiv 126
    (46x46 = 2116; 2116 - 1990 = 126)

    2^{128} mod (1990) \equiv 126^2 mod (1990) \equiv 1946
    the math (126^2 = 15876; 15876 - 1990 x 7 = 1946)

    2^{256} \, mod \, (1990) \, \equiv \, 1946^2 \, mod \, (1990) \equiv 3786916; 3786916 - 1902 x 1990 = 1936

    2^{512} \, mod \, (1990) \, \equiv \, 1936^2 \, mod \, (1990) \equiv 3748096; 3748096 - 1883 x 1990 = 926

    2^{1024} \, mod \, (1990) \equiv 926^2 \, mod \, (1990) \, \equiv \, 857476 ; 857476 - 430 x 1990 = 1776

    synopsis:
    ALL values mod 1990
    2^2 = 4
    2^4 = 16
    2^{64} = 126
    2^{128} = 1946
    2^{256} = 1936
    2^{512} = 926
    2^{1024} = 1776

    You need the product of those residues (1776 x 926 x 1936 x 1946 x 126 x 16 x 4) mod 1990.

    (1776 x 926 ) mod 1990 = 836
    (836 x 1936 ) mod 1990 = 626
    (626 x 1946 ) mod 1990 = 316
    (316 x 126 ) mod 1990 = 16
    ( 16 x 16 ) mod 1990 = 256
    (256 x 4 ) mod 1990 = 1024

    2^{1990} \, = \,

    11212213821037641838211261730250800625217946309459
    91406716447985181412364640986634625644029605963154
    21723238734276119411469445211021782747209563609000
    64972513586913002471902343817263588695316881975481
    15137338732859195463512171761366673017832426429237
    99711910701330467586859989849241515282750160373017
    90300912516495018013525937732371563272857314544411
    76762001979655338142876191485666369934489856131673
    01959569331441814577169706892972697421731624269082
    89983779501164116695096053678910074226753634436580
    34720511968591074370394031117377266157313625740076
    97876147886258594553557393376919388439633643700224

    that number divided by 1990 will have a remainder of 1024.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Remainder Problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 8th 2011, 10:23 AM
  2. Remainder Problem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 30th 2010, 01:39 PM
  3. Another remainder problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: July 16th 2010, 03:19 AM
  4. Remainder problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 17th 2009, 01:33 AM
  5. Remainder problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 20th 2009, 04:46 AM

Search Tags


/mathhelpforum @mathhelpforum