induction: 6 divides $(a^{2n+1}-a)$

Question

Proof by induction:

$\forall n \in \mathbb{N}$: 6 divides $(a^{2n+1}-a)$, $a \in \mathbb{N}$

Induction:

for $n=1:$ $(a^{3}-a) = a*(a^{2}-1)=???$

How do I transform the expression further to get to the result.

Answer 1

Base case. $n=1$ gives $a^3-a=a(a^2-1)=a(a+1)(a-1)$. Observe that $3$ divides this expression as you have a product of three consecutive integers. We can also see that $2$ divides this expression as, if $a$ is odd, then $a+1$ and $a-1$ are both even and an even number multiplied by an odd number gives you an even number. A similar argument works for if $a$ is even. Since $2$ and $3$ both divide this expression, then we can conclude that $6$ does too.

Inductive hypothesis. Assume that $6$ divides $a^{2n+1}-a$. So we can say $a^{2n+1}-a=:6k$ for some $k\in\Bbb N$.

Inductive step. Let's try for $n+1$. We have \begin{align*} a^{2(n+1)+1)}-a&=a^{2n+3}-a\\ &=a^{2n+1}a^2-a\\ &=(6k+a)a^2-a\\ &=6ka^2+a^3-a\\ &=6ka^2+a(a^2-1)\\ &=6ka^2+a(a+1)(a-1) \end{align*}

Use the argument in the base case to conclude that the whole expression in the inductive step is divisible by $6$.

Answer 2

Use that $$a^{2n+1}-a=a(a^{2n}-1)=a(a^n-1)(a^n+1)$$

Answer 3

If $a$ is an integer, then $a(a^2-1)=a(a+1)(a-1) = (a-1)a(a+1)$, i.e., the product of three consecutive integers. Thus, at least one of these must be even (so $2$ divides the product), and one of these must be a multiple of three (so $3$ divides the product).

If both $2$ and $3$ divide the product, then $2\cdot 3 = 6$ divides it also.

---

Alternatively, if you consider $n=0$ you get $a-a=0$, which is trivially divisible by $6$.

Answer 4

All what you have to do is to factorize $a^2-1$: $$a (a^2 -1)=a (a-1)(a+1)$$