Skip to main content
MathOverflow

Return to Question

added 2 characters in body
Source Link
Mikhail Katz
Mikhail Katz
  • 16.6k
  • 2
  • 54
  • 127

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.

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

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.

fix mod latex
Source Link
Arturo Magidin
Arturo Magidin
  • 7.2k
  • 1
  • 42
  • 60

Smallest solution to $x^2 \equiv x~(mod~n)x\pmod{n}$

Given $n$, is it possible to upper bound the smallest $x > 1$ that satisfies the congruence $x^2 \equiv x~(mod~n)$$x^2 \equiv x\pmod{n}$? Obviously when $n$ is 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.

Smallest solution to $x^2 \equiv x~(mod~n)$

Given $n$, is it possible to upper bound the smallest $x > 1$ that satisfies the congruence $x^2 \equiv x~(mod~n)$? Obviously when $n$ is 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.

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

Source Link
Xiaosheng Mu
Xiaosheng Mu
  • 765
  • 3
  • 12

Smallest solution to $x^2 \equiv x~(mod~n)$

Given $n$, is it possible to upper bound the smallest $x > 1$ that satisfies the congruence $x^2 \equiv x~(mod~n)$? Obviously when $n$ is 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.