 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/e/solution

In modular arithmetic, calculations may be performed after replacing each input by its remainder. For a positive modulus

m

, write

[a]_{m}

for the remainder in

{0, \dots, m - 1}

. Then

[a + b]_{m} [ab]_{m} [a^{k}]_{m} = [[a]_{m} + [b]_{m}]_{m}, = [[a]_{m} [b]_{m}]_{m}, = [[a]_{m}^{k}]_{m} (k \geq 0) .

Equivalently, if

a \equiv a^{'} (mod m)

and

b \equiv b^{'} (mod m)

a + b \equiv a^{'} + b^{'}

and

ab \equiv a^{'} b^{'}

, and a fixed nonnegative integer exponent gives

a^{k} \equiv (a^{'})^{k}

. One cannot in general reduce the exponent modulo

m

by this rule.

 New to topics? Read the docs here!