How to prove $f(x^n)$ is divisible by $x^n-1$

Question

The question states that if $f (x)$ is a polynomial such that $x-1|f(x^n)$ prove that $f(x^n)$ is divisible by $x^n-1$

This is how I proceeded since$x-1|f(x^n)$

$f(1)=0$

$\frac {f (x^n)-f(1)}{x^n-1}=g(x)$

since $f(1)=0$

$\frac{f(x^n)}{x^n-1}=g(x)$ hence $x^n-1|f(x^n)$

I guess my proof is incorrect can someone please point out the mistakes and give the correct proof.

Have you heard about complex numbers and roots of unity? – Arthur Aug 30 '17 at 10:51 — Arthur, Aug 30 '17 at 10:51
What is the underlying field/ring? Or is it irrelevant? – freakish Aug 30 '17 at 11:03 — freakish, Aug 30 '17 at 11:03

score 13 · Accepted Answer · answered Aug 30 '17 at 11:15

13

$x-1|f(x^n)$ $\quad\Rightarrow\quad$ $f(1)=0$ $\quad\Rightarrow\quad$ $x-1|f(x)$ $\quad\Rightarrow\quad$ $x^n-1|f(x^n)$.

answered Aug 30 '17 at 11:15

A.Γ.

29,518

This should be the most straightforward one +1. – Vim Aug 30 '17 at 11:17
Yes! The only reason I'm not deleting my own answer is because I want to leave that explanation of OP's error. – Jyrki Lahtonen Aug 30 '17 at 11:29

Jyrki Lahtonen · Answer 2 · 2017-08-30T11:35:25.447

José's solution is nice. And I agree with his assessment that an error you made is that you didn't explain why $g(x)$ is a polynomial. To see the error consider the following piece of faulty reasoning:

A False Fact. If $f(1)=0$ then $(x-1)^2\mid f(x)$.

Proof. Write $$ \frac{f(x)-f(1)}{(x-1)^2}=g(x). $$ Because $f(1)=0$ we see that $$ \frac{f(x)}{(x-1)^2}=g(x). $$ If your logic were valid, we could conclude that $(x-1)^2\mid f(x)$. But this result is clearly false in general. For example when $f(x)=x^2-1$ we have $f(1)=0$, but $(x-1)^2\nmid (x^2-1)$.

You can also do the following.

Let $$ f(x)=a_0+a_1x+\cdots+a_mx^m, $$ where $m$ is the degree of $f$. Then $$ f(x^n)=a_0+a_1x^n+\cdots+a_mx^{nm}. $$ We are given that $x-1\mid f(x^n)$. This means that $x=1$ is a zero of $f(x^n)$, or that $0=a_0+a_1+\cdots+a_m.$

But then $$ \begin{aligned} f(x^n)&=f(x^n)-f(1)\\ &=a_0(1-1)+a_1(x^n-1)+a_2(x^{2n}-1)+\cdots+a_m(x^{mn}-1). \end{aligned} $$ Here all the binomials $x^{kn}-1$, $k=0,1,\ldots,m$, are divisible by $x^n-1$. Hence so is $f(x^n)$.

Thank you for that explanation, earlier I was not able to understand why my assumption was incorrect — Pulsar, Aug 30 '17 at 11:33

score 1 · Answer 3 · answered Aug 30 '17 at 10:56

1

Your proof is wrong because you did not prove that $g(x)$ is a polynomial.

Let $z\in\mathbb C$ be such that $z^n=1$. Then $f(z^n)=f(1)=0$. So, $z$ is a root of $f(x^n)$. Therefore, $f(x^n)$ is a multiple of$$(x-z_1)(x-z_2)\ldots(x-z_n),\tag{1}$$where $z_1,\ldots,z_n$ are the $n^\text{th}$ roots of unity. But $(1)=(x^n-1)$.

answered Aug 30 '17 at 10:56

José Carlos Santos

427,504

2

Why do you assume that the polynomial is over $\mathbb{C}$? – freakish Aug 30 '17 at 11:03
@freakish I didn't. I only assumed that it was a polynomial over a subfield of $\mathbb C$. Otherwise, replace $\mathbb C$ with an algebraic closure of the field you are working with. – José Carlos Santos Aug 30 '17 at 11:16
If we go there you also have the problem that some $z_i$s may be equal. Say, if the underlying field has characteristic two, then $x^8-1=(x-1)^8$ et cetera. So technically this works when the zeros of $z^n-1$ are simple. – Jyrki Lahtonen Aug 30 '17 at 11:33
@JyrkiLahtonen Yes, you are right. – José Carlos Santos Aug 30 '17 at 11:35

farruhota · Answer 4 · 2017-08-30T13:46:29.210

1

Assume the polynomial of degree $m$ has the roots $x_1,x_2,...,x_m$: $$f(x)=a_0x^m+a_1x^{m-1}+\cdots +a_m=a_0(x-x_1)(x-x_2)\cdots (x-x_m).$$ Then: $$f(x^n)=a_0(x^n-x_1)(x^n-x_2)\cdots (x^n-x_m).$$ Since $f(1)=f(1^n)$, then $x-1|f(x^n) \Rightarrow x-1|f(x)$. It implies that at least one root of $f(x)$ is $1$, hence $f(x^n)$ will have a factor $(x^n-1)$.

edited Aug 30 '17 at 13:46

answered Aug 30 '17 at 11:21

farruhota

31,482

How to prove $f(x^n)$ is divisible by $x^n-1$

4 Answers4