0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ note that $545^2\equiv 1 \mod 24$ $\endgroup$ – Dr. Sonnhard Graubner Nov 8 '14 at 13:53
  • $\begingroup$ Is it a typo or on purpose that you use once $23$ and once $24$? $\endgroup$ – quid Nov 8 '14 at 13:55
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.