The polynomial $x^3-1$ over $\mathbb{Z}_p$, where $p$ is a prime, factors as $(x-1)(x^2+x+1)$.
The polynomial $x^7-1$ over $\mathbb{Z}_{13}$ factors as, $(x-1)(x^2+3x+1)(x^2+5x+1)(x^2+6x+1)$.
All these $(x-1),(x^2+x+1),(x^2+3x+1),(x^2+5x+1),(x^2+6x+1)$ are irreducible factors.
Does a polynomial $x^q-1$ over $\mathbb{Z}_p$, where $p,q$ are primes ($q<p$), always factorize to $(x-1)$ times several quadratic factors of the form $(x^2+ax+1)$, where $a \in \mathbb{Z}_p$? (a quadratic factor with constant term "1"?)
Thanks a lot in advance.
No. For example, $x^7 - 1 = (x-1)(x^6+x^5+ x^4+x^3+x^2+x+1)$ modulo $19$ as a product of irreducible factors. It is easy to see that $x-1$ is always a factor, but from that point on I think more specific conditions may be required on $p$ and $q$ ($q<p$ seems arbitrary in this respect) for this breakup to occur.
Note : Showing explicitly that the sixth degree polynomial is irreducible requires Galois theory.
We will use the demonstration in the comments for this purpose. We wish to show that $$ x^6+x^5+ x^4+x^3+x^2+x+1 $$
is irreducible modulo $19$. Note that a root of this polynomial can be found in a finite field extension of $\mathbb F_{19}$, which will be of the form $\mathbb F_{19^m}$ for some $m$.
However, any root of this polynomial will also satisfy $x^7 = 1$, therefore we are ask : for which $m$ is there a non-unit $x$ such that $x^7 = 1$ as elements of $\mathbb F_{19^m}$?
If there is such an element $x$, then $7$ must divide $19^m-1$. Conversely, because $7$ is prime, $7$ dividing $19^m-1$ implies the converse by Cauchy's theorem. Therefore, the question now is : which $m$ are such that $7$ divides $19^m-1$?
One can easily check that the set of all such $m$ is of the form $n\mathbb N$ for $n$ being the possible smallest value of $m$. Combining Euler's theorem with a few simple tests, one sees that $m$ can be any multiple of $6$.
So, any root of $x^6+x^5+\ldots+1 = 0$ must then lie in an extension of degree at least $6$. However, because the degree of this polynomial is also at most $6$, it follows that the root lies in an extension of degree $6$, and therefore $x^6+x^5+\ldots+1$ is its minimal polynomial, hence irreducible over $\mathbb F_{19}$.