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?
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?
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?
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)
This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
By continuing to use this site, you are consenting to our use of cookies.