How to calculate mod of number with big exponent

Question

I want to find

$$ 5^{133} \mod 8. $$ I have noticed that $5^n \mod 8 = 5$ when $n$ is uneven and 1 otherwise, which would lead me to say that $5^{133} \mod 8 = 5$ But I don't know how to prove this. How can I prove that this is the case (or find another solution if it is not)?

Answer 1

First of all it is easy to see that $5^2\equiv 1$ (mod $8$). We also know that $133=66\times 2+1$. Hence

$5^{133}\equiv 5^{2\times 66+1}\equiv 5\times (5^2)^{66}\equiv 5\times 1^{66}\equiv 5$ (mod $8$).

Answer 2

"Highbrow method":

If you undertake to learn any number theory , there is Euler's theorem: $$a^{\varphi (n)}\cong1\pmod n$$, for $a$ relatively prime to $n$.

($\varphi$ is Euler's totient function, and just returns the number of positive integers less than $n$ that are relatively prime to $n$.)

Now $\varphi (8)=4$. Hence $5^4\cong1\pmod8.$

Use this to reduce the exponent: $133=4×33+1\implies5^{133}=(5^4)^{33}\cdot 5\cong5\pmod8$.