1

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
cowdrool
  • 147

1 Answers1

1

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