# Prove that there exists a positive integer $a$ such that $n|a^2-a$

Let $n$ be a positive integer with $k$ distinct prime divisors. Prove that there exists a positive integer $a$ with $1<a<\frac{n}k+1$ such that $n|a^2-a$

I can't solve it. Could someone help me?

• Trivial observation: if $n$ is a prime power then we can take $a=n$. – Dietrich Burde Jan 5 '18 at 19:18
• @DietrichBurde Now Chinese remainder. – orole Jan 5 '18 at 19:19

Let $n=\prod _{i=1}^kp_i^{c_i}$ with $c_i\ge 1$. Fix $j\in\{0,\ldots,k\}$. Then we can find $a_j\in\{1,\ldots,n\}$ with $a_j\equiv 1\pmod {p_i^{c_i}}$ for $i\le j$ and $a_j\equiv 0\pmod {p_j^{c_j}}$ for $i>j$.
If we order the $k+1$ distinct numbers $a_j$ in ascending order (apparently staring with $a_k=1$ and ending with $a_0=n$), there must be two consecutive terms $a_r,a_s$ in this sequence with $0<a_s-a_r\le\frac{n-1}{k}$. Let $\tilde a=a_s-a_r$.
First assume $s>r$. Then neither of $r,s$ is $=0$, hence $p_1^{c_1}\mid \tilde a$. In particular, $\tilde a>1$. We have $\tilde a\equiv 1\pmod {p_i^{c_i}}$ for $r<i\le s$ and $\tilde a\equiv 0\pmod {p_i^{c_i}}$ otherwise. We conclude that $\tilde a(\tilde a-1)\equiv 0\pmod n$. As $\frac{n-1}k<\frac nk+1$, we find a solution by letting $a=\tilde a$.
Next assume $s<r$. As above, we have $\tilde a\equiv 0\text{ or }{-1}\pmod {p_i^{c_i}}$ for all $i$, hence $\tilde a(\tilde a+1)\equiv 0\pmod n$. So if we let $a=\tilde a+1>1$, we have $a(a-1)\equiv 0\pmod n$. Also, $a\le \frac{n-1}k+1<\frac nk+1$, hence this $a$ has the desired properties.