I need to prove that for natural numbers $a$, and positive integers $n$, the number $a^{2n+1}-a$ is divisible by $6$.
I have proved the case when $n=1$, that $a^3-a$ is divisible by $6$. I'm having trouble proving that if $a^{2n+1}-a$ is divisible by $6$, then $a^{2(n+1)+1}-a$ is also divisible by $6$.
hint: $a^{2n+1} - a = a(a^{2n}-1) = a(a^2-1)(a^{2n-2} + a^{2n-4} + \cdots + 1) = a(a-1)(a+1)(.....)$ is divisible by $6$ since it has a product of $3$ consecutive integers: $a-1,a,a+1$.
To do an induction proof.
The base case is done. Assume $6\mid a^{2n+1} - a \Rightarrow a^{2n+3} - a = (a^{2n+3} - a^{2n+1}) + (a^{2n+1} - a) = a^{2n}\cdot a\cdot (a-1)(a+1) + (a^{2n+1}-a)$ is divisible by $6$ since the first term has again a product of $3$ consecutive integers, and the expression in the parentheses is divisible by $6$ by inductive step so the sum is divisible by $6$, complete the induction proof.
Hint $\ $ Let $\,f(n) = a^{2n+1}\!-a\,$ Then $\,f(n\!+\!1) - f(n)= (a\!-\!1)a(a\!+\!1) a^{2n}\,$ is a multiple of $6,\,$ since a product of $3$ consecutive integers is divisible by both $3$ and $2.\,$ Therefore if $\,f(n)\,$ is divisible by $6$ then so too is $\,f(n\!+\!1) = f(n) + (a\!-\!1)a(a\!+\!1)a^{2n},\,$ yielding the inductive step.
Remark $\ $ The method employed is a very general one that is worth explaining. The basic idea is that $\,6\,$ dividies $\,f(n)\,$ for all $\,n\ge 0\,$ iff it is the constant sequence $\,f(n)\equiv 0\pmod 6.$ But it is trivial to prove by induction that a sequence has constant value $\equiv c\,$ $\iff$ $\,f(0)\equiv c\,$ and $\,f(n\!+\!1)\equiv f(n),\,$ i.e. $\,f(n\!+\!1)-f(n)\equiv 0.\,$ This is precisely the method employed above, except it uses divisibility language vs. modular language (congruences).
This method is a special case of the powerful method telescopic induction, which is explained at length in many posts here.
Induction assumption: $a^{(2n+1)} \equiv a \pmod 6$. OK, we prove this for n=1, and then we assume this is true for n.
Now we have: $a^{(2n+3)} \pmod 6\equiv (a^{(2n+1)}) * (a^2) \pmod 6 \equiv $ (using the induction hypothesis) $ \equiv a \cdot a^2 \pmod 6\equiv a^3 \pmod 6$
But $a^3 - a = a\cdot(a-1)\cdot(a+1) $ which is apparently divisible by 6 (because this product contains 1 number divisible by 2 and one number divisible by 3). Thus $6 / (a^3 - a)$ and therefore $6 / (a^{(2n+3)}-a)$
You've shown that this is true for $n=1$:
$a^{2+1}-a=6m$
Assume that this is true for $n$:
$a^{2n+1}-a=6k$
Prove that this is true for $n+1$:
$a^{2(n+1)+1}-a=$
$a^{2n+3}-a=$
$a^2(a^{2n+1}-a)+a^3-a=$
$a^2(\color{red}{a^{2n+1}-a})+\color{blue}{a^{2+1}-a}=$
$a^2\color{red}{6k}+\color{blue}{6m}=$
$6(a^2k+m)$
Please note:
Since you have proved $a^3-a$ is divisive by $6$ that is $a^3-a=6q_1$ where $q_1\in\mathbb{Z}.$ If $a^{2n+1}-a$ is divisible by $6,$ then $a^{2n+1}-a=6q$ where $q\in \mathbb{Z}.$ This implies $a^{2n+1}=6q+a,$ equivalently $a^{2n+3}=6qa^2+a^3$ or $$a^{2n+3}-a=6qa^2+a^3-a=6qa^2+6q_1=6(qa^2+q_1)$$ That is $a^{2n+3}-a$ is divisible by 6.
