Using Chinese Remainder Theorem to prove existence of nontrivial idempotents $\!\bmod n$ The question goes like this: use the CRT to prove that if an integer $n>1$ is not a power of a prime, then there exists an integer $x$ such that $n|(x^{2}-x)$ but $n$ does not divide $x$ nor $x-1$. I can see this working with a simple example like $n=12$, which lets $x=4,-3$. I got this by using $n|(x^{2}-x)$ to imply $x^{2}-x-nk=0$ but I cannot see to proving this with the CRT in particular. Any help is appreciated.
 A: Suppose that $n$ is not a prime power. Then $n=ab$ for some relatively prime
numbers $a$ and $b$, both greater than $1$.
By the Chinese Remainder Theorem, there exists an integer $x$ such that 
$x\equiv 0\pmod{a}$ and $x\equiv 1\pmod{b}$. Thus $a$ divides $x$ and $b$ divides $x-1$. It follows that $ab$ divides $x(x-1)$.  Note that $ab$ does not divide $x$, for $b$ divides $x-1$, and therefore $b$ and $x$ are relatively prime. Similarly, one can show that $ab$ does not divide $x-1$. 
A: Hint $\bmod n\,$ we seek a solution of $\ x(x-1)\equiv 0\ $ but $\,x\not\equiv 0,1.\, $ If $\,n = p^k\,$ is a prime power we get only trivial solutions: $\,p^k\mid x(x-1)\,$ $\Rightarrow\,p^k\mid x\,$ or $\,p^k\mid x-1\,$ by $\,x,\,$ $\,x-1\,$ coprime. Else $\,n\,$ is not a prime power so we can write $\,n = ab\ $ with coprime $\,a,b>1.\,$ What happens when we CRT lift the solutions $\, x\equiv 0,1\,$ mod $\,a,b\,$ to four solutions mod $\,n\,?$ The solutions $\,x\equiv (0,0),(1,1)\,$ mod $\,(a,b)\,$ map to $0,1\,$ mod $ab,\,$ but the solutions $\,(0,1),(1,0)\,$ mod $\,(a,b)\,$ map to values $\not\equiv 0,1\,$ mod $\,ab.$
Remark $\ $ Elements satisfying $\,x^2 = x\,$ (and $\,\color{#c00}{x\neq 0,1})$ are called $\rm\color{#c00}{(nontrivial)}$ idempotents. They are intimately connected to coprime factorizations (of both elements and rings). As we see above, modulo any non-prime-power composite $\,n,\,$ there are nontrivial idempotents $\,(0,1),(1,0).$ 
Some integer factorization algorithms work by searching for nontrivial idempotents mod $\,n,\,$ which immediately yield a factorization of $\,n\,$ (generally one can quickly factor $\,n\,$ given any polynomial which has more roots mod $\,n\,$ than its degree, so any notrivial idempotent or nontrivial square-root will split $\,n,\,$ since it yields a quadratic with $3$ roots).
