# Prove that $x-1$ is a factor of $x^n-1$

Prove that $x-1$ is a factor of $x^n-1$.

My problem: I already proved it by factor theorem and by simply dividing them. I need another approach to prove it. Is there any other third approach to prove it? If yes please share it. I will be very thankful to you.

Thanks.

: Factor Theorem: $x -r$ is a factor of $f(x)$ if and only if $f(r) = 0$.

• What is factor theorem? Jan 25, 2015 at 21:10
• If $x-r$ is a factor of $f(x)$ then this implies that $f(r)=0$ Jan 25, 2015 at 21:11
• Why do you need another approach? Jan 25, 2015 at 21:14
• @induktio Yes I also had this in mind.Thanks for detailed proof.
– Flip
Jan 25, 2015 at 21:36

You can easily prove $(x-1)\underbrace{(1+x+...+x^{n-1})}_S=x^n-1$, which is your desired result by expanding the left paranthesis (keyword: geometric series) as follows:

$(x-1)S = xS-S = (x+x^2+...+x^n)-(1+x+...+x^{n-1}) = x^n-1$ (telescope sum)

• How do you derive $x^n-1 = (x-1)(1+x+x^2+...+x^{n-1})$? Nov 11, 2016 at 7:24
• @Duane Expand the left parenthesis on the right side: $(x-1)(1+x+x^2+\ldots+x^{n-1}) = x(1+x+x^2+\ldots+x^{n-1})-1(1+x+x^2+\ldots+x^{n-1})$. Nov 11, 2016 at 10:21

Since the question is tagged "abstract algebra" let's use a little, viz. congruences.

Proof $$\,\ {\rm mod}\,\ x-1\!:\,\ x\equiv 1\,\color{#c00}{\overset{\rm CP}\Rightarrow}\, x^n\equiv 1^n \$$ thus $$\ x-1\mid x^n-1$$

using $$\,\rm\color{#c00}{CP}$$ = Congruence Power Rule (or iterated Product Rule), whose simple proof is exactly the same as it is for the ring of integers, since it uses only commutative ring laws.

Or, specializing $$\,a = x\!-\!1\,$$ below (an inductive proof of first term of a binomial expansion), immediately yields that $$\,x^n = 1 + (x\!-\!1)k,\,$$ for $$\,k\in\Bbb Z[x],\$$ so $$\ x\!-1\mid x^n\!-\!1\,$$ in $$\,\Bbb Z[x].$$

\begin{align} (1+ a)^n\, \ \ =&\,\ \ 1 + ak,\ {\rm some}\ k\in\Bbb Z,\ \ \ {\rm i.e.}\ \ P(n)\\[1pt] \Rightarrow\ (1+a)^{\color{#c00}{n+1}}\! =&\ (1+ak)(1 + a)\\[2pt] =&\,\ \ 1+ a\,(\underbrace{k\!+\!1\!+\!ka\!}_{\large k'\,\in\,\Bbb Z})\qquad\ \ {\rm i.e.}\ \ P(\color{#c00}{n\!+\!1})\\ \end{align}\qquad

The above is essentially a special case of the prior proof using congruences, without using the language of congruences (see here for how to write such proofs in congruence language).

Problem: Show that $x^{n-1}$ is divisible by $x-1$ for all $n\in\mathbb{N}$ and where $x\neq 1$ is a natural number.

Proof. For any integer $n\geq 1$, let $S(n)$ denote the statement $$S(n) : (x-1)\mid (x^n-1)\quad |\quad \forall n\in\mathbb{N},\, x\in\mathbb{N}\setminus\{1\}.$$ Note that $S(n)$ is a special case of a more general statement: Let $P(n)$ be the statement that for any polynomials $p$ and $q$, $$P(n) : (p-q)\mid (p^n-q^n)\quad |\quad \forall n\in\mathbb{N},\,p\neq q.$$ It is clear that $S(n)$ is the case when $p=x$ and $q=1$.

Base step ($n=1$): The statement $P(1)$ says that $(p-q)\mid (p^1-q^1)$ which is true because $(p-q)\mid (p-q)$; that is, $p-q$ divides itself, of course.

Inductive step ($P(k)\to P(k+1)$): Fix some $k\geq 1,\,k\in\mathbb{N}$. Assume that $$P(k) : (p-q)\mid (p^k-q^k)\quad |\quad \forall k\in\mathbb{N},\,p\neq q$$ holds. That is, $p^k-q^k=(p-q)\ell$, where $\ell$ is some arbitrary polynomial. To be proved is that $$P(k+1) : (p-q)\mid (p^{k+1}-q^{k+1})$$ follows. To see that $P(k+1)$ follows, show that $p^{k+1}-q^{k+1}$ is divisible by $p-q$: \begin{align} p^{k+1}-q^{k+1} &= p^{k+1}-p^kq+p^kq-q^{k+1}\tag{manipulate}\\[0.5em] &= p^k(p-q)+q(p^k-q^k)\tag{factor out $p^k$ and $q$}\\[0.5em] &= p^k(p-q)+q(p-q)\ell\tag{by $P(k)$}\\[0.5em] &= (p-q)(p^k+q\ell).\tag{factor out $p-q$} \end{align} It has been shown that $(p-q)\mid (p^{k+1}-q^{k+1})$, thus concluding the proof of the induction step. By the principal of mathematical induction, for every $n\in\mathbb{N}$, the stronger result $P(n)$ holds, and thus $S(n)$ holds as well.

A polynomial of the form $x - a$ divides the polynomial $f$ if and only if $f(a) = 0$.

• OP already knew this approach (probably what he meant by "factor theorem"). Jan 25, 2015 at 21:23
• @user314: I didn't know the term "factor theorem", compare also the first comment at the question. Anyway, in my opinion this is the shortest and most elegant way to get the desired result, and I don't think my answer deserves all the downvotes it got (3 downvotes so far). Jan 25, 2015 at 21:47

If you have a polynomial $p(x)$ of degree more than $1$, and write $p(x) = (x-a)q(x)+ r(x)$, then $a$ is a root of $p(x)$ if and only if $r(a) = 0$, and since $\deg r(x) < \deg(x-1) = 1$, we get that $r$ is constant. Write $x^n-1 = (x-1)q(x) + r(x)$ and notice that $1$ is a root of $x^n-1$.

Hint: Use (or prove inductively) that $$x^n-y^n = (x-y)\sum_{i=0}^{n-1}y^ix^{n-1-i}$$ for all $x,y \in \Bbb{R}$, $n \in \Bbb{N}$

A proof similar to Bill's: $$x - 1$$ divides $$x^n - 1$$ iff $$x^n - 1 \equiv 0 \pmod{x - 1}$$. But $$\mathbb{Q}[x]/(x - 1)$$ is the splitting field of $$x - 1$$, meaning that $$x \equiv 1$$, thus $$x^n - 1 \equiv 1^n - 1 \equiv 0$$.