6
$\begingroup$

In algebra & polynomials, how do we prove that $$x-1 \mid x^n -1?$$

$\endgroup$
  • 1
    $\begingroup$ FACTOR THEOREM, FACTOR THEOREM, FACTOR THEOREM. $\endgroup$ – JP McCarthy Feb 11 '15 at 10:30
  • 2
    $\begingroup$ both have $x=1$ as zero ...' $\endgroup$ – kjetil b halvorsen Feb 11 '15 at 11:14
18
$\begingroup$

Consider $(x-1)(1+x+x^2+\ldots+x^{n-1})$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do you derive $x^n-1 = (x-1)(1+x+x^2+...+x^{n-1})$? $\endgroup$ – Duane Nov 11 '16 at 7:22
  • $\begingroup$ @Duane You can use long division to find the quotient of $x^n - 1$ by $x-1$. $\endgroup$ – Alex Provost Nov 11 '16 at 17:28
11
$\begingroup$

You can prove it by induction. $$x^{n+1}-1 = x^{n+1}-x^n + x^n -1 = (x-1)x^n + x^n-1$$

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

Clearly $x\equiv 1 \pmod{x-1}$. Hence $x^n-1\equiv 1^n-1\equiv 0 \pmod{x-1}$, i.e. $x-1\mid x^n-1$.

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

Hints: For any two reals $\,a,b\,$ :

$$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\ldots+ab^{n-2}+b^{n-1})$$

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

Factorization method

Clearly, $x^{n} - 1 = (x - 1)(x^{n - 1} + x^{n - 2} + \dots + 1)$. Thus, $(x - 1) | (x^{n} - 1)$ since there exists the polynomial namely $(x^{n - 1} + x^{n - 2} + \dots + 1)$ that is multiplied by $(x - 1)$ to obtain $(x^{n} - 1)$.

Substitution method

Suppose that $x - 1 = 0 \rightarrow x = 1$. If we substitute that value for $(x^{n} - 1)$, then clearly $1^{n} - 1 = 0$. This shows that $(x^{n} - 1)$ has a factor $(x - 1)$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Hint: Apply division algorithm, what can be the remainder?

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

By Remainder theorem $ f(x) = x^n -1 ,$ if $ f(1) = 0$, then $ (x-1)$ is a factor of $f(x) $ .

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Another proof by induction: $$ x^{n+1}-x+x-1=x(x^{n}-1)+x-1 $$ RHS also divides $x-1$ because $x^n-1$ divides it by the assumption of the $n^{th}$ step

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Please use "divide" the other way round. For example $x-1$ divides $x^n-1$ but $x^n-1$ does not divide $x-1$ in general. $\endgroup$ – Did May 7 '13 at 15:21
0
$\begingroup$

$x-1$ has as many zeros as its degree allows (i.e. one, and it's 1), and $x^n-1$ shares all those zeros. From that it follows that $x-1|x^n-1$, at least of you're working over a field. Over a ring (i.e. where you cannot, in general, divide) you also need that the coefficient of the largest power in $x-1$ divides the coefficient of the largest power in $x^n-1$, but you have that too.

What you use here is that if $p(a)=0$, then $(x-a)|p$.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.