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.

$\begingroup$ For $n=k(k+1)$ one evidently has $x\leq 1/2+\sqrt{n+1/4}$ for $x=k+1$. $\endgroup$ – KFabian Jun 20 '16 at 14:06

$\begingroup$ On the other hand, for arbitrary $n$ we have the lower bound $x\ge1/2+\sqrt{n+1/4}$. $\endgroup$ – Emil Jeřábek 3.0 Jun 20 '16 at 14:22

$\begingroup$ Based on a small amount of numerical calculations, this may indeed be possible. What is your argument to get $x \le \frac n2$ when $n$ has at least 2 prime factors? $\endgroup$ – Kimball Jun 20 '16 at 16:55

$\begingroup$ There is a nontrivial solution by the Chinese Remainder Theorem. Moreover, each solution $x$ is paired with another solution $1x$, that is, $n+1x$, so one of those satisfies $1<x<n+1x$, i.e., $x\le n/2$. $\endgroup$ – Emil Jeřábek 3.0 Jun 20 '16 at 17:03
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>n1u_i>0$ as we need). Then $u_1+u_2\in (2n/3,n1)$ (case $u_1+u_2=n1$ is impossible since $u_1+u_2$ is divisible by $q_3$), take a solution $n1u_1u_2$.
Update. David Speyer shows in his answer that this may be generalized to the estimate $(n1)/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_i1}k \prod_{j\ne i} p_j\equiv 1\pmod {p_i}$ for all $i=1,2,\dots,m1$.
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_{m1}$ and to $k/p_1\dots p_{m1}$ 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_i1}{k}\cdot \frac{n}{p_i}$ are our $u_i$'s for $i=1,2,\dots,k1$, $u_k=1(u_1+\dots+u_{k1})$. 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$.
If there are infinitely many twin primes, then we can't do much better than $n/2$. If $q=2k1$ and $p = 2k+1$ are primes, then the solutions to $x^2\equiv x \bmod pq$ are $0$, $1$, $k(2k1) \approx (pq)/2  \sqrt{pq}$ and $k(2k+1) \approx (pq)/2 + \sqrt{pq}$.

3$\begingroup$ Even without twin primes, there are infinitely many $n$ where the least $x$ is exactly $n/2$: namely, $n=2p$ for $p$ an odd prime (or prime power). However, I thought the question asked for better bounds if there are more prime factors. $\endgroup$ – Emil Jeřábek 3.0 Jun 20 '16 at 16:10
Building on Fedor Petrov's answer, if $n$ has $k$distinct factors, we can find a solution below $(n1)/k$. Let $n=q_1 q_2 \cdots q_k$, with $q_i$ prime powers. Let $e_i$ be $1$ modulo $q_i$ and $0$ modulo $q_j$ for $j \neq i$. Let $f_j$ lie in $\{ 1,2,\ldots, n \}$ and be congruent to $e_1+e_2+\cdots+e_j \bmod n$. So $e_0=n$ and $e_n=1$. Then there must be some $i < j$ with $f_jf_i \leq (n1)/k$. (We have $k+1$ numbers in $\{ 1,2,\ldots, n \}$, so the closest two differ by at most $(n1)/k$.) Then $f_jf_i \equiv e_j+e_{j1}+\cdots+e_{i+1}$ is an idempotent, and it is not $0$ (since $i \neq j$) nor $1$ (that could only happen if $j=k$ and $i=0$, but then $f_kf_0 = n1$).

$\begingroup$ Nice! This looks to be essentially sharp, and even strong conjectures like twin primes are not necessary, see update to my answer. $\endgroup$ – Fedor Petrov Jun 20 '16 at 21:58

$\begingroup$ strictly speaking, this is not $\leqslant (n1)/k$, but $\leqslant (n1)/k+1$, since our small positive idempotent is either $f_jf_i$ or $1(f_jf_i)$. $\endgroup$ – Fedor Petrov Oct 6 '16 at 4:38
Given any odd prime $p$, let $r=\lfloor p/2\rfloor1$. We work in $\mathbb{Z}_p^\ast$ and consider the elements $\pm 1,\pm 1/2,\pm 1/3,\ldots \pm 1/r$. By the pigeonhole principle there is a residue $\bar q$ which is not on the list. We then use Dirichlet to find a prime $q\in\mathbb{N}$ congruent to $\bar q$ modulo $p$. Then letting $n=pq$, we see that we can't improve the $\frac{n}{2}$ bound significantly for a product of two primes.
For a product of three primes e.g., $2pq$, we can do a little better because solving the problem for $n=pq$ automatically produces a solution for $2pq$ as well.