How to prove that $n^7\equiv n^3\mod40,\forall n\in\mathbb{Z}$

Solution 1:

$$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$

Solution 2:

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 $$