1
$\begingroup$

Suppose we wanted to find the least non-negative residue of, say, $15^{81} \ \text{mod $13$}$, as is a problem in Norman Bigg's Discrete Math text.

I know how to solve this by brute-force, but I'm trying to focus a bit more on tricks of the trade that would get me to an answer faster and more intuitively than trial and error, i.e., picking an appropriate power and hoping I can enter the numbers fast enough on my calculator so as to not run out of time on an exam.

So, the first, and perhaps most useful trick here, is to say that in mod $13$, $2 \equiv 15$. This simplifies the problem considerably. The next step I'm hesistant about, though, is whether we could say that $81 \equiv 3 \ \text{mod $13$}$, so $2^{81} = 2^3 = 8$. This doesn't seem to work, as the correct answer to this problem should be $6$.

My questions, then, are:

(1) If it's accurate that this approach fails, why does it fail? (The answer to this, I imagine, could be as simple as "the modular system doesn't extend to exponents," but I would appreciate if someone could note this, if so.)

(2) Are there any other useful tricks for a problem like this that simplify the computation?

Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ 1. Read about Fermat's little theorem. Since 13 is prime, you should reduce the exponent (i.e. 81) modulo 12 (not modulo 13). This gives $2^9$ modulo 13, which is 5. $\endgroup$ – Aravind Jun 21 '18 at 17:29
  • 1
    $\begingroup$ 2. Use repeated squaring: Find $x^2,x^4,x^8$ etc. $\endgroup$ – Aravind Jun 21 '18 at 17:29
  • $\begingroup$ Excellent. I've heard, but completely forgot, about that theorem. Thank you for this. $\endgroup$ – Matt.P Jun 21 '18 at 17:31

Your Answer

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

Browse other questions tagged or ask your own question.