modulo of a large number

Question

I need help with solving modulo of large numbers, wondering if it is possible to compute the answer without the use of calculator.

for example: 545^112 (mod 23) how can this be solved? I reduced my answer to 545^2 (mod 23) and wonder if there is a way to continue without the use of calculator to compute 545^2.

and how can I find 545^112 (mod 24) from here?

Thanks.

Answer 1

You can reduce $545 \pmod{23}$. So $545^{112}\equiv 545^2\equiv 16^2 \pmod{23}$.

For your second question, you can reduce $545 \pmod{24}$ and you can reduce $112 \pmod{8}$ since $\varphi(24)=8$

Answer 2

A simple reduction is to note that if $$a \equiv b \pmod{n} $$ then $$a^c \equiv b^c \pmod{n} $$ So you can reduce $545$ modulo $23$.

In combination with the reduction you used already, this results in something very manageable.