Number Plus One divides Power Plus One iff Odd

From ProofWiki
Jump to navigation Jump to search

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$

By elementary complex analysis:

$q \in \set {e^{\paren {2 k + 1} i \pi / n}: 0 \le k < n}$


from which it is apparent that $-1$ is not among these roots.

Thus $q + 1$ is not a divisor of $q^n + 1$ when $n$ is even.

$\blacksquare$


Sources