Азиатско-Тихоокеанская математическая олимпиада, 2014 год

Найдите все натуральные $n$, для которых при любом целом $k$ существует такое целое $a$, что $a^3 + a - k$ кратно $n$. ( Warut Suksompong )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ.Все натуральные $n = 3^b,$ где $b$ — неотрицательное целое.
Решение. Нам нужны такие $n$, что множество $A = \{a^3 + a\ |\ a \in \mathbf{Z} \}$ является полной системой вычетов по модулю $n$. Будем называть это свойство свойством (*). Нетрудно увидеть, что $n = 1$ удовлетворяет (*), а $n = 2$ — нет. Также ясно, что для выполнения свойства (*) число $n$ необходимо должно быть нечетным.
Если $a \equiv b \pmod{n},$ то $a^3 + a \equiv b^3 + b \pmod{n}$. Таким образом, $n$ удовлетворяет (*) тогда, и только тогда, когда не существует $a,b \in \{0, \ldots, n-1 \}$ с условиями $a \ne b$ и $a^3 + a \equiv b^3 + b \pmod{n}.$
Покажем, что $3^j$ удовлетворяет (*) для всех $j \ge 1.$ Пусть $a^3 + a \equiv b^3 + b \pmod{3^j}$ для $a \ne b.$ Тогда $(a-b)(a^2 + ab + b^2 + 1) \equiv 0 \pmod{3^j}.$ Можно легко проверить, что $a^2 + ab + b^2 + 1$ никогда не делится на $3$.
Теперь заметим, что если множество $A$ не содержит полной системы вычетов по модулю $r$, то не содержит и полной системы вычетов по модулю любого кратного $r$. Иными словами, нам достаточно доказать, что $p > 3$ не удовлетворяет свойству (*).
Если $p \equiv 1 \pmod{4},$ то существует такое $b$, что $b^2 \equiv -1 \pmod{p}.$ Далее, возьмем $a = 0$ и получим сравнение $a^3 + a \equiv b^3 + b \pmod{p}$.
Теперь предположим, что $p \equiv 3 \pmod{4}.$ Докажем, что существуют такие целые $a,b \not\equiv 0 \pmod{p}$, что $a^2 + ab + b^2 \equiv -1 \pmod{p}.$ Полагая $c$ обратным к $b$ по модулю $p$ (то есть $bc \equiv 1 \pmod{p}$), получим эквивалентное соотношение $(ac)^2 + ac + 1 \equiv -c^2 \pmod{p}.$ Заметим, что $-c^2$ может принимать все значения квадратичных невычетов по модулю $p$. Если мы сможем найти такое $x$, что $x^2 + x + 1$ является квадратичным невычетом по модулю $p$, то эти значения $a$ и $c$ подходят.
Заметим, что если различные $x,y \in \{ 0, \ldots, p-1\} = B,$ то $x^2 + x + 1 \equiv y^2 + y + 1 \pmod{p}$ тогда, и только тогда, когда $p$ делит $x + y + 1$. Следовательно, $x^2 + x + 1$ принимает ровно $(p+1)/2$ значений по модулю $p$, когда $x$ пробегает $B$. Поскольку существует ровно $(p-1)/2$ квадратичных невычетов по модулю $p$, среди $(p+1)/2$ значений $x^2 + x + 1$ в случае, когда там нет ни одного квадратичного невычета, должен быть $0$ и все квадратичные вычеты.
Пусть $C$ — множество квадратичных вычетов по модулю $p$ и $0$, и пусть $y \in C$. Предположим, что $y \equiv z^2 \pmod{p}$ и возьмем $z \equiv 2w + 1 \pmod{p}$ (мы всегда можем выбрать такое $w$). Тогда $y + 3 \equiv 4(w^2 + w + 1) \pmod{p}.$ Из предыдущей части решения мы знаем, что $4(w^2 + w + 1) \in C$. Это означает, что $y \in C \implies y + 3 \in C.$ Из этого соотношения следует, что все элементы $B$ лежат в $C$ — противоречие. Это завершает доказательство.

Решение 1: Докажем, что сущ. $a,b,$ что $p\mid a^2+ab+b^2+1\iff p\mid (2a+b)^2+3b^2+4,$ где $p>3.$

Заметим, что $\{x^2\}$ дает $\dfrac{p+1}{2}$ различных остатков по модулю $p,$

и $\{-3y^2-4\}$ тоже дает $\dfrac{p+1}{2}$ различных остатков. Тогда эти два множества имеют два сравнимых элемента, т.е. $\exists x,y:$

$$x^2\equiv -3y^2-4 \iff x^2+3y^2+4\equiv 0\pmod p.$$

Тогда $a\equiv \dfrac{x-y}{2}$ и $b\equiv y$ подходит под наше утверждение. $\square$

Решение 2: Заметим, что для $p>2:$

$$\prod_{\forall a\not\equiv 0} a \equiv \prod_{\forall a\not\equiv 0} (a^3+a)\pmod p\implies\prod_{\forall a\not\equiv 0} (a^2+1) \equiv 1\pmod p$$

Заметим, что

$$P(1)\equiv\prod_{\forall x\not\equiv 0} (x^2+1)\equiv \prod_{\forall x\not\equiv 0} (x+i)\prod_{\forall x\not\equiv 0} (x-i) \equiv (i^{p-1}-1)^2\equiv 2-2i^{p-1},$$

где преобразования происходили в $F_{p}.$ Здесь мы использовали утверждение

$$Q(y)\equiv(1+y)(2+y)\ldots((p-1)+y)\equiv y^{p-1}-1.$$

Заметим, что в зависимости от остатка $p$ по модулю $4,$ либо $2-2i^{p-1}=0,$ либо $2-2i^{p-1}=4,$ откуда

$$1\equiv P(1)\equiv 2-2i^{p-1}\equiv \{0,4\}\pmod p\implies p=3.\square$$

Комментарий: Утверждение, что $P(1)\equiv \{0,4\}$ можно было объяснить посредством многочлена $(x-1)^{\frac{p-1}{2}}-1,$ у которого произведение корней в квадрате как раз таки равно $P(1).$