1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A problem with Euler theorem

  1. Apr 17, 2009 #1
    1. The problem statement, all variables and given/known data

    i need to obtain the remainder of the divison [tex] 2^{1000005}[/tex] divided by 55

    2. Relevant equations

    Euler theorem [tex] 2^{\phi (55)}=1 mod(55) [/tex]

    3. The attempt at a solution

    my problem is that applying Euler theorem i reach to the conclusion that the remainder is the same as the value 'a' inside the congruence equation

    [tex] 2^{5}=a mod(55)[/tex] but it would give me that a is negative ¡¡

    it gives me a=-23 or similar using congruences or a =32
  2. jcsd
  3. Apr 17, 2009 #2
    phi(55) = 4*10=40

    So, 2^40 = 1

    1000005 = 1000000 + 5 which Modulo 40 is 5

    So 2^2000005 = 2^5 = 32.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook