## Odd Power Divisibility

#### Problem

Prove that $6^n + 8^n$ is divisible by 7 iff $n$ is odd.

#### Solution

We shall prove this in two different ways. The first proof, which is the simplest, makes use of congruences and the second proof makes use of the binomial expansion .

__First Proof__

As $6 \equiv -1 \mod 7$ and $8 \equiv 1 \mod 7$ it follows that $6^n \equiv (-1)^n$ and $8^n \equiv 1$.

$\therefore S = 6^n + 8^n \equiv (-1)^n + 1 \mod 7$.

If $n$ is even then $(-1)^n = 1 \implies S \equiv 2 \mod 7$.

If $n$ is odd then $(-1)^n = -1 \implies S \equiv 0 \mod 7$.

Thus S is divisible by 7 iff $n$ is odd.

__Second Proof__

Let $x = 6^n = (7 - 1)^n$ and $y = 8^n = (7 + 1)^n$.

$\begin{align}\therefore y &= 7^n + \dbinom{n}{n-1}7^{n-1} + \dbinom{n}{n-2}7^{n-2} + ... \dbinom{n}{2}7^2 + \dbinom{n}{1}7 &+ 1\\x &= 7^n - \dbinom{n}{n-1}7^{n-1} + \dbinom{n}{n-2}7^{n-2} - ... &+ &\pm1\\\therefore x+y &= 2 \times 7^n + 2 \dbinom{n}{n-2}7^{n-2} + 2 \dbinom{n}{n-4}7^{n-4} + ...\end{align}$

We note that the last term of the series for $x$ will be $-1$ if $n$ is odd and $+1$ if $n$ is even. Therefore the series for $x + y$ will end $ 2 \dbinom{n}{1}7$ if $n$ is odd and 2 if $n$ is even. In other words, all the terms will divide by 7 except the last term when $n$ is odd.

Hence $x + y \equiv 0 \mod 7$ iff $n$ is odd.

What can you deduce about $x + y \mod 49$?

Investigate the remainder when $(a - 1)^n + (a + 1)^n$ is divided by $a$ or $a^2$.