Team Selection Test for JBMO, 2024

We consider two cases.

Case 1: $x = 0$ is one of the remainders.

Then $k+1$ divides exactly one of the divisors. Thus $k+1$ divides $n$ and indeed $k+1 = n$. So $k+1$ has $k$ positive divisors. Then $k|k+1$ or $k-1|k+1$. Therefore, $k=1,2$ or $3$, that is $k+1=2,3$ or $4$.

Case 2: $0$ is not one of the remainders.

Suppose that $k+1$ is not prime. Then $k+1 = pm$ where $p$ is a prime number and $m > 1$ is an integer. The ones with the remainders $p, 2p, \dots, p(m-1)$ are the ones which are divisible by $p$. Let $n = p^a r$ where $\gcd(p, r) = 1$. Let $s$ be the number of positive divisors of $r$. Then $k = (\alpha+1)s$ and $m-1 = \alpha s$ is the number of positive divisors of $n$ which are divisible by $p$. Then we have
$$2 < \frac{pm-1}{m-1} = \frac{k}{m-1} = \frac{(\alpha+1)s}{\alpha s} = \frac{\alpha+1}{\alpha} \le 2,$$
which is a contradiction. Thus, in this case $k+1$ has to be prime.

Remark: By Dirichlet's theorem and primitive roots, for any prime number $p$ there exists a prime number $q$ such that $n = q^{p-2}$ has $p-1$ positive divisors and they all have distinct remainders when divided by $p$.