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

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? I don't think Fermat's little theorem is applicable since 35 is not a prime. Can we use Euler's Theorem to solve this?

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

We can't use Fermat's little theorem directly, but we can calculate the residues mod 5 and mod 7. By Fermat's little theorem,

$\displaystyle 2^5 \equiv 2 (\mod 5) \Rightarrow 2^{20} \equiv 2^4 \equiv 1 (\mod 5)$.

Also, the powers of 2 form the sequence 1,2,4,1,2,4,1,2,4... (mod 7). 20 is congruent to 2 (mod 3) so

$\displaystyle 2^{20} \equiv 2^2 \equiv 4 (\mod 7)$

Out of the numbers 1,2,3,...,35, we can easily show that 11 is the only number that is both 1 mod 5 and 4 mod 7. Therefore the answer is 11.

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

yes, you can use Euler's theorem. since gcd(2,35) = 1, we have:

2^{φ(35)} = 1 (mod 35).

now φ(35) = φ(5)φ(7) = (4)(6) = 24.

this tells us the order of 2 in U(35) is either 2,3,4,6,8,12 or 24. we can eliminate 2,3 and 4 straightaway.

now 2^{6} = 64 = 29 (mod 35), so the order of 2 is not 6.

2^{12} = (29)^{2} = 841 = 1 (mod 35), so the order of 2 is 12.

thus: 2^{20} = (2^{12})(2^{8}) = 2^{8} = (16)^{2} = 256 = 11 (mod 35).