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.$
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.