How to prove that $n^7\equiv n^3\mod40,\forall n\in\mathbb{Z}$ I have a problem when I try to induction on $\mathbb{Z}$. I don't know how to solve when I try $n-1$ or $n+1$. 
 A: We have the following generalization of Fermat's Little Theorem:
$$a^{k+\lambda(m)} \equiv a^k \bmod m $$
for all $a$ and all $k \geq \max v_p(m)$.
Here, $\lambda$ is Carmichael’s function and $v_p(m)$ is the exponent of $p$ in the prime factorization of $m$.
In your case, $m=40=2^3\cdot5$ and so $k\ge 3$. Since $\lambda(m)=lcm(\lambda(8),\lambda(5))=lcm(2,4)=4$, we get
$$a^{3+4} \equiv a^3 \bmod 40 $$
A: It's special case $\ p^i = 2^3,\ q^j = 5,\ \phi = 4,\ k=3\ $ of the Euler-Fermat generalization below.
Theorem $\ \  n^{\large k+\phi}\equiv n^{\large k}\pmod{p^i q^j}\ \, $ assuming $ \ \color{#0a0}{\phi(p^i),\phi(q^j)\mid \phi},\, $ $\, \color{#90f}{k\ge i,j},\,\ p\ne q.\ $ Proof:
$ p\nmid n\,\Rightarrow\, {\rm mod\ }p^i\!:\  n^{ \phi}\equiv 1\,\Rightarrow\, n^{k + \phi}\equiv n^k,\, $ by $\  n^{\Large \color{#0a0}\phi}\! = (n^{\color{#0a0}{\Large \phi(p^{ i})}})^{\large \color{#0a0}m}\overset{\color{blue}{\rm E}}\equiv 1^{\large m}\!\equiv 1\,$ by $\,\rm\color{blue}{E}=$ Euler.
$\color{#c00}{p\mid n}\,\Rightarrow\, {\rm mod\ }p^i\!:\  n^k\equiv 0\,\equiv\, n^{k + \phi}\ $ by $\ n^k = n^{k-i} \color{#c00}n^i = n^{k-i} (\color{#c00}{mp})^i$ and $\,\color{#90f}{k\ge i}.$
So $\ p^i\mid n^{k+\phi}\!-n^k.\,$ By symmetry $\,q^j\,$ divides it too, so their lcm $ = p^iq^j\,$ divides it too. $\ $ QED
Remark $\ $ Obviously the proof immediately extends to an arbitrary number of primes. This leads the way to Carmichael's Lambda function, a generalization of Euler's phi function.
A: $$n^7-n^3=n^3(n^4-1)=n^2(n^5-n)$$
Using Fermat's Little Theorem, $5|(n^5-n)$
If $n$ is even $8|n^3$
Else $\displaystyle n$ is odd, $=2m+1,$(say),
Both $n+1,n-1$ are even, one is divisible by $4$ and the other is by $2$
Algebraically,  $\displaystyle(2m+1)^2=4m^2+4m+1=8\frac{m(m+1)}2+1\implies 8|(n^2-1)$  if $n$ is odd

Alternatively,
$$F=n^7-n^3=n^3(n^4-1)=n^3(n^2-1)(n^2+1)$$
$$=n(n^2-4+4)(n^2-1)(n^2+1)$$
$$=n(n^2-4)(n^2-1)(n^2+1)+4\cdot n(n^2-1)(n^2+1)$$
$$=n(n^2-4)(n^2-1)\cdot  (n^2+1)+4\cdot n(n^2-1)(n^2-4+5)$$
$$=\underbrace{(n-2)(n-1)n(n+1)(n+2)}_{\text{The product of } 5 \text{ consecutive integers}}\left[n^2+1+4\right]+20\underbrace{(n-1)n(n+1)}_{\text{The product of } 3 \text{ consecutive integers}}$$
Now utilize The product of n consecutive integers is divisible by n factorial or The product of n consecutive integers is divisible by n! (without using the properties of binomial coefficients) to find that $F$ is actually divisible by $20\cdot 3!=120$
