Friday, April 14, 2017

polynomials - Prove $x^n-1$ is divisible by $x-1$ by induction





Prove that for all natural number $x$ and $n$, $x^n - 1$ is divisible by $x-1$.



So here's my thoughts:
it is true for $n=1$, then I want to prove that it is also true for $n-1$



then I use long division, I get:




$x^n -1 = x(x^{n-1} -1 ) + (x-1)$



so the left side is divisible by $x-1$ by hypothesis, what about the right side?


Answer



So first you can't assume that the left hand side is divisible by $x-1$ but for the right hand side we have that $x-1$ divides $x-1$ and by the induction hypothesis we have that $x-1$ divides $x^{n-1}-1$ so what can you conclude about the left hand side.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...