$(x - 1)|(x^n -1); \forall x \neq 1 $ by induction. I am just hoping to get some help on this question.  Show that:
$$\forall x \neq 1; (x - 1)|(x^n -1)$$
I am trying to prove this by induction on $n$.  Here is what I have so far:
$ \forall x \neq 1; P(n)=(x - 1)|(x^n -1)$.
Base case: $P(1)$
This is obviously true, as $(x^1-1) = (x-1) = (x-1)a; where \ a = 1$ So by the definition of divisibility, $(x-1)|(x-1)$ and $P(1)$ is true.
Inductive assumption $P(k)$ is true.
Inductive step. Prove $P(k+1)$ is true.
by the inductive assumption and the definition of divisibility, we know that $(x-1)|(x^k -1)$ so $x^k = a(x-1); where\ a \in Z$
Assume $(x^{k+1}-1)$ Then $(x^{k+1}-1)=(x^k*x-1) = (a(x-1) *x -1)$
Am I on the correct track here?  The algebra is overwhelming me a bit.  Any help or hints are welcome.
 A: Hint
$$x^{n+1}-1=x(x^n-1)+x-1$$
A: Since a bunch of inductive arguments have already been posted, I thought I'd just add in the way I like best
$$ (x-1)\left(\sum_{k=0}^{n-1} x^k\right)=\left(\sum_{k=1}^n x^k\right)-\left(\sum_{k=0}^{n-1} x^k\right) =x^n-1$$
A: What you assume for the inductive step is that $(x-1)|(x^k-1)$.  From that, you need to prove that $(x-1)|(x^{k+1}-1)$.  The usual way is to somehow find the inductive hypothesis in what you are trying to prove.  It seems useful to argue that $(x-1)|x(x^k-1)$, then ...
A: You are on the right track, but you made a mistake.
$(x-1)|(x^k -1)$ means $x^k-1=a(x-1)$. Thus from $P(k)$ you know that $x^k=a(x-1)+1$.
Then
$$(x^{k+1}-1)=(x^k*x-1) = \left[ \left(a(x-1) +1\right) *x -1 \right]= a(x-1)x+x-1$$
A: Since $(x-1)|(x^1-1)$, the statement is true for $n=1$. Assume that $$(x-1)|(x^k-1)$$ for an arbitrary positive integer $k$. That is, assume that $$x^k=j(x-1)+1$$ for some integer $j$. We must show that $$(x-1)|(x^{k+1}-1).$$ Consider $x^{k+1}-1=x\cdot x^k-1$. Using our induction hypothesis we see that $$x\cdot x^k-1=x(j(x-1)+1)-1$$ which becomes $$jx(x-1)+(x-1)=(jx+1)(x-1).$$ So $(x-1)|(x^{k+1}-1)$. Thus by the Principle of Mathematical Induction $(x-1)|(x^n-1)$ for all $n\in \mathbb{N}$.
