2
$\begingroup$

This question already has an answer here:

Prove $a^n+1$ is divisible by $a + 1$ if $n$ is odd:

We know $a$ cannot be $-1$ and the $n \in \mathbb{N}$. Since $n$ must be odd, we can rewrite $n$ as $2k+1$. Now we assume it holds for prove that it holds for the next term.

$$a^{2(k+1)+1}+1$$ $$=a^{2k+3}+1$$ $$=a^3\cdot a^{2k}+1$$ $$=(a^3+1)\cdot a^{2k} -a^{2k}+1$$

Im not sure on what to do next. Since $a^{2k}$ means that the exponential term will be even and thus you cant use the fact that $a^n+1$ is divisible by $a + 1$ if $n$ is odd.

$\endgroup$

marked as duplicate by Bill Dubuque divisibility Apr 7 at 17:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Why should $a$ not be $-1$? The statement not only still makes sense, but it's true as well. $\endgroup$ – Saucy O'Path Apr 7 at 17:24
  • $\begingroup$ First show $X+1$ divides $X^n +1$ as polynomials using factor theorem. Then the rest follows. $\endgroup$ – Ignorant Mathematician Apr 7 at 17:24
2
$\begingroup$

Use the fact that, since $n$ is odd\begin{align}a^n+1&=a^n-(-1)^n\\&=\bigl(a-(-1)\bigr)\bigl(a^{n-1}+(-1)a^{n-2}+(-1)^2a^{n-3}+\cdots\bigr)\\&=(a+1)(a^{n-1}-a^{n-2}+\cdots+1).\end{align}

$\endgroup$
1
$\begingroup$

For the inductive step, as $(a+1)$ divides $a^{n-2}+1$(as if $n$ is odd then also $n-2$ is odd), consider $$(a^n+1)-(a^{n-2}+1)=a^{n-2}(a^2-1)=a^{n-2}(a+1)(a-1)$$ As, $(a+1)$ divides $a^{n-2}+1$ and also divides $(a^n+1)-(a^{n-2}+1)$, we can conclude that $(a+1)$ divides $(a^n+1)$.

$\endgroup$
1
$\begingroup$

Here’s a proof using polynomial.

Recall: A polynomial Q divide a polynomial P if and only if all roots of Q (with multiplicity) are roots of P.

Now we consider $Q(a)=a+1$ and $P(a)=a^n+1$. Note that both P and Q are monic polynomial.

$Q|P \iff P(-1)=0$ since $P(-1)=(-1)^n+1$ then $Q|P\iff n$ is odd.

$\endgroup$

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