7-я Международная Жаутыковская олимпиада, 2011 год

Пусть $n$ — целое число, $n > 1$. Элемент $a$ из множества $M=\{1, 2, \dots, n^2-1\}$ назовем хорошим , если найдется элемент $b$ из $M$ такой, что число $ab-b$ делится на $n^2$. Далее, элемент $a$ назовем очень хорошим , если $a^2-a$ делится на $n^2$. Пусть $g$ и $v$ — число хороших и число очень хороших элементов в $M$ соответственно. Докажите, что $v^2+ v\leq g\leq n^2-n$.

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

Докажем, что $g\le n^2-n.$ Любое число вида $a=i\cdot n,$ для любого $i=1,\ldots,n-1,$ нехорошее$.$ Иначе $$n^2\mid ab-b=b(a-1)\implies n^2\mid b, \quad\text{так как}\quad (a-1,n^2)=1.$$

Но тогда $n^2\le b\le n^2-1,$ противоречие. В следствии, хороших чисел не более $(n^2-1)-(n-1)=n^2-n,$ или же $g\le n^2-n.\quad\square$

Примечание: $a$ $-$ хорошее, тогда и только тогда, когда $gcd(a-1,n^2)>1.$