Pls help me find the least non-negative residue of this problem

[peejigno]

How can you find the least non-negative residue of 2^20 modulo 35. If using a calculator, we can easily get 11, however, is there a concrete solution to show this? Can we use Euler's Theorem to solve this?

 

[Deleted member 4993]

How can you find the least non-negative residue of 2^20 modulo 35. If using a calculator, we can easily get 11, however, is there a concrete solution to show this? Can we use Euler's Theorem to solve this?

Duplicate Post:

http://mathhelpforum.com/number-the...-find-least-non-negative-residue-problem.html

 

[daon2]

How can you find the least non-negative residue of 2^20 modulo 35. If using a calculator, we can easily get 11, however, is there a concrete solution to show this? Can we use Euler's Theorem to solve this?

2^5 (mod 35) = 32 (mod 35) = (-3) (mod 35)

So 2^20 (mod 35) = (-3)^4 (mod 35) = 3^4 (mod 35)

edit: yes, you can use Euler's Theorem, but it isn't much better. First note that phi(35)=phi(5)*phi(7) = 24. So 2^24=1 (mod 35)

1. Find the multiplicative inverse of 2 mod 35 (it is a unit, so it has one--obvious in this case).
2. 2^20 (mod 35) = 2^24*(2^(-1))^4 (mod 35) = (2^(-1))^4 (mod 35)