Разрешимое сравнение

[nnosipov]

vorvalm в сообщении #890842 писал(а):

Действительно

$x^p+y^p\equiv x+y\pmod {p^2}$.

Да, только это верно по модулю $p$, а не $p^2$. Это ещё вчера Whitaker заметил, но его сообщение об этом куда-то исчезло.

На самом деле при подстановке $y=1-x$ мы даже не рискуем пройти мимо какого-нибудь решения сравнения $x^p+y^p \equiv 1 \pmod{p^2}$. Таким образом, задача сводится к доказательству разрешимости сравнения $x^p+(1-x)^p \equiv 1 \pmod{p^2}$.

[vorvalm]

nnosipov в сообщении #890849 писал(а):

Да, только это верно по модулю $p$, а не $p^2$.

Какую роль в этой задаче играет $p=6n+1$?
Можно ли утверждать, что если

$x^p+y^p\equiv 1\pmod{p^2}$, то

$x+y\equiv 1\pmod{p^2}$

[nnosipov]

vorvalm в сообщении #890907 писал(а):

Какую роль в этой задаче играет $p=6n+1$?

Существенную. Для иных $p$ сравнение может оказаться неразрешимым.

vorvalm в сообщении #890907 писал(а):

Можно ли утверждать, что если

$x^p+y^p\equiv 1\pmod{p^2}$, то

$x+y\equiv 1\pmod{p^2}$

Нельзя: первое сравнение не изменится, если к $x$ и $y$ добавить произвольные числа, кратные $p$; второе же сравнение при этом может перестать быть верным.

[vorvalm]

Спасибо.

[Sonic86]

Все-таки решилось практически в лоб:
Как уже выяснили, $x+y\equiv 1\pmod {p^2}$, так что нужно найти нетривиальное решение сравнения $x^p+(1-x)^p\equiv 1 \pmod{p^2}$.
Положим $x\equiv t+1$:
$(t+1)^p-t^p-1\equiv 0\pmod{p^2}$
Возведем 1-ю скобку в $p$-ю степень по биному Ньютона, крайние члены сократим, сократим на $p$:
$\sum\limits_{k=1}^{p-1}t^k\frac{(p-1)...(p-(k-1))}{k!}\equiv 0\pmod{p}\Lefrightarrow$
$\sum\limits_{k=1}^{p-1}t^k(-1)^{k-1}\frac{1}{k}\equiv 0\pmod{p}$
$t\equiv -u, x\equiv -u+1, u=y$:
$\sum\limits_{k=1}^{p-1}\frac{y^k}{k}\equiv 0\pmod{p}$
Теперь уже несложно заметить, что если $y$ - решение, то и $y^{-1}$ - решение (это можно было заметить даже в самом начале). Оказывается, что $y=-\omega$ - корень уравнения, где $\omega: \omega^3\equiv 1, \omega\not\equiv 1$, и $\omega$ существует, поскольку $3\mid p-1$.
Проверяем: подставляем, приводим подобные, получаем соотношение, которое надо доказать:
$c_0+c_1\omega+c_2\omega^2\equiv 0\pmod{p}$, где
$c_0=\sum\limits_{m=1}^{\frac{p-1}{6}}\left(\frac{1}{6m}-\frac{1}{6m-3}\right)$
$c_1=\sum\limits_{m=1}^{\frac{p-1}{6}}\left(\frac{1}{6m-2}-\frac{1}{6m-5}\right)$
$c_2=\sum\limits_{m=1}^{\frac{p-1}{6}}\left(-\frac{1}{6m-1}+\frac{1}{6m-4}\right)$
Соотношение будет верно $\Leftirghtarrow c_0\equiv c_1\equiv c_2\pmod{p}$.
Дальше я не утерпел и доказываю это грубо в лоб: проверяю 2 соотношения $c_0\equiv c_1$ и $c_0\equiv c_2$. Я переношу все слагаемые в одну часть, привожу к общему знаменателю, знаменатель выкидываю, получаю сумму четырех приведенных кубичных многочленов, у которых 2 знака $+$, а еще 2 знака - $-$. Т.е. кубические члены сокращаются сразу. Чуть позже обнаруживается, что квадратичные слагаемые тоже сокращаются. В результате у меня получились соотношения
$\sum\limits_{m=1}^{\frac{m-1}{6}}(12m-5)\equiv 0\pmod p$ и
$\sum\limits_{m=1}^{\frac{m-1}{6}}(12m-1)\equiv 0\pmod p$
Суммируя в лоб, получаем суммы $\frac{p-1}{6}(p-1+6-5)$ и $\frac{p-1}{6}(p-1+1)$, сравнимые с нулем по модулю $p$.

Но осталось такое ощущение, что можно как-то проще (проверка равенства коэффициентов явно излишне усложнена). Кроме того, хочется найти все $p$, при которых сравнение разрешимо. А еще лучше - найти число решений сравнения (уже есть как минимум 2 пары решений)

[nnosipov]

Sonic86, спасибо, хорошее решение. Почему бы и не в лоб, если получается. Мне понравилась найденная Вами форма задачи, где возникает уравнение $\sum\limits_{k=1}^{p-1}\frac{y^k}{k}\equiv 0\pmod{p}$. У меня, действительно, немного попроще: дело в том, что многочлен $x^p+(1-x)^p-1$ тупо делится на $x^2-x+1$ при $p \equiv \pm 1 \pmod{6}$ (над кольцом $\mathbb{Z}$), поэтому достаточно суметь решить сравнение $x^2-x+1 \equiv 0 \pmod{p^2}$, а это понятно когда возможно и как.

По поводу любых $p$ и/или всех решений: по-моему, тёмный лес, никаких идей. Вообще, эту задачу я вытащил из чулана (и она, формально говоря, даже не моя), мне показалось, вполне сгодится для школьных олимпиад (а в Вашем варианте я бы и студентам не постеснялся предложить).

[nnosipov]

Впрочем, сам сюжет фактически известен. Например, задача М2173 из "Кванта" состоит в следующем.

Пусть $p>3$ --- простое число, $a$, $b$ --- такие целые числа, что $a^2+ab+b^2$ делится на $p$. Докажите, что $(a+b)^p-a^p-b^p$ делится на $p^3$.

Год-два назад эта задача обсуждалась на dxdy.

[rightways]

А как доказывается разрешимость сравнении

$x^2-x+1\equiv 0 (mod p=6k+1) $ и $x^p+(1-x)^p-1\equiv 0 (mod x^2-x+1) $
С помощью примитивных корней не получилось.

А может через символов Якоби получится решить задачу?


И.. где можно научиться решать как в решении Sonic86 ну типа использовать $w^3\equiv 1$ есть хороший материал?

[Mathusic]

rightways в сообщении #892719 писал(а):

$x^p+(1-x)^p-1\equiv 0 \pmod{x^2-x+1}$

Это верно в поле комплексных чисел, а, значит, для целых чисел тоже.
Проверьте.

rightways в сообщении #892719 писал(а):

$x^2-x+1\equiv 0 \pmod {p=6k+1} $

Решение будет, если будет у $x^2 \equiv (-1)^2-4\cdot1\cdot 1=-3 \pmod {p^2}$ (и, наверно, вы имели в виду все-таки $\pmod {p^2}$).

(Оффтоп)

a \equiv b \pmod{p^2}

$a \equiv b \pmod{p^2}$

[Sonic86]

rightways в сообщении #892719 писал(а):

$x^p+(1-x)^p-1\equiv 0 (mod x^2-x+1) $

$x^p+(1-x)^p-1\equiv x^p+x^{2p}-1$, потом $x^6\equiv 1\pmod{x^2-x+1}$, значит $x^p+x^{2p}-1\equiv x^{p\bmod 6}+x^{2p\bmod 6}-1$, дальше понятно.

rightways в сообщении #892719 писал(а):

И.. где можно научиться решать как в решении Sonic86 ну типа использовать $w^3\equiv 1$ есть хороший материал?

Не знаю Айрленд Роузен Классическое введение в современную ТЧ + можно почитать про алгебраические числа и конечные поля. И задачки порешать. Я сам не знаю.

rightways в сообщении #892719 писал(а):

А может через символов Якоби получится решить задачу?

Я когда-то пробовал, у меня не получилось. Попробуйте. (мои попытки тогда закончились чем-то левым и малоинтересным: post291144.html#p291144)

nnosipov в сообщении #892387 писал(а):

дело в том, что многочлен $x^p+(1-x)^p-1$ тупо делится на $x^2-x+1$ при $p \equiv \pm 1 \pmod{6}$ (над кольцом $\mathbb{Z}$)

Ааа, блин, значит переусложнил доказательство. Факт делимости от подстановки-то не зависит