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

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} \cdot {2}^{4} = \left(16 \cdot 16\right) \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 = \left(32 \cdot 32\right) \mod 47 = 37 \mod 47$
${2}^{20} \mod 47 = \left(37 \cdot 37\right) \mod 47 = 6 \mod 47$
${2}^{40} \mod 47 = \left(6 \cdot 6\right) \mod 47 = 36 \mod 47$
${2}^{80} \mod 47 = \left(36 \cdot 36\right) \mod 47 = 27 \mod 47$
${2}^{160} \mod 47 = \left(27 \cdot 27\right) \mod 47 = 24 \mod 47$

Finally, since ${2}^{200} = {2}^{160} \cdot {2}^{40}$
${2}^{200} \mod 47 = \left(24 \cdot 36\right) \mod 47 = 18 \mod 47$.