Q4 Matemática  (Middle European Mathematical Olympiad 2009)

Determine todos os inteiros $k\ge 2$ tal que para todos os pares $(m$, $n)$ de diferentes inteiros positivos não maiores que $k$, o número $n^{n-1}-m^{m-1}$ não é divisível por $k$.