Городская олимпиада по математике среди физ-мат школАлматы, 2012 год

Пусть дано натуральное число $n$, а $m$ — целое число из множества $\{0,\text{ }1,\text{ }...\text{ },\text{ }{{n}^{2}}-1\}$ такое, что число ${{x}^{n}}+{{y}^{n}}-m$ не делится на ${{n}^{2}}$ ни при каких целых $x$ и $y$. Докажите, что количество таких $m$ не меньше $\frac{n(n-1)}{2}$. ( М. Кунгожин )

Комментарий/решение

Заметим такой факт: $(x+n)^n \equiv x^n+C_{n}^1 n x^{n-1}+...+n^n \equiv x^n (mod n^2)$

Это означает что $x^n$ может давать максимум $n$ различных остатков( $0^n,1^n,2^n,...,(n-1)^n$). Из этого вытекает что $x^n+y^n$ дают не больше $n(n+1)/2$ различных остатков. Очевидно что таких $m$ не меньше $n^2-(n+1)n/2=n(n-1)/2$.