Distinct Remainders, a problem from IMOQ.

 Here is a cute problem for IOQM.

What is the smallest $n$ such that $1^4, 2^4, \dots , 14^4$ all leave distinct remainders when divided by $n$?

Solution.

Now $x^4 - y^4$ = $(x-y)(x+y)(x^2+y^2)$, we want this to be non-zero $\mod n$.

If $n \lt 28$, then we can find distinct $x, y \le 14$ such tht $x+y = n$.

We also have that $(13+1)(13-1)$ is divisible by $28$.

$29 = 5^2 + 2^2$

$(11+1)(11-1)$ is divisible by $30$.

Now consider $n=31$. For $31$ to not be a candidate we must have that $x^2+y^2$ is divisible by $31$.

But, it is well known that if $p$ is a prime of the form $4m+3$, and it divides $x^2+y^2$, then it divides $x$ and $y$.

Thus $31$ is our answer.