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

• Jul 4th 2012, 06:23 AM
peejigno
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?
• Jul 4th 2012, 08:46 AM
richard1234
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,

$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

$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.
• Jul 11th 2012, 10:25 PM
Deveno
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 26 = 64 = 29 (mod 35), so the order of 2 is not 6.

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

thus: 220 = (212)(28) = 28 = (16)2 = 256 = 11 (mod 35).