XVI математическая олимпиада «Шелковый путь», 2017 год

Пусть $p=9k+1$ — простое число, где число $k$ — натуральное. Докажите, что существует целое число $n$ такое, что ${{n}^{3}}-3n+1$ делится на $p$. ( Ануарбеков Т. )

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

Лемма 1:

Для любого простого $p=9k+1$ существует натуральное число $a$ такое, что

$a^9≡1 (mod p)$ и

$a^k≢1 (mod p)$

для всех $k=1,2,3….,8$.

Доказательство:

Пусть $x$- примитивный корень $p$, то есть $x^{p-1}≡1(mod p)$, но

$(x^{p-2}-1)(x^{p-3}-1)…(x-1)$ не делится на $p$. Тогда так как $9|p-1$ то в качестве нашего $a$, подходит число $a=x^{(p-1)/9}$, и следовательно $a^9≡1(mod p)$ и $a^k≢1 (mod p)$ для всех $k=1,2,3….,8$.

Лемма 2:

Для любого простого $p=9k+1$ существует натуральное число $a$ такое, что

$a^6+a^3+1$ делится на $p$.

Доказательство:

По лемме 1, имеем :

$a^9-1=(a^3-1)(a^6+a^3+1)⋮p$ .

И так как $a^3-1$ не делится на $p$, то отсюда следует что $a^6+a^3+1≡0 (mod p )$

Теперь в задаче, имеем:

$a^6+a^3+1≡0 (mod p )$

откуда $a$ и $p$ взаимно просты, значит существует такой $b$, что $ab≡1(mod p)$.

Следовательно, $$b^3(a^6+a^3+1)=

=a^3(ab)^3+a^3b^3+b^3≡

≡a^3+b^3+1=

=(a+b)^3-3ab(a+b)+1≡

≡(a+b)^3-3(a+b)+1=

=n^3-3n+1≡0 (mod p)$$

где $n=a+b$, что и требовалось доказать.