compute 4^123 mod 7

Question

 

Hello 

I want help with compute 4^123 mod 7

 

thanks

Answer 1

4^123 = 2^246

 

Write a series of congruences: 2^o = 1  so

2^o Ξ 1 mod 7 

2¹ Ξ 2 mod 7   

2² Ξ 4 mod 7

2³ Ξ 1 mod 7 ⇐the results 1, 2 or 4 begin to repeat, here.

 

You'll find that as the powers of 2 increase by 1, the above pattern repeats (successively congruent to 1, 2 & 4) cyclically (or periodically).

 

So you can take the exponent 246 and divide it by 3, keeping only the remainder (exponent 0, 1 or 2).  The remainder is 0, so we conclude that 2^246 Ξ 1 mod 7.

 

In short, the answer is 1.