# How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?

How to prove $\forall m,n\in\mathbb N$:

$$56786730 \mid mn(m^{60}-n^{60})?$$

-
Hint: There is a relation between the prime factors of 56786730 and the divisors of 60. – Hagen von Eitzen Apr 2 '13 at 18:32
$56786730 = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 31 \times 61$. – Lord Soth Apr 2 '13 at 18:35
Little Fermat!! – Jyrki Lahtonen Apr 2 '13 at 18:36

Notice that $56786730=2\times3\times5\times7\times13\times31\times 61$.
By Fermat's Little theorem, $61 \mid m^{60}-n^{60}$ as $m^{60}\equiv 1 \bmod 61$ and $n^{60}\equiv 1 \bmod 61$. [Fermat's little theorem states that $a^{p-1}\equiv 1 \bmod p$ for a prime $p$ where $\gcd(a,p)=1$]. Using casework, notice that $2 \mid mn(m^{60}-n^{60})$ (i.e. either $m$ is odd and $n$ is even or both are odd). Either way the given expression is a multiple of $2$. Notice that other factors of $56786730$ are also primes. Apply FLT again and again to finish the proof.
Hint $\$ Apply little Fermat, noticing that $\rm\displaystyle\ 56786730\ = \!\!\prod_{\large {\begin{array}\rm p\ prime\\ \rm p-1\mid\, 60\end{array}}}\! p$