China National Team Selection Test

Proof Clearly, if $n$ satisfies the required property, then $1\le n\le p-1$. Denote all such $n$'s by $n_1<n_2<\cdots <n_k$; we shall show that $k\le 12p^{\frac{2}{3}}$. If $k\le 12$ there is nothing to prove. In what follows, we assume that $k>12$.

Rename $n_{i+1}-n_i$ ($1\le i\le k-1$) in nondecreasing order as $1\le {\mu }_1\le {\mu }_2\le \cdots \le {\mu }_{k-1}$. It is clear that $$\sum _{i=1}^{k-1}{\mu }_i=\sum _{i=1}^k(n_{i+1}-n_i)=n_k-n_1<p.\stackrel{◯}{1}$$ First, we show that for any $s\ge 1$, $$|\{1\le i\le k-1:{\mu }_i=s\}|\le s,\stackrel{◯}{2}$$ i.e. there are at most $s$ ${\mu }_i$'s equal to $s$. In fact, suppose that $n_{i+1}-n_i=s$; then $n_i!+1\equiv n_{i+1}!+1\equiv 0(\mathrm{mod}p)$, so $(p,n_i!)=1$, and $$(n_i+s)(n_i+s-1)\cdots (n_i+1)\equiv 1(\mathrm{mod}p).$$ Thus, $n_i$ is a solution to the congruence equation $$(x+s)(x+s-1)\cdots (x+1)\equiv 1(\mathrm{mod}p).$$ Since $p$ is a prime number, there are at most $s$ solutions to the above equation, thanks to Lagrange's theorem. Thus, there are at most $s$ $n_i$'s with $n_{i+1}-n_i=s$, i.e. ② holds.

Now, we show that for any nonnegative integer $l$, if $\frac{l(l+1)}{2}+1\le k-1$, then ${\mu }_{\frac{l(l+1)}{2}+1}\ge l+1$. Suppose on the contrary that ${\mu }_{\frac{l(l+1)}{2}+1}\le l$. Then ${\mu }_1,{\mu }_2,\dots ,{\mu }_{\frac{l(l+1)}{2}+1}$ are all positive integers between $1$ and $l$. By ②, there is at most one ${\mu }_i$ equal to $1$, at most two ${\mu }_i$'s equal to $2$, $\dots$, at most $l$ ${\mu }_i$'s equal to $l$, and thus there are at most $1+2+\cdots +l=\frac{l(l+1)}{2}$ ${\mu }_i$'s less than or equal to $l$, which contradicts the assumption that ${\mu }_1,{\mu }_2,\dots ,{\mu }_{\frac{l(l+1)}{2}+1}$ are all less than or equal to $l$.

Let $m$ be the largest positive integer with $\frac{m(m+1)}{2}+1\le k-1$. Then $$\frac{m(m+1)}{2}+1\le k-1<\frac{(m+1)(m+2)}{2}+1,\text{③}$$ and hence $$\begin{array}{rl}\sum _{i=1}^{k-1}{\mu }_i& \ge \sum _{i=0}^{m-1}(i+1{)}^2\\ & =\frac{m(m+1)(2m+1)}{6}>\frac{m^3}{3}.\end{array}$$ Since $k>12$, $m\ge 4$, combining ① and ③ we get $$\begin{array}{rl}k& <2+\frac{(m+1)(m+2)}{2}\\ & <4m^2+4{\left(3\sum _{i=1}^{k-1}{\mu }_i\right)}^{\frac{2}{3}}\\ & <4\times (3p{)}^{\frac{2}{3}}.\end{array}$$ This completes our proof.