• Support PF! Buy your school textbooks, materials and every day products Here!

A problem with Euler theorem

  • #1
391
0

Homework Statement



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

Homework Equations



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



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
 

Answers and Replies

  • #2
1,838
7
phi(55) = 4*10=40

So, 2^40 = 1

1000005 = 1000000 + 5 which Modulo 40 is 5

So 2^2000005 = 2^5 = 32.
 

Related Threads for: A problem with Euler theorem

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
3
Views
8K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
2
Views
3K
Top