5
$\begingroup$

How does one determine modulo without a calculator in cases like this: $$15^7 - 13^5(\mod14)$$ Normally I would simply divide what is given by the modulo number and take the decimal output and times it by the modulo number. How can I work out $15^7 - 13^5(mod14)$ without the use of a calculator?

Now what I am thinking is: $$15 \cong 1 \mod 14 $$ $$15^7 \cong 1 \mod 14$$ $$13 \cong -1 \mod 14$$ $$13^2 \cong 1 \mod 14$$ $$13^5 \cong -1 \mod 14$$ $$[15^7 - 13^5(\mod 14)] = 1 (\mod 14) + 1 (\mod 14) = 2\mod 14$$ Is that right?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Yes, that is correct. More generally, you can make use of the Euler Phi Function : en.wikipedia.org/wiki/Euler%27s_totient_function $\endgroup$ – Prahlad Vaidyanathan Oct 19 '13 at 12:50
  • 1
    $\begingroup$ Yes you are right. And the fact that you did that without calculator pleases me. $\endgroup$ – drhab Oct 19 '13 at 12:51
  • $\begingroup$ Actually, you could of replaced the 15 and 13 with 1 and -1 in the first step. You don't need to place mod 14 in an expression event. In general, the only time you can't replace numbers with their modular equivalents is when they are in the exponent or denominator (other people, fact-check me on that.) $\endgroup$ – PyRulez Oct 19 '13 at 13:01
1
$\begingroup$

Yes, that's correct! $$[15^7 - 13^5]\pmod{14} \;\;= \;\;2\pmod {14}$$

|cite|improve this answer
$\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.