# Number Plus One divides Power Plus One iff Odd

## Theorem

Let $q, n \in \Z_{>0}$.

Then:

$\paren {q + 1} \divides \paren {q^n + 1}$

if and only if $n$ is odd.

In the above, $\divides$ denotes divisibility.

## Proof

Let $n$ be odd.

Then from Sum of Odd Positive Powers:

$\displaystyle q^n + 1 = \paren {q + 1} \sum_{k \mathop = 1}^n \paren {-1}^k q^{k - 1}$

Let $n$ be even.

Consider the equation:

$q^n + 1 = 0$

We have:

$\paren {-1}^n + 1 = 2$

So $-1$ is not a root of $q^n + 1 = 0$.

By Polynomial Factor Theorem, $q + 1$ is not a divisor of $q^n + 1$ when $n$ is even.

$\blacksquare$