1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    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!

Homework Help: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook