Given $n$, is it possible to upper bound the smallest $x > 1$ that satisfies the congruence $x^2 \equiv x\pmod{n}$? Obviously when $n$ is a prime power $x = n$, and we are in the worst situation. However for other $n$ we can make $x \leq \frac{n}{2}$. Perhaps better bounds can be obtained if we know that $n$ has more prime factors. 



Smallest solution to $x^2 \equiv x\pmod{n}$
We may really get better estimates if $n$ have at least three prime divisors, like, say $0<x\leqslant n/3$. 


If $n=\prod q\_i$ for prime powers $q\_i$, denote by $u\_i$ a solution which is 1 modulo $q\_i$ and 0 modulo all $q\_j,j\ne i$. Assume that they all belong to $(n/3,2n/3)$ (if $2n/3<u\_i<n$, then $n/3>n-1-u\_i>0$ as we need). Then $u\_1+u\_2\in (2n/3,n-1)$ (case $u\_1+u\_2=n-1$ is impossible since $u\_1+u\_2$ is divisible by $q\_3$), take a solution $n-1-u\_1-u\_2$.


**Update.** David Speyer shows in his answer that this may be generalized to the estimate $(n-1)/k$ for $n$ having $k$ distinct prime divisors. Let me show that the constant $1/k$ can not be improved for a fixed $k$. Fix $k\geqslant 2$. We need a 


**Lemma.** For any $m\geqslant 1$ there exist (arbitrarily large) primes $p\_1,\dots,p\_m$ congruent to 1 modulo $k$ such that $\frac{p\_i-1}k \prod\_{j\ne i} p\_j\equiv 1\pmod {p\_i}$ for all $i=1,2,\dots,m-1$.


**Proof.** Induction in $m$. Base $m=1$ is formally trivial (take any $p\_1$ congruent to 1 modulo $k$). Induction step from $m$ to $m+1$. Take $p\_{m+1}$ congruent to 1 modulo $kp\_1\dots p\_{m-1}$ and to $-k/p\_1\dots p\_{m-1}$ modulo $p\_m$. This is possible by Dirichlet theorem (and Chinese Remainders Theorem.)


Use this lemma for $m=k$ and choose primes $p\_1,\dots,p\_k$ satisfying conditions of lemma, set $n=p\_1\dots p\_k$. Then $u\_i=\frac {p\_i-1}{k}\cdot \frac{n}{p\_i}$ are our $u\_i$'s for $i=1,2,\dots,k-1$, $u\_k=1-(u\_1+\dots+u\_{k-1})$. They are all pretty close to $n/k$, thus for any $I\subset \{1,\dots,k\}$, $0<|I|<k$, we have $\sum\_{i\in I} U\_i$ is close to $|I|\cdot n/k$,so, we do not have solution of $x^2\equiv x \pmod n$ much less than $n/k$.


