Claim. Given a positive integer nn, let Sn={a1,a2,a3,…,am}S_n=\{a_1,a_2,a_3,\ldots,a_m\} be the set of all positive integers less than nn and relatively prime to nn. Then ∑k=1mak\sum_{k=1}^m a_k is divisible by nn.

Proof. Using the fact that if kk is relatively prime to nn, then so is n−kn-k, we can compute twice the sum with the following.

∑k=1m(ak+(n−ak)). \sum_{k=1}^m \left(a_k+(n-a_k)\right).

The desired sum is half of the above equation, which simplifies as follows.

12∑k=1m(ak+(n−ak))=12∑k=1mn=mn2. \begin{aligned} \frac{1}{2}\sum_{k=1}^m \left(a_k+(n-a_k)\right) &= \frac{1}{2}\sum_{k=1}^m n \\ &= \frac{mn}{2}. \end{aligned}

Thus the sum is mn2\frac{mn}{2}, which is divible by nn.

□