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

Question

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$.

Answer 1

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

Answer 2

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$.

Answer 3

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)

Answer 4

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}$

Answer 5

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.

Answer 6

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).