Read

cyclotomic polynomial first. Here's why such a

polynomial has a

sequence of coefficients which reads the same in both directions, maybe with a change of

signs. Suppose

*t* is a

primitive *n*'th

root of

unity. Then so is its

conjugate. But since |

*t*|=1, 1/

*t* is the conjugate of

*t*.

Now, the *n*'th cyclotomic polynomial is simply the minimal polynomial (over **Z**) for *t*, hence also for its conjugate 1/*t*. Writing out the polynomial as

*p(x)* = *a*_{k} x^{k} + ... + *a*_{0},

we see that

0 = *a*_{k} t^{k} + ... + *a*_{0}

and

0 = *a*_{k} 1/*t*^{k} + ... + *a*_{0}.

Multiplying the last equation by

*t*^{k}, we get

0 = *a*_{0} t^{k} + ... + *a*_{k}.

So if

*q(x)* is the polynomial with reverse coefficient sequence compared to

*p(x)*, we have that

*q(t)=0* and has the same

degree as

*p(x)*, and is therefore a multiple of it. But

*a*_{0} is the product of all primitive

*n*'th roots of unity, hence is either +1 or -1. Thus either

*p(x)=q(x)* or

*p(x)=-q(x)*, as required...