# Why are two statements about a polynomial equivalent?

I am reading a claim that the following two statements are equivalent.

• One of the roots of a polynomial $v(t)$ is a $2^j$-th root of unity, for some $j$.
• The polynomial $v(t)$ is divisible either by $1-t$ or by $1+t^{2^{j-1}}$, for some $j$.

We know that the coefficients of $v(t)$ are from $\{-1,0,1\}$.

I am not sure exactly how to interpret this. For which $j$ is this true?

Should $j$ be a positive integer such that $2^j$ is at most the degree of $v(t)$ for example or should there be some other restriction on $j$ or is it really true with no restriction on $j$?

Erratum: Fixed exponent in $1+t^{2^{j-1}}$.

A $2^j$-th root of unity is a root of a polynomial $P$ if and only if the minimal polynomial of that root is a factor of $P$. The minimal polynomials of roots of unity are called cyclotomic polynomials, and it's easy to see that for $j=0$, this is $1-t$, and for $j > 0$, it is $1 + t^{2^{j-1}}$ :
$$\Phi_{2^j} = \prod_{\zeta^{2^j} = 1, \zeta^{2^{j-1}} \neq 1} (\zeta - t) = \frac{\prod_{\zeta^{2^j} = 1} (\zeta - t) }{\prod_{\zeta^{2^{j-1}} = 1} (\zeta - t) } = \frac{1-t^{2^j} }{ 1-t^{2^{j-1}}} = 1+t^{2^{j-1}}$$
• This strict connection is true for minimal $2^j$-th roots of unity. It is not clear from the OP if these minimal roots are intended. If not, then a $2^j$-th root of unity can also be minimal for some smaller degree $2^{j-k}$, which then determines the cyclotomic polynomial. – Dr. Lutz Lehmann May 13 '14 at 10:17
• If you were given such a polynomial $v(t)$, how would you test the condition in practice? – user66307 May 13 '14 at 10:55
• @Lembik : I would check divisibility by the cyclotomic polynomials of degree not greater than that of $v$. In this case ($2^j$-th roots of unity), due to the shape of those cyclotomic polynomials, doing the division is very fast. – mercio May 13 '14 at 10:59