# 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? – graydad Jan 25 '15 at 21:10
• If $x-r$ is a factor of $f(x)$ then this implies that $f(r)=0$ – Mufasa Jan 25 '15 at 21:11
• Why do you need another approach? – Rob Arthan Jan 25 '15 at 21:14
• @induktio Yes I also had this in mind.Thanks for detailed proof. – Flip Jan 25 '15 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})$? – Duane Nov 11 '16 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})$. – flawr Nov 11 '16 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\qquad\qquad\quad {\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'})\ \ \ {\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.

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"). – user26486 Jan 25 '15 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). – azimut Jan 25 '15 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}$