How to evaluate $3^{123}\!\bmod 3\,$ and $5^{123}\! \bmod 2$ and similar?

Question

I hope someone can explain me how to solve modulo -equations ,e.g.

$5^{123} \mod 2$

It was a little bit overwhelming for me to get a feeling for solving such equations.I don't how and when i have to use one of these great theorems like, Fermat's little ,Euler totient function,Chinese remainder theorem a.s.o.So I decide to ask you guys for helping me with my stacks.

Answer 1

The answer is pretty obvious: it is $0$ ($3^n$ where $n$ is a positive integer obviously divides $3$ and thus has a remainder of $0$). If you were asking for$\pmod{10}$, then we would apply Euler's Totient's Function, $\phi(n)$ and then simplify from there. For your next question, since $5\equiv 1\pmod 2$, we have that $$5^{123}\equiv 1^{123}\equiv 1\pmod{2}.$$