Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
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)
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$.
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$.
