How to show $n^5 + 29 n$ is divisible by $30$ Show that $n^5 + 29 n$ is divisible by $30$.
Attempt:
$n^4 ≡ 1 \pmod 5$ By Fermat Little Theorem
 A: Hint $\ n^5+29n = n^5-n + 30n\,$ so it suffices to show $\,30\mid n^5-n,\,$ for which it suffices to show it is divisible by $\,2,3,5.\,$  This is easy to do in each case as below, or directly, e.g. consider $\,n^5\!-\!n = n(n^4\!-\!1) = (n\!-\!1)n(n\!+\!1)(n^2\!+\!1),\,$ and $\,n^2\!+\!1 \equiv n^2\!-\!4\equiv (n\!-\!2)(n\!+\!2)\pmod 5$ 
Alternatively, it follows immediately from a slight generalization of $\color{#c00}{\rm Fermat's}$ little Theorem: 


*

*$ $ If $\ p\!-\!1\mid e\!-\!1\,$ then $\, {\rm mod}\ p\!:\ n^e\equiv n.\,$ Indeed, it is true if $\,n\equiv 0,\,$ and if $\,n\not\equiv 0\,$ then $\,e\, =\, 1+k(p\!-\!1)\ $ so $\ n^e\equiv n (\color{#c00}{n^{p-1}})^k\overset{\rm\color{#c00}{ Fermat}}\equiv n \color{#c00}{(1)}^k\equiv n,\ $ so $\ n^e\!-n\equiv n-n\equiv 0.$ 


Remark $\ $ Above we used  basic congruence rules.  The key idea generalizes, see Korselt's Carmichael Number Criterion.
A: If you use induction, you can use $$\{(n+1)^5+29(n+1)\}-(n^5+29n)=5n(n+1)(n^2+n+1)+30.$$
Here, note that $n(n+1)$ is divisible by $2$ and that $n(n+1)(n^2+n+1)$ is divisible by $3$. 
A: You want to show that $n^5+29n$ is divisible by $2$, $3$ and $5$.


*

*$n^5+29n\equiv n^5+n\equiv n^2n^2n+n\equiv nnn+n\equiv nn+n\equiv n+n\equiv0\pmod{2}$

*$n^5+29n\equiv n^5-n\equiv n^3n^2-n\equiv nn^2-n\equiv n-n\equiv0\pmod{3}$

*$n^5+29n\equiv n^5-n\equiv n-n\equiv0\pmod{5}$
All use Fermat's little theorem: $n^p\equiv n\pmod{p}$ for $p$ prime.
A: HINT
$29\equiv -1\pmod{30},n^5-n=n(n-1)(n+1)(n^2+1)$
A: Here's another way:  $\rm\,\ n^5+29n\, =\, n^5-n + 30n\,$ and $\rm\ 30\mid n^5-n\ $ by
$$\rm\begin{eqnarray} n(n^4\!-\!1)/30\, &=&\rm\ \ n\ \quad (n^2-1)\quad\, (\color{#C00}{n^2\!+\!\!}&\color{#c00}1)/&\!\!30\!\!\!\!\!\!  & & \\ 
&=&\ \ \rm n\,(n\!+\!1)\,(n\!-\!1)\,(\ \ \ \,\color{#C00}5 &\!\color{#C00} + &\!\!\!\rm\color{#C00}{ (n\!+\!2)\,(n\!-\!2)})/30 \\ 
&=&\ \ \rm (n\!+\!1)\,n\,(n\!-\!1)\ \color{#c00}5/30\! &\! + &\!\!\!\rm \color{#C00}{(n\!+\!2)}\,(n\!+\!1)\,n\,(n\!-\!1)\,\color{#C00}{(n\!-\!2)}/30 \\
 &=&\rm\qquad\qquad\ {n\!+\!1\ \!\choose 3}\ &\! + &\ \ \rm 4\,{n\!+\!2\ \! \choose 5}\  \ \in\ \ \Bbb Z 
\end{eqnarray}\qquad$$
A: You can prove this by induction. Case $n = 1$ is obviously true.
Hint: Use the binomial theorem in the inductive step. Also, a number is divisible by $30$ if and only if it is divisible by its prime factors $2$, $3$, and $5$.
A: Modulo $6$, the expression is $n^5 + (-1)n = n^5 -n$.
Modulo $5$, $n^5 \equiv n$ by Fermat's Little Theorem, so $n^5 - n \equiv 0 \pmod 5$.
Since $5$ and $6$ are coprime $n^5 + 29n \equiv 0 \pmod {30}$.
A: $$n^5+29n-(n-2)(n-1)n(n+1)(n+2)=5n^3+25n=5(n-1)n(n+1)+30n$$
$$\implies n^5+29n=\underbrace{(n-2)(n-1)n(n+1)(n+2)}_{\text{The product of }5\text{ consecutive integers}}+5\underbrace{((n-1)n(n+1))}_{\text{The product of }3\text{ consecutive integers}}+30n$$
See The product of n consecutive integers is divisible by n factorial
