Exercise 7. Let $p \geqslant 3$ be a prime number. For $k \in \mathbb{N}$ satisfying $1 \leqslant k \leqslant p-1$, the number of divisors of $\mathrm{kp}+1$ that are strictly between $k$ and $p$ is denoted by $a_{k}$.

What is the value of $a_{1}+a_{2}+\ldots+a_{p-1}$?
Solution to Exercise 7 The answer is $p-2$.

We will show that each of $\{2, \ldots, \boldsymbol{p}-1\}$ contributes exactly once to the count represented by $a_{1}+a_{2}+\ldots+a_{p-1}$.

Let $2 \leqslant \mathrm{~m} \leqslant \mathrm{p}-1$ be an integer, we aim to show two things:

1. m is counted at most once
2. m is indeed counted

m is counted at most once:

By contradiction, suppose there exist $1 \leqslant \mathrm{i} < \mathrm{j} \leqslant p-1$ such that:
- $m \mid i p+1$ and $m \mid j p+1$ and $m>j$

We then have $\mathrm{m} \mid \mathrm{p}(\mathfrak{j}-\mathfrak{i})$ but $\operatorname{pgcd}(\mathrm{m}, \mathrm{p})=1$ so $\mathrm{m} \mid \mathfrak{j}-\mathfrak{i}$. However, this is impossible because $0 < \mathfrak{j}-\mathfrak{i} < \mathfrak{j} < \mathrm{m}$. Therefore, m is counted at most once.

m is indeed counted:

We consider the $m-1$ integers $\{p+1, 2p+1, \ldots, (m-1)p+1\}$.

Just as before, we see that they are distinct modulo m. Moreover, none of them is $\equiv 1(\bmod m)$ because if we remove the +1, no integer is divisible by $m$.

Thus, m is counted exactly once, and this concludes the proof.

Comment from the graders

The general approach was understood, but the formalization of this reasoning was not always rigorous.