 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/discrete-mathematics-continuous-mathematics-and-probability-resit/3/c/solution

a = q n + r

and

b = s n + t

q, s

and

0 \leq r, t < n

a \equiv b (mod n)

. Apply the addition rule from part (b)(i) with

- q n \equiv - s n \equiv 0 (mod n)

to obtain

r = a - q n \equiv b - s n = t (mod n) .

Therefore

n ∣ r - t

. But

- n < r - t < n

, and the only multiple of

n

in that interval is zero. Hence

r = t,

so the two remainders agree.

 New to topics? Read the docs here!