Let $q$ be a prime power and $n$ a positive integer s.t. $\gcd(n, q) = 1$. Let $E(n)$ be the set of the complex $n$-th roots of unity. For every positive integer $d$ such that $d | n$ , let

$$Q_d(x) := \prod_{\alpha \in E(n):\mathrm{ord}(\alpha)=d} (x- \alpha)$$

Why does follow from this that

$$x^n-1 = \prod_{d |n} Q_d(x)$$

  • 3
    $\begingroup$ where exactly does q appear in your question? Does it have any relevance? $\endgroup$ – Pink Panther Mar 28 at 11:09
  • $\begingroup$ Is that over $\mathbb C$ ? $\endgroup$ – lhf Mar 28 at 11:55
  • $\begingroup$ If two polynomials have leading coefficient $1$ and have the same roots, they have to be equal. $\endgroup$ – D_S Mar 28 at 13:19
  • $\begingroup$ @D_S Only if the multiplicities of all of the roots are the same. $\endgroup$ – Morgan Rodgers Mar 30 at 16:39

I don't know how your $q$ needs to be in the mix there but let me elaborate the other things a little bit. We will need a little bit of group theory and some facts from complex analysis.

A complex $n$-th root of unity is a solution to the equation $z^n=1$. That is, it is a root of the complex polynomial $z^n-1$. Lets call the set of all such roots $E(n)$. This set forms a group w.r.t. to complex multiplication (note that $1$ is an $n$-th root of unity for every $n$). Now, by the Fundamental Theorem of Algebra, there are at most $n$ distinct $n$-th roots of unity as $z^n-1$ is a polynomial of degree $n$ and you can actually show that there are exactly $n$, i.e. $|E(n)|=n$.

I don't go into the details now, but you can express them as values of the exponential function.

Every such root $\lambda\in E(n)$ can be given an order $\mathrm{ord}(\lambda)\in\mathbb N$ which is the smallest $m$ such that $\lambda^m-1=0$, i.e. the degree of the polynomial of which it was first introduced as new root of unity.

E.g. note that $-1$ is a 4th root of unity but however it was already a 2nd root of unity and will be an $n$-th root of unity for every even $n$. Thus $\mathrm{ord}(\lambda)=2$ although $\lambda\in E(4)$ as well.

Now, taking an $n$-th root of unity $\lambda$, you have that the set


forms a cyclic group generated by $\lambda$ with respect to complex multiplication. You can easily verify the closure of this under multiplication as $\lambda^{\mathrm{ord}(\lambda)}=1$.

Now, as $\lambda\in E(n)$ and $E(n)$ is itself a group w.r.t. complex multiplication, we have that

$$\{\lambda,\lambda^2,\dots,\lambda^{\mathrm{ord}(\lambda)}\}\subseteq E(n)$$

i.e. it forms a subgroup of $E(n)$. We now recite Lagrange's theorem from group theory:

Let $G$ be a finite group and $U$ a subgroup of $G$ (thus necessarily finite), then $|U|$ divides $|G|$.

We thus have, that $\mathrm{ord}(\lambda)=|\{\lambda,\lambda^2,\dots,\lambda^{\mathrm{ord}(\lambda)}\}|$ divides $n$.

Thus, every $n$-th root of unity has an order and every such order divides $n$.

Again, by the Fundamental Theorem of Algebra, we have that

$$z^n-1=\prod_{\lambda\in E(n)}(z-\lambda)$$

i.e. we can split the polynomial into linear factors of its roots and the $(z-\lambda)$ are pairwise distinct. If we define the polynomials

$$Q_d(z)=\prod_{\lambda\in E(n):\mathrm{ord}(\lambda)=d}(z-\lambda)$$

for every $d$ dividing $n$, then we naturally get

$$z^n-1=\prod_{d\mid n}Q_d(z)$$

as every such $(z-\lambda)$ occurs in exactly one $Q_d(z)$ once from the considerations before, where $d=\mathrm{ord}(\lambda)$ divides $n$.

A little fact, which is of no direct relation to your question but I really like mentioning it, is that understanding this formula

$$z^n-1=\prod_{d\mid n}Q_d(z)$$

is one of three steps towards a relatively simple proof of a fascinating theorem from abstract algebra which is:

Every finite division ring is a field.

i.e. in every finite division ring the multiplication operation is necessarily commutative. This is known as Wedderburn's little theorem and see this if it spiked you interest.

  • $\begingroup$ WOW! Thank you very, very much for this phenomenal answer! $\endgroup$ – JohnD Mar 29 at 16:38
  • $\begingroup$ @JohnD I'm flattered, you're very welcome. $\endgroup$ – blub Mar 29 at 16:48

There are essentially $3$ relatively straightforward facts (and one complicated one) required to draw the required conclusion.

The first is that if $\alpha ^n-1=0$, $ord(\alpha)\mid n$.

This is a direct consequence of Euclid's division lemma/ the division algorithm and the definition of the order of the element- the order of an element, $\alpha$, is defined as the smallest positive integer, $m$, such that $\alpha^m=1$ (in this context). Suppose then that we are given an $n$ such that $\alpha^n-1=0$. $n$ is just an integer and $ord(\alpha)$ is just some positive integer so we may use the division algorithm to write $n=ord(\alpha)k+r$ where $k$ is an integer and $r$ is an integer such that $0\leq r<ord(\alpha)$.
But this gives us that $$\alpha^n=1\implies \alpha^{ord(\alpha)k+r}=1\implies (\alpha^{ord(\alpha)})^k\alpha^r=1\implies (1)^k\alpha^r=1\implies\alpha^r=1$$
And so, if $r$ were any non-zero number we would have a contradiction as $r$ is a positive integer that is $<ord(\alpha)$ but we still have $\alpha^r=1$ despite the fact that $ord(\alpha)$ was itself defined to be the smallest such positive integer- it follows that $r$ must be $0$ and so, if $\alpha^n-1=0$, $ord(\alpha)\mid n$.

The second important fact is that if $r$ is a root of the polynomial $p(x)$, then $(x-r)$ divides $p(x)$

This results, likewise, from the division algorithm but this time for polynomials. Suppose $p(x)$ has a root $r$. We consider the division algorithm applied to $p(x)$ with a divisor of $(x-r)$. $$p(x)=(x-r)q(x)+t(x)$$ where $t(x)$ is either the $0$ polynomial or $t(x)$ has order strictly less than that of $(x-r)$. If $t(x)$ is the $0$ polynomial, we are done. Otherwise, we note that since $(x-r)$ is of degree $1$, $t(x)$ must be of degree $0$, i.e. a constant polynomial so $t(x)=t$. $$p(x)=(x-r)q(x)+t$$ But if we plug $r$ into the above equation. we get $$p(r)=0\implies (r-r)q(r)+t=0\implies t=0$$ which contradicts the assumption that $t(x)$ was not the zero polynomial. Hence, if $r$ is a root of $p(x)$, $(x-r)$ divides $p(x)$.

The third is that any polynomial in the polynomial ring, $F[X]$ of a field, $F$, has a root in a suitable field extension, $K\supset F$ OR just The Fundamental Theorem of Algebra .

This is the one slightly complicated bit- the main purpose of this is that it allows us to say that $x^n-1$ has roots. More technically, a field is basically a set of elements with operations of addition, multiplication, division, etc. defined so that they have all the nice properties we see in things like standard addition or multiplication on the reals (like commutativity and distributivity). The bit above in bold before the "OR" basically states that for any polynomial, $s(x)$, with coefficients in some field, $F$, there exists another field, $K$, such that $K\supset F$ and a root of $s(x)$ lies in $K$. Since each field has a multiplicative identity, the roots of $x^n-1$ have the same basic algebraic properties in all fields so one can simply refer to the FTA instead. It may also seem rather odd to bring up the statement about field extensions given that it seems to be more general than the FTA (making a claim about all fields instead of just $\mathbb C$) but the FTA's strength comes from its claim about that $\mathbb C$ is algebraically closed- the statement about fields in general doesn't tell you where the root will be, effectively- just that one exists. The FTA, on the other hand, tells you both that the roots will exist and that they will lie $\mathbb C$ but this result clearly isn't a general one. This is why, in a sense, the FTA is stronger and also why its proof necessarily involves a topological element. If you know a bit about polynomial rings, you can find a sketch of the ideas in the question and answer here

The reason this is important is that it tells us that any polynomial can be factored as $\prod_{r\in ROOTS} (x-r)^{m_r}$ where $m_r$ is the multiplicity of each root and $ROOTS$ is the set of all roots of the polynomial. We can see this by using the third fact- $p(x)$ has a root, $r_1$, (in some suitable extension or in just $\mathbb C$ if you like). The third fact tell us we can write $p(x)$ as $(x-r_1)q_1(x)$. $q_1(x)$ is a new polynomial- it too has some root, $r_2$ so we may write $p(x)=(x-r_1)((x-r_2)q_2(x))=(x-r_1)(x-r_2)q_2(x)$. We keep repeating this process- we stop at exactly the $deg(p(x))$th step because the degree of each $q_r(x)$ is less than the degree of each $q_{r-1}(x)$ and so $q_{deg(p(x))-1}$ will be linear. It may, of course, be the case that some $r_k$ equals some $r_j$ in which case the multiplicity of the root $r_j=r_k$ is greater than one- this manifests as the power of each term in the product ($ROOTS$ is a set).

The final important fact is that $x^n-1$ never has repeated roots

The three facts above this one tell us that we can write $x^n-1$ as $\prod_{r\in ROOTS}(x-r)$ but there is something we must be careful of- the possibility of $x^n-1$ having repeated roots. The third fact assured us that any polynomial will always have some root, and, hence, that it can be factored as a product of linear polynomials in its roots but there was no assurance that those roots need be distinct (as mentioned before). For instance, the polynomial $x^3-8x^2+21x-18$ factors as $(x-3)^2(x-2)$. Can something like this happen with $x^n-1$? As it turns out, no. This is a result of a property of repeated roots and how they affect the relationship between a polynomial and its formal derivative. Simply put, the formal derivative of a polynomial $$a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$$ is $$na_nx^{n-1}+(n-1)a_{n-1}x^{n-2}+...+2a_2x+a_1$$ The benefit of using the formal derivative lies in the many properties it inherits from the calculus-style definition of a derivative (the sum rule, the product rule, etc.) but it is, of course, a formal operation on polynomials over rings rather than the limit of a quotient. The key fact here is that, if a polynomial has no factor of degree at least $1$ in common with its formal derivative, it has no repeated roots. The contrapositive of this is fairly simple- if $p(x)$ has a repeated root $r$, then we may write $p(x)=(x-r)^2q(x)$ for some $q(x)$. By the properties of the formal derivative, $p'(x)=(x-r)^2q'(x)+2(x-r)q(x)$ so that $x-r$ is a factor with degree $\geq 1$ of both $p(x)$ and $p'(x)$. In the case of $x^n-1$, our formal derivative is $nx^{n-1}$ which clearly has no factor of degree $\geq 1$ in common with $x^n-1$, giving us that $x^n-1$ has distinct roots.

The problem at hand

Now, we turn our attention to the product in the question. By the first fact, each root of $x^n-1$ has an order that divides $n$. This means, for any root $r$ of $x^n-1$, the polynomial $x-r$ appears at least once among all the $Q_d(x)$'s. Then, since each root, $r$, of $x^n-1$ has a unique order (by the definition of an element's order), each $x-r$ occurs exactly once among all the $Q_d(x)$. This gives us that $Q_d(x)=\prod_{r\in ROOTS, \\distinct} (x-r)$.

By fact three, $x^n-1$ can be written as $\prod_{r\in ROOTS}(x-r)^{m_r}$ where $m_r$ is the multiplicity of each root. Finally, by fact four the multiplicity of each root is simply $1$ so that $$x^n-1=\prod_{r\in ROOTS}(x-r)^{m_r}=\prod_{r\in ROOTS} (x-r)^1=\prod_{r\in ROOTS, \\distinct} (x-r)=\prod_{d\mid n}Q_d(x)$$

(please comment or edit for any corrections)

Edit: removed some extraneous details and fixed some errors

  • 1
    $\begingroup$ ${WOW}^2$ Thank you very, very much for this great answer! One question and two great answers...thank you!! =) $\endgroup$ – JohnD Mar 29 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.