1

I have been looking at $x^2 - x \equiv 0 \pmod 6$. Factoring $x^2 - x$ yields:

$$x^2-x = x(x-1)$$

Solving $x(x-1) \equiv 0 \pmod 6$ implies $x \equiv 0$ or $x \equiv 1 \pmod 6$. However, these are not all the solutions. As it turns out, $x \equiv 3$ and $x \equiv 4 \pmod 6$ are also solutions. Plugging $3$ and $4$ it is easy to see that indeed $4 \cdot 3 \equiv 0 \pmod 6$.

However, it is not immediately obvious. My question is how to find these non-trivial solutions? Is there a good technique? What if $6$ was replaced by a relatively larger composite number? I can see solving the equations in prime factors could be one way. But I am interested to know if there are methods without needing to find prime factors.

Josh
  • 1,086
  • 4
  • 15
  • No, $x(x-1)\equiv 0$ does not mean $x\equiv 0$ or $x\equiv 1.$ The reason this is true for real numbers is that if $ab=0,$ then either $a=0$ or $b=0.$ But that isn’t true for $\equiv\pmod 6.$ – Thomas Andrews Aug 14 '21 at 02:44
  • The claim $x(x-1)=0$ iff $x=0$ or $x-1=0$ works only if the space you're working on is an integral domain (no zero divisors). Working with $\Bbb Z_n$ (or $\Bbb Z/n\Bbb Z)$, this is true iff $n$ is prime. – Prasun Biswas Aug 14 '21 at 02:46
  • 1
    Solve separately $x^2-x\equiv 0\pmod 2$ and $x^2-x\equiv 0\pmod 3.$ Then use Chinese remainder theorem to put together $$x\equiv a\pmod2\x\equiv b\pmod 3$$ for $a$ a root modulo $2$ and $b$ a root modulo $3.$ – Thomas Andrews Aug 14 '21 at 02:47
  • You don't necessarily have to break down the modulus into prime factors, breaking it into pairwise coprime factors would suffice. Then, you can use the Chinese Remainder Theorem, utilising the fact that $\gcd(x,x-1)=1$ to break the congruence into cases with simultaneous congruences. – Prasun Biswas Aug 14 '21 at 02:49
  • I specified in my question that I am not interested in solutions that are concerned with prime factors. coprime factors also make use of prime factorization. If this problem cannot be solved without looking into prime factors, please say so. – Josh Aug 14 '21 at 04:29
  • and it is true that $x(x-1) \equiv 0$ does not necessarily mean $x \equiv 0$ or $x \equiv 1$ in this case. But these are trivial solutions and that is the sense in which I used "imply". Sorry that I did not make that clear. – Josh Aug 14 '21 at 04:33
  • Brute with the realization that $-x,x$ can't both be a solution in most cases. – Roddy MacPhee Aug 14 '21 at 15:17

1 Answers1

0

Prime factorization is required for finding all solutions.

As pointed out in the comments, if we know the prime factorization of $n$, then we can find the solutions of $x^2 - x \equiv 0 \pmod n$ using the Chinese remainder theorem. For example, if $n$ is a semiprime $pq$, then the four solutions are $x \equiv 0, 1, p^{q-1}, q^{p-1} \pmod n$.

Conversely, if we know one of the nontrivial solutions $x \not\equiv 0, 1 \pmod n$, then $\gcd(x, n)$ is a nontrivial factor of $n$. So any algorithm for finding these solutions is effectively an algorithm for factoring $n$.

Anders Kaseorg
  • 8,377