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$.