# A problem with Euler theorem

1. Apr 17, 2009

### zetafunction

1. The problem statement, all variables and given/known data

i need to obtain the remainder of the divison $$2^{1000005}$$ divided by 55

2. Relevant equations

Euler theorem $$2^{\phi (55)}=1 mod(55)$$

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

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

it gives me a=-23 or similar using congruences or a =32

2. Apr 17, 2009

### Count Iblis

phi(55) = 4*10=40

So, 2^40 = 1

1000005 = 1000000 + 5 which Modulo 40 is 5

So 2^2000005 = 2^5 = 32.