Smallest solution to $x^2 \equiv x\pmod{n}$

Question

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.

Answer 1

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$.

Answer 2

If there are infinitely many twin primes, then we can't do much better than $n/2$. If $q=2k-1$ and $p = 2k+1$ are primes, then the solutions to $x^2\equiv x \bmod pq$ are $0$, $1$, $k(2k-1) \approx (pq)/2 - \sqrt{pq}$ and $k(2k+1) \approx (pq)/2 + \sqrt{pq}$.

Answer 3

Building on Fedor Petrov's answer, if $n$ has $k$-distinct factors, we can find a solution below $(n-1)/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_j-f_i| \leq (n-1)/k$. (We have $k+1$ numbers in $\{ 1,2,\ldots, n \}$, so the closest two differ by at most $(n-1)/k$.) Then $f_j-f_i \equiv e_j+e_{j-1}+\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_k-f_0| = n-1$).

Answer 4

Given any odd prime $p$, let $r=\lfloor p/2\rfloor-1$. 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.