10
$\begingroup$

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.

$\endgroup$
  • $\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 $1-x$, that is, $n+1-x$, so one of those satisfies $1<x<n+1-x$, i.e., $x\le n/2$. $\endgroup$ – Emil Jeřábek 3.0 Jun 20 '16 at 17:03
6
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • 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
6
$\begingroup$

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

$\endgroup$
  • $\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 (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)$. $\endgroup$ – Fedor Petrov Oct 6 '16 at 4:38
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.