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

1 Answer
Jarob R G.
Apr 11, 2018

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

Related questions
Impact of this question
4487 views around the world
You can reuse this answer
Creative Commons License