For which $n \in \mathbb{N}$ does $x^8 + [2]_nx^7+[6]_nx^6-x^2-[2]_nx - [6]_n = [0]_n$ have at least $7$ distinct solutions? I have to find one $n \in \mathbb{N}$ such that $$x^8 + [2]_nx^7+[6]_nx^6-x^2-[2]_nx - [6]_n = [0]_n$$ has at least $7$ distinct solutions in $\mathbb{Z}_n$ (or, equivalently, $f(x) = x^8 + [2]_nx^7+[6]_nx^6-x^2-[2]_nx - [6]_n \in \mathbb{Z}_n[x]$ has at least $7$ roots with multiplicity $1$). 
How do I approach such a problem?
 A: I think n=43 works. The roots are 1, 6, 7, 36, 37, 42, 8, and 33.
The first observation is that this polynomial factors over $\mathbb{Z}$ as $(x^6-1)(x^2+2x+6)$. We can actually go further and factor $(x^6-1)$ more, but I don't think it's necessary.
The next simplification is to just look for $n$ prime, in particular then the multiplicative group $\mathbb{Z}_n^\times$ is cyclic and has $6$ solutions to $x^6=1$ iff $n$ is $1 \text{ mod } 6$.
Okay so thats a good start, if we take primes congruent to $1 \text{ mod } 6$ we automatically get $6$ distinct roots. Now we just need to find such a prime where $(x^2+2x+6)$ has a solution which is not also a 6th root of unity.
From there could invoke some quadratic reciprocity arguments to conclude that $x^2+2x+6$ has a root mod $p$ if $p$ is congruent to $1, 3, 7, \text{ or } 9 \text{ mod } 20$, but its probably much faster (and what I did) to just check the first few primes congruent to $1 \text{ mod } 6$. We see that $x^2+2x+6$ factors mod $7$ but overlaps with the sixths roots of unity, the next case that works is $43$.
A: We can factor:
$f(x)=(x^6-1)(x^2+2x+6)$.
We are looking for an $n$ such that $\phi(n)=6k$ and such that $-5$ is a quadratic residue $\pmod n$. $21$ makes the job.
In fact $\phi(21)=12$ and thus $x^{12} \equiv 1 \pmod {21}$ has 12 solutions, in particular $6$ are good for us!
Solving the polynomial of degree $2$ we see that we would love to have a square root of $-5$. In our case $-5 \equiv 16 = 4^2 \pmod {21}$. Substituting $4$ inside the classical solution of a polynomial of degree $2$ We get two solutions $3$ and $-5$.
We now have $6$ different root and $2$ new roots. To see that they don't coincide just put for example $3$ inside $x^6-1$ and check that it is not $0$ in $\mathbb Z_{21}$.
I just noticed that $9$ is easier and smaller: in fact $\phi(9)=6$ and $-5 \equiv 4 = 2^2 \pmod 9$.
A: Hint We can proceed naively but efficiently. It is plausibly useful to factor $f(x)$ over $\Bbb Q$:
$$f(x) = (x^6 - 1)(x^2 + 2 x + 6),$$
and recalling our cyclotomic polynomials, we can easily factor the first factor, giving, respectively,
$$f(x) = (x - 1)(x + 1)(x^2 + x + 1)(x^2 - x + 1)(x^2 + 2 x + 6).$$
Obviously, we need $n \geq 7$.
On the other hand, we see that modulo $3$ all of the above factors factor especially nicely, and respectively into
$$x-1, \quad x + 1, \quad (x - 1)^2, \quad (x + 1)^2, \quad x(x - 1).$$

For each $x$ such that at least two of these factors are $0 \pmod 3$, the product of the corresponding terms in the factorization over $\Bbb Q$ is $0 \pmod 9$, and hence so is $p(x)$. By inspection, that condition holds when $x \equiv \pm 1 \pmod 3$, and hence $p(x) = 0 \pmod 9$ for $x = 1, 2, 4, 5, 7, 8$. Finally, we see that substituting $x = 6$ into $x^2 + 2 x + 6$ gives $0$ mod $9$, so $n = 9$ satisfies the criterion.

