Prove by induction that $a^{4n+1}-a$ is divisible by 30 for any a and $n\ge1$

Question

It is valid for n=1, and if I assume that $a^{4n+1}-a=30k$ for some n and continue from there with $a^{4n+5}-a=30k=>a^4a^{4n+1}-a$ then I try to write this in the form of $a^4(a^{4n+1}-a)-X$ so I could use my assumption but I can't find any $X$ that would set the two expressions equal.

Then I tried factoring $a^{4n+1}-a=30k$ as $a(a^n-1)(a^n+1)(a^{2n}+1)=30k$ and using that as my assumption. Then I also factor as $a^{4n+5}-a=a(a^{n+1}-1)(a^{n+1}+1)(a^{2n+2}+1)$ and again I'm stuck not being able to use my assumption.

Please note that I strictly need to use induction in this problem.

Answer 1

We start with the base case: $n = 1 \implies P(1): a^5 - a = a(a-1)(a+1)(a^2+1)$. The product $ 6 = 3! \mid a(a-1)(a+1) $. If $a = 0, 1, 4 \pmod 5 \implies 5 \mid a^5 - a \implies 30 \mid a^5 - a$ since $\text{gcd}(5,6) = 1$. If $a = 2, 3 \pmod 5 \implies 5 \mid a^2 + 1 \implies 30 \mid a^5 - a$. Thus $P(1)$ is true.

Assume $P(n): 30 \mid a^{4n+1} - a$ is true. Then

$$\begin{align}P(n+1): a^{4n+5} - a &= a^{4n+5} - a^{4n+1} + (a^{4n+1}-a) \\ &= a^{4n}(a^5-a) + (a^{4n+1}-a) \end{align}$$ The first term of this sum is divisible by $30$ as we just proved it, and the second term is divisible by $30$ by inductive step, thus the sum is divisible by $30$, thus $P(n+1)$ is divisible by $30$, completing the induction process.

Answer 2

$a(a^{4n}-1)=a(a^{2n}-1)(a^{2n}+1)=a(a^{n}-1)(a^{n}+1)(a^{2n}+1)$.

Assume $30 | a(a^{4n}-1)$.

$30 | a(a^{4(n+1)}-1)$ if and only if $30 | a(a^{4(n+1)}-1)-a(a^{4n}-1)$.

Try factoring: $a(a^{4(n+1)}-1)-a(a^{4n}-1)$. Think about how regardless of $a$, you can show that one of the terms of the factorization must be divisible by 2, another divisible by 3, and another divisible by 5.

Answer 3

Don't factor entirely. Just factor enough to realize

$a^{4n+1} - a = a(a^{4n} - 1)=a(a - 1)(a^{4n-1} + a^{4n-2} + .... + a + 1)$.

Assume for $n = k$ that

$a^{4k + 1}-a= a(a^{4n} - 1)=a(a - 1)(a^{4k-1} + a^{4k-2} + .... + a + 1)= 30M$

then $a^{4(k+1) + 1} - a = a(a-1)(a^{4k + 3} + ...)=$

$a(a-1)(a^{4k + 3} + a^{4k + 2} + a^{4k+1} + a^{4k}) +a(a - 1)(a^{4k-1} + a^{4k-2} + .... + a + 1)$

$= a(a-1)(a^{4k + 3} + a^{4k + 2} + a^{4k+1} + a^{4k}) + 30M$.

$= a(a-1)(a^3 + a^2 + a + 1)a^{4k} + 30M$

$= (a^{4*1 + 1} - a)a^{4k} + 30M$.

But $30|(a^{4*1 + 1} - a) $ By our initial step. So $30|(a^{4*1 + 1} - a)a^{4k} + 30M$.

====

In hind sight it's easy to see that $a^{4(n+1) + 1} - a = a^{4(n+1) + 1} - a^{4n+1} + a^{4n + 1} - a = (a^{4*1 + 1} - a)a^{4n} - (a^{4n+1} - a)$.

So $a^{4*1 + 1} -a|a^{4*m + 1} - a;m \ge 1$ via induction.

Answer 4

Below we first give a natural proof using modular arithmetic, then we explain how to translate it into divisibility language, and finally we show how to make the induction obvious by bringing to the fore the innate monoid structure (i.e. closure under multiplication), revealing that the induction is the obvious induction that sets closed under multiplication are closed under powers.

Hint $\ $ See this answer for various proofs of the base case $\,30\mid \color{#0a0}{a^{\large 5}-a}.\,$ The inductive step is

$\ {\rm mod}\ 30\!:\,\ \color{#c00}{a^{\large 4n+1}\equiv a}\,\Rightarrow\,a^{\large 4(n+1)+1}\!\equiv a^{\large 4} \color{#c00}{a^{\large 4n+1}}\!\equiv a^{\large 4}\color{#c00}a\equiv \color{#0a0}{a^{\large 5}\equiv a}.\ \ $ QED

Remark $\ $ If modular arithmetic is unfamilar you can eliminate it above to obtain $$ a^{\large 4(n+1)+1}\!-a = a^4(\color{#c00}{a^{4n+1}\!-a}) + \color{#0a0}{a^5 - a} $$

By our induction hypothesis we know that $\,30\mid \color{#c00}{a^{4n+1}-a}\,$ and $\,30\mid \color{#0a0}{a^{\large 5}-a}\,$ by the base case, hence $30$ divides the RHS above, so also the equal LHS, which completes the inductive proof. The proofs in Daniel's and egreg's answers are essentially the same, except they work explicitly with quotients instead of using divisibility inferences.

Alternatively you can prove by induction that $\,a^4-1\mid a^{4n}-1\,$ then scale that by $\,a.$

Monoid Structure $\ $ Abstracting the first proof yields the following

$$ ab\equiv a\equiv ac\,\Rightarrow \overbrace{a\,b}^{\large a}c\equiv a$$

Thus the solution set $S$ of $\,ax\equiv a\,$ is closed under multiplication, i.e. $\, b,c\in S\,\Rightarrow\, bc\in S.\,$ By an obvious induction this implies that $\,S\,$ is closed under powers $\,b\in S\,\Rightarrow\, b^n\in S\,$ for all $\,n\ge 1.\,$ The first proof is just the special case $\, b = a^4.$

Thus the essence of the induction is that sets closed under multiplication are closed under powers. Bringing to the for this innate algebraic structure simplifies the problem so much that the inductive step becomes obvious. Such simplification occurs frequently in common induction problems (e.g. here) so it is worth the effort to first look for such innate structure before diving head-first into brute force inductive proofs.

Answer 5

The induction hypothesis is that $a^{4n+1}-a=30k$, for some integer $k$.

Therefore $$ a^{4(n+1)+1}-a=a^4\cdot a^{4n+1}-a=a^4(30k+a)-a=30ka^4+a^5-a $$ and the proof is reduced to showing that $a^5-a$ is divisible by $30$, which is the base step.

Answer 6

Here is how I would write up the main part of the induction proof (DeepSea and Bill handle the base case easily), in the event that you may find it useful: \begin{align} a^{4k+5}-a&= a^4(a^{4k+1}-a)+a^5-a\tag{rearrange}\\[1em] &= a^4(30\eta)+a^5-a\tag{by ind. hyp.; $\eta\in\mathbb{Z}$}\\[1em] &= a^4(30\eta)+30\ell\tag{by base case; $\ell\in\mathbb{Z}$}\\[1em] &= 30(a^4\eta+\ell)\tag{factor out $30$}\\[1em] &= 30\gamma.\tag{$\gamma\in\mathbb{Z}$} \end{align}