Number of solutions of polynomials in a field

Question

Consider the polynomial $x^2+x=0$ over $\mathbb Z/n\mathbb Z$

a)Find an n such that the equation has at least 4 solutions

b)Find an n such that the equation has at least 8 solutions

My idea is to check individual n, and I found the answer for a is n=6 at x={0,2,3,5} f(x)={0, 6, 12, 30)

Is there any shorter way?

Answer 1

Look at the structure of this $x(x+1)=0$.

This will always have the solutions $x=0$ and $x=-1=n-1$ and if $n$ is prime that will be all.

But if neither factor is zero, the ring will have zero divisors in it, and you are looking at two consecutive zero divisors, one even and one odd. So the first thing to test is $2 \times 3$, and that works as does $-2\times -3$ which is $4\times 3 \mod 6$.

You will need to think a little harder to find an example with eight solutions.

Answer 2

If $n$ is not the power of a prime there are solutions distinct from $0$ and $-1$.

Indeed, in this case you can write $n=ab$ where $a$ and $b$ are coprime. Bezout's identity gives: $$ax+by=1$$ That means that there are two consecutive integers, one of them is a multiple of $a$ and the other a multiple of $b$. This gives you a solution of the equation. And for each possible factorization $n=ab$ there is at least another solution.

Answer 3

Let $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where the $p_i$ are distinct primes and the $a_i$ are $\ge 1$.

Consider the system of congruences $x\equiv e_i \pmod{p_i^{a_i}}$ ($i=1$ to $k$) where the $e_i$ can be either $0$ or $-1$. There are $2^k$ such systems.

By the Chinese Remainder Theorem, the above system of congruences has a unique solution modulo $n$.

If $x$ is any such solution, then $x(x+1)\equiv 0\pmod{p_i^{a_i}}$, and hence modulo $n$. Conversely, if $x(x+1)\equiv 0\pmod{n}$, then $x(x+1)\equiv 0\pmod{p_i^{a_i}}$. But any solution of the congruence modulo $p_i^{a_i}$ must be congruent to $0$ or $-1$ modulo $p_i^{a_i}$.

It follows that our congruence has precisely $2^k$ solutions modulo $n$.

For exactly $8$ solutions, we can therefore use $n=(2)(3)(5)$, or any other positive integer with three distinct prime factors.