China National Team Selection Test

Let $n=p_1^{a_1}\cdots p_k^{a_k}$ be the standard factorization of $n$. Since $p_1^{a_1},\dots ,p_k^{a_k}$ are pairwise coprime, by the Chinese Remainder Theorem, for each $i$, $1\le i\le k$, congruence equations $$\{\begin{array}{l}x\equiv 1(\mathrm{mod}{p}_i^{a_i})\\ x\equiv 0(\mathrm{mod}{p}_j^{a_j}),j\ne i\end{array}$$ have solution $x_i$. For any solution of $x_0^2=x_0(\mathrm{mod}n)$, we see that $x_0(x_0-1)\equiv 0(\mathrm{mod}n)$. Then for each $i=1,2,\dots ,k$, either $x_0\equiv 0(\mathrm{mod}{p}_i^{a_i})$ or $x_0\equiv 1(\mathrm{mod}{p}_i^{a_i})$. Further, let $S(A)$ be the sum of elements of subset $\{x_1,x_2,\dots ,x_k\}$ (particularly, $S(\varnothing )=0$). Obviously, we have $$S(A)(S(A)-1)\equiv 0(\mathrm{mod}n).$$ (This is because of the selection of $x_i$, such that $S(A)(\mathrm{mod}{p}_i^{a_i})$ is either 0 or 1.) Moreover if $A\ne A^{\prime }$, then $S(A)\ne S(A^{\prime })(\mathrm{mod}n)$. Therefore, the sum of all subsets of $\{x_1,x_2,\dots ,x_n\}$ is exactly all solutions of $x(x-1)\equiv 0(\mathrm{mod}n)$. Let $S_0=n$, $S_r$ be the least non-negative remainder of $x_1+x_2+\cdots +x_r$ modulo $n$, $r=1,2,\dots ,k$. Thus $S_k=1$. For all $1\le r\le k-1$, $S_r\ne 0$. Since $k+1$ numbers $S_0,S_1,\dots ,S_k$ are in $[1,n]$, by Dirichlet's Drawer Principle, there exist $0\le l<m\le k$, such that $S_l,S_m$ in the same interval $\left(\frac{jn}{k},\frac{(j+1)n}{k}\right]$, $(0\le j\le k-1)$, where $l=0$ and $m=k$ do not hold simultaneously. Thus, $|S_l-S_m|<\frac{n}{k}$. Denote $y_1=S_1,y_r=S_r-S_{r-1}$ ($r=2,3,\dots ,k$). So any sum of $y_r\equiv x_r(\mathrm{mod}n)$ ($r=1,2,\dots ,k$) meets the requirement. If $S_m-S_l>1$, then $a=y_{l+1}+y_{l+2}+\cdots +y_m=S_m-S_l\in (1,\frac{n}{k})$ is the solution of the equation $x^2-x\equiv 0(\mathrm{mod}n)$. If $S_m-S_l=1$, then $n$ ($y_1+y_2+\cdots +y_l+(y_{m+1}+y_{m+2}+\cdots +y_k)$, that is, $n$ ($x_1+x_2+\cdots +x_l+(x_{m+1}+x_{m+2}+\cdots +x_k)$. Notice that $m>l$, which contradicts to the definition of $x_i$. If $S_m-S_l=0$, then $n\mid y_{l+1}+y_{l+2}+\cdots +y_m$, that is, $n\mid x_{l+1}+x_{l+2}+\cdots +x_m$, which contradicts the definition of $x_i$. If $S_m-S_l<0$, then $$\begin{array}{rl}a& =(y_1+y_2+\cdots +y_l)+(y_{m+1}+\cdots +y_k)\\ & =S_k-(S_m-S_l)=1-(S_m-S_l)\end{array}$$ is the solution of equation $x^2-x\equiv 0(\mathrm{mod}n)$, and $1<a<1+\frac{n}{k}$. Summing up, there exists $a$ satisfying the condition. $\square$