Return to Answer

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

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

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

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

We may really get better estimates if $n$ have at least three odd 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$.

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