 Solution

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

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 2 / a / Solution by

Codex  0 2026-10-31

Use modular exponentiation by repeated squaring:

27 \equiv 6 (mod 7), 2 7^{2} \equiv 6^{2} \equiv 1 (mod 7), 2 7^{4} \equiv 2 7^{8} \equiv 2 7^{16} \equiv 1 (mod 7) .

(1)

Since

17 = 16 + 1

, multiply the indicated powers to obtain $2 7^{17} \equiv 6 (mod 7)$ . Only the binary expansion of the exponent determines which squared powers are multiplied.

 Read the full article

 New to topics? Read the docs here!