$ k=2,3$ are the only solutions, which can be checked easily. Let $ k\ge 4.$If $ \phi(k)+1<k$ then we can choose $ n=1,m=\phi(k)+1$ which are clearly different, and we are done. Otherwise $ k$ is prime and greater than $ 3$ so we can choose $ n=k-1,m=\frac{k+1}{2}$ or $ n=1,m=\frac{k+1}{2}$, and we are done by FLT.

I agree for the case where $ k$ is prime and $ > 3$. But if $ m = \phi(k) + 1$ then $ m^{m-1} \equiv 1 \bmod{k}$ is not true if $ \gcd(k, \phi(k)+1) > 1$ This can easily happen e.g $ k = 15 \implies \phi(k)+1 = 9$

FelixD wrote: Determine all integers $ k\ge 2$ such that for all pairs $ (m$, $ n)$ of different positive integers not greater than $ k$, the number $ n^{n - 1} - m^{m - 1}$ is not divisible by $ k$. $ k = 2,3$ are solutions of this problem . We divide problem into two cases : If $ k$ is even and is greater than 2 . It is easy to see that $ (m,n) = (k - 1,1 )$ then $ k$ is a divisor of number $ n^{n - 1} - m^{m - 1}$ .Therefore if $ k > 2$ then exist $ (m,n)$ satisfies condition . Remain case is $ k$ is odd . We will show that $ k$ must have form $ p^a$ where $ p$ is a prime . If not then exists $ p,q$ such that $ n = pq$ where $ p,q > 1$ and $ \gcd(p,q) = 1$ . By the chinese remainder theorem , exist n such that : \[ n\equiv 1 (\mod p)\] \[ n\equiv - 1 (\mod q )\] It is easy to show that $ n$ is different from $ 1$ and $ k - 1$ and $ n^{n - 1}\equiv 1 , - 1 (\mod k )$ . If this congruence is 1 then we choose $ m = 1$ and the other we choose $ m = k - 1$ . So we only need to solve this problem when $ n = p^a$ . But is is quite easy . If $ a > 2$ then we choose $ m = \varphi(p^a) + 1$ and $ n = 1$ then $ p^a |n^{n - 1} - m^{m - 1}$ If $ a = 1$ (it is equivalent to the fact that $ k$ is a prime number . Suppose it does not exist pair of $ (m,n)$ satisfies condition then $ n^{n - 1}$ is a complete reside system mod p . Because the is exactly $ \frac {p - 1}{2}$ numbers are quadratic residue mod p and if n is odd then $ n^{n - 1}$ is a quadratic residue mod p so if n is even then $ n^{n - 1}$ is not a quadratic residue mod p . Applying property of Jacobi's symbol we have $ n$ is also a nonquadartic residue mod p when $ n$ is even . If $ p > 3$ then $ 4$ is an even number and a quadratic residue mod p and we will have contradiction . Thus $ p$ must be equal 3 and it is easy to check that $ 3$ is a suitable number . Hence ,all numbers satisfy condition are $ k = 2$ and $ k = 3$

This seems to be a hard problem unless I'm missing an easy trick. We try to rule out all cases $ k > 3$ For primes we can find $ (m,n)$ as described by Ahwingsecretagent above. For numbers that have a square factor greater than one $ x^2 | k$ then we take $ m = \frac{k}{x}$ and $ n = k$ For numbers that are products of two primes $ k = pq, p < q$ consider two cases: 1st case: $ p \nmid q-1$: solve $ m = ap \equiv 1 \bmod{q}$ for $ 0 < a < q$ and solve $ n = bp \equiv 1 \bmod{q-1}$ for $ 0 < a < q$ these have solutions because $ (p,q) = (p,q-1) = 1$ $ m^{m-1} \equiv 0 \bmod{p}$ and $ n^{n-1} \equiv 0 \bmod{p}$ $ m^{m-1} \equiv 1 \bmod{q}$ and $ n^{n-1} \equiv 1 \bmod{p}$ so $ m^{m-1} \equiv n^{n-1} \bmod{pq}$ as required 2nd case $ p \mid q-1$: then take $ m=1$ and $ n = \phi(k) +1 = (p-1)(q-1) + 1$ which works because $ (k,n) = 1$ This leaves cases where $ k$ is the product of 3 or more distinct primes

TTsphn i don't understand something if p | n-1 and q | n+1 then pq | n^2-1 or n | n^2-1 what have I misunderstood just for record only three guys got more then one point on this task (8,5,4) i got one point on proving its impossible for even k(>2)

It's just a typo. Where he has $ n = pq$ it should be $ k = pq$. $ n$ is a different number.

And it's not corect. For example: $ p=3$ and $ q=5$. $ 4=1$ mod $ 3$ and $ 4=-1$ mod $ 5$ but $ 4^3=4$ mod $ 15$ but $ 4\neq 1,-1$ mod $ 15$ The correction of the part why an odd $ k$ can have only one distinct prime devisor should be: by chinese reminder theorem we have $ n_1=1$ mod $ p$, $ n_1=-1$ mod $ q$ and $ n_2=-1$ mod $ p$, $ n_2=1$ mod $ q$. Obviously $ n_1,n_2\neq 1,-1$ and $ n_1\neq n_2$ mod $ k$ ($ k=pq$). $ n_1+n_2=0$ mod $ p$ and $ n_1+n_2=0$ mod $ q$ therefore $ n_1+n_2=0$ mod $ k$. but since $ 1\leq n_1,n_2\leq k$ we have $ n_1+n_2=k$ Since $ k$ is odd one of $ n_1,n_2$ is odd. wlog let it be $ n_1$. Than $ n_1^{n_1-1}=1^{n_1-1}=1$ mod $ p$ and $ n_1^{n_1-1}=(-1)^{n_1-1}=1$ mod $ q$ (because $ n_1-1$ is even). therefore $ n_1^{n_1-1}=1$ mod $ k$ by chinese reminder theorem. idea of alternative solution: if $ n$ is odd than $ n^{n-1}$ is a quadratic residue mod $ k$. The numbers $ 1^0,3^2,5^4..$ are all quadratic residues mod $ k$. The number $ 4^3=8^2$ is also a quadratic residue. But there are roughly $ \frac{k}{2}$ distinct quadratic residues for odd $ k>3$...

I agree that the solution of TTsphn is incorrect. However the quadratic residue method proposed by Jure the frEEEk can easily be made to work. The number of distinct quadratic residues $ \bmod{k}$ is at most $ [\frac{k}{2}] + 1$. That is because $ (-x)^2 \equiv x^2 \bmod{k}$ and $ x \equiv -x \bmod{k}$ has one or two solutions $ \bmod{k}$ according to whether $ k$ is odd or even. $ n^{n-1}$ is a quadratic residue $ \bmod{k}$ if $ n$ is odd or if $ n$ is a square or if $ n=k$. For $ k \ge 5$ this gives more quadratic residues than the number of distinct residues $ \bmod{k}$ so there must be some that are $ \equiv \bmod{k}$

PhilG wrote: I agree that the solution of TTsphn is incorrect. However the quadratic residue method proposed by Jure the frEEEk can easily be made to work. The number of distinct quadratic residues $ \bmod{k}$ is at most $ [\frac {k}{2}] + 1$. That is because $ ( - x)^2 \equiv x^2 \bmod{k}$ and $ x \equiv - x \bmod{k}$ has one or two solutions $ \bmod{k}$ according to whether $ k$ is odd or even. $ n^{n - 1}$ is a quadratic residue $ \bmod{k}$ if $ n$ is odd or if $ n$ is a square or if $ n = k$. For $ k \ge 5$ this gives more quadratic residues than the number of distinct residues $ \bmod{k}$ so there must be some that are $ \equiv \bmod{k}$ Excuse me ! . This is also my idea when I see this problem again . Indeed ,we can find the number of quadratic residue mod $ n$ but in this case ,your idea is enough to solve this problem .

FelixD wrote: Determine all integers $ k\ge 2$ such that for all pairs $ (m$, $ n)$ of different positive integers not greater than $ k$, the number $ n^{n-1}-m^{m-1}$ is not divisible by $ k$.

Ahwingsecretag wrote: Otherwise $ k$ is prime and greater than $ 3$ so we can choose $ n=k-1,m=\frac{k+1}{2}$ or $ n=1,m=\frac{k+1}{2}$, and we are done by FLT. can anyone explain this please. thanks