Thread: 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?

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,

.

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



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.

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⁶ = 64 = 29 (mod 35), so the order of 2 is not 6.

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

thus: 2²⁰ = (2¹²)(2⁸) = 2⁸ = (16)² = 256 = 11 (mod 35).