 Solution

ID: past-exam-of-the-options-i-course-of-the-university-of-oxford/2012/c/c1/b/solution

Let

R_{n} = {k \in Z : 0 < k < n, g cd (k, n) = 1}

. The map

k \mapsto n - k

sends

R_{n}

to itself because

g cd (n, n - k) = g cd (n, k) = 1.

Applying it twice returns

k

, so it is a bijection. Reindexing the finite sum by this bijection gives

k \in R_{n} \sum k = k \in R_{n} \sum (n - k) .

There is no need to assume that every residue belongs to a pair of distinct elements; the reindexing also handles the fixed point when

n = 2

 New to topics? Read the docs here!