1
$\begingroup$

It is fairly straightforward to perform a modulus operation on small numbers by hand, but is there an easy way to find the modulus of larger numbers based on the smaller roots? For example:

180 mod 13 is 11. Is there an easy way to find, by hand, the following:

  • 180^2 mod 13
  • 180^4 mod 13
  • 180^8 mod 13
  • 180^12 mod 13
$\endgroup$
1
$\begingroup$

Yes, via successive squaring:

  • $180^2 \equiv 11^2 \equiv 121 \equiv -9 \equiv 4 \pmod{13}$

  • $180^4 = (180^2)^2 \equiv 4^2 \equiv 3 \pmod{13}$

  • $180^8 = (180^4)^2 \equiv \cdots$

and so on. In this manner, any exponent which is a power of $2$ can be done. Now for other exponents, write as a sum of powers of $2$ - for example, $12 = 8 + 4$.

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