Question

Find the least positive residues modulo 47 of 2^200. Help me please to solve this problem?

Answer 1

`2^200 mod 47 = 18 mod 47`

Explanation:

There are probably more elegant ways to solve this problem, but we can make use of the fact that you are allowed to multiply across a modulo.

E.g., `2^4 = 16`, so `2^4 mod 47 = 16`. To find `2^8 mod 47` use the fact that `2^8 = 2^4 * 2^4 = (16 * 16) mod 47 = 256 mod 47 = 21 mod 47`.

We proceed in the following manner.
`2^5 mod 47 = 32 mod 47`
`2^10 mod 47 = (32 * 32) mod 47 = 37 mod 47`
`2^20 mod 47 = (37*37) mod 47 = 6 mod 47`
`2^40 mod 47 = (6*6) mod 47 = 36 mod 47`
`2^80 mod 47 = (36 * 36) mod 47 = 27 mod 47`
`2^160 mod 47 = (27*27) mod 47 = 24 mod 47`

Finally, since `2^200 = 2^160 * 2^40`
`2^200 mod 47 = (24 * 36) mod 47 = 18 mod 47`.