XVI математическая олимпиада «Шелковый путь», 2017 год
Комментарий/решение:
Лемма 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$, что и требовалось доказать.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.