 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/discrete-mathematics-probability-and-continuous-mathematics/2/g/solution

a, a^{2}, a^{4}, a^{8}, \dots

by successively squaring. The binary representation of the exponent specifies which of these values to multiply. For modular exponentiation, reduce after every multiplication; only a number of steps proportional to the logarithm of the exponent is needed.

Here

13 \equiv 2 (mod 11)

and

17 = 16 + 1

. Successive squares give

2^{2} \equiv 4, 2^{4} \equiv 16 \equiv 5, 2^{8} \equiv 25 \equiv 3, 2^{16} \equiv 9 (mod 11) .

Therefore

1 3^{17} \equiv 2^{16} 2 \equiv 9 \cdot 2 \equiv 7 (mod 11); remainder 7.

 New to topics? Read the docs here!