Let n=p1a1⋯pkak be the standard factorization of n. Since p1a1,…,pkak are pairwise coprime, by the Chinese Remainder Theorem, for each i, 1≤i≤k, congruence equations
{x≡1(modpiai)x≡0(modpjaj),j=i
have solution xi.
For any solution of x02=x0(modn), we see that x0(x0−1)≡0(modn). Then for each i=1,2,…,k, either x0≡0(modpiai) or x0≡1(modpiai). Further, let S(A) be the sum of elements of subset {x1,x2,…,xk} (particularly, S(∅)=0). Obviously, we have
S(A)(S(A)−1)≡0(modn).
(This is because of the selection of xi, such that S(A)(modpiai) is either 0 or 1.) Moreover if A=A′, then S(A)=S(A′)(modn). Therefore, the sum of all subsets of {x1,x2,…,xn} is exactly all solutions of x(x−1)≡0(modn).
Let S0=n, Sr be the least non-negative remainder of x1+x2+⋯+xr modulo n, r=1,2,…,k. Thus Sk=1. For all 1≤r≤k−1, Sr=0. Since k+1 numbers S0,S1,…,Sk are in [1,n], by Dirichlet's Drawer Principle, there exist 0≤l<m≤k, such that Sl,Sm in the same interval (kjn,k(j+1)n], (0≤j≤k−1), where l=0 and m=k do not hold simultaneously.
Thus, ∣Sl−Sm∣<kn. Denote y1=S1,yr=Sr−Sr−1 (r=2,3,…,k). So any sum of yr≡xr(modn) (r=1,2,…,k) meets the requirement.
If Sm−Sl>1, then a=yl+1+yl+2+⋯+ym=Sm−Sl∈(1,kn) is the solution of the equation x2−x≡0(modn).
If Sm−Sl=1, then n (y1+y2+⋯+yl+(ym+1+ym+2+⋯+yk), that is, n (x1+x2+⋯+xl+(xm+1+xm+2+⋯+xk). Notice that m>l, which contradicts to the definition of xi.
If Sm−Sl=0, then n∣yl+1+yl+2+⋯+ym, that is, n∣xl+1+xl+2+⋯+xm, which contradicts the definition of xi.
If Sm−Sl<0, then
a=(y1+y2+⋯+yl)+(ym+1+⋯+yk)=Sk−(Sm−Sl)=1−(Sm−Sl)
is the solution of equation x2−x≡0(modn), and 1<a<1+kn.
Summing up, there exists a satisfying the condition. □