Question

How do I determine 8^402 mod 5? I know that 8 is 3 mod 5 but I get stuck after that.

Answer 1

i believe 5 and 402 are relatively prime

Answer 2

8*8*8*...*8 = x (m5)

3*3*3*...*3 = x (m5)
402 times

9*9*9*...*9 = x (m5)
201 times

4*4*4*...*4 = x (m5)
201 times

16*16*16*...*16 * 4
100 times 1 time

16 = 1 (m5)

so im thinking we get down to 4 (m5) in the end

Answer 3

theres prolly some thrms that ive forgotten about that could make that simpler overall

Answer 4

\[8^{402}\]
\[4^{402}~2^{402}\]
\[(4^2)^{201}~2^{402}\]
\[(16)^{201}~2^{402}\]
\[(1)^{201}~2^{402}\]
\[2^{402}\]
\[2^{400+2}\]
\[2^{400}~2^2\]

Answer 5

the answers i'm finding say 4 mod 5 but I just don't understand how it gets there

Answer 6

it has to do with reducing the setup ... if you want to approach it the long way

Answer 7

there is a shorter route that i can never fully recall; but i think that 2^(400) 2^(2) is key to it

Answer 8

my long route, was to take this to 4^2 = 16; since 16 = 5(3)+1 , 16 = 1 mod5

1*1*1*1*1 ... = 1 so all that leaves us the the *4 thats left over
4 = 4 mod5

Answer 9

8*8 = 64 = -1 mod 5 would have been another way to view it

\[8^{402}\]
\[(8^2)^{201}\]
\[(64)^{201}\]
\[(-1)^{201}\]
\[(-1)^{200+1}\]
\[(-1)^{200}~(-1)^1\]
\[(-1)^1=-1\]

-1 = 5(-1) + 4, therefore ... 4 mod 5