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

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.

• For $n=k(k+1)$ one evidently has $x\leq 1/2+\sqrt{n+1/4}$ for $x=k+1$. – KFabian Jun 20 '16 at 14:06
• On the other hand, for arbitrary $n$ we have the lower bound $x\ge1/2+\sqrt{n+1/4}$. – Emil Jeřábek 3.0 Jun 20 '16 at 14:22
• 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? – Kimball Jun 20 '16 at 16:55
• There is a nontrivial solution by the Chinese Remainder Theorem. Moreover, each solution $x$ is paired with another solution $1-x$, that is, $n+1-x$, so one of those satisfies $1<x<n+1-x$, i.e., $x\le n/2$. – 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>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$.

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

• 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. – 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 $(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$).

• Nice! This looks to be essentially sharp, and even strong conjectures like twin primes are not necessary, see update to my answer. – Fedor Petrov Jun 20 '16 at 21:58
• strictly speaking, this is not $\leqslant (n-1)/k$, but $\leqslant (n-1)/k+1$, since our small positive idempotent is either $f_j-f_i$ or $1-(f_j-f_i)$. – Fedor Petrov Oct 6 '16 at 4:38

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.