# modulo of a large number

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.

• note that $545^2\equiv 1 \mod 24$ Nov 8, 2014 at 13:53
• Is it a typo or on purpose that you use once $23$ and once $24$?
– quid
Nov 8, 2014 at 13:55

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$.
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$