2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Разрешимое сравнение
Сообщение28.07.2014, 10:56 
Заслуженный участник


20/12/10
8858
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}$.

 Профиль  
                  
 
 Re: Разрешимое сравнение
Сообщение28.07.2014, 12:51 


31/12/10
1555
nnosipov в сообщении #890849 писал(а):
Да, только это верно по модулю $p$, а не $p^2$.

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

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

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

 Профиль  
                  
 
 Re: Разрешимое сравнение
Сообщение28.07.2014, 12:56 
Заслуженный участник


20/12/10
8858
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$; второе же сравнение при этом может перестать быть верным.

 Профиль  
                  
 
 Re: Разрешимое сравнение
Сообщение28.07.2014, 13:20 


31/12/10
1555
Спасибо.

 Профиль  
                  
 
 Re: Разрешимое сравнение
Сообщение01.08.2014, 16:55 
Заслуженный участник


08/04/08
8556
Все-таки решилось практически в лоб:
Как уже выяснили, $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 пары решений)

 Профиль  
                  
 
 Re: Разрешимое сравнение
Сообщение01.08.2014, 18:34 
Заслуженный участник


20/12/10
8858
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$ и/или всех решений: по-моему, тёмный лес, никаких идей. Вообще, эту задачу я вытащил из чулана (и она, формально говоря, даже не моя), мне показалось, вполне сгодится для школьных олимпиад (а в Вашем варианте я бы и студентам не постеснялся предложить).

 Профиль  
                  
 
 Re: Разрешимое сравнение
Сообщение02.08.2014, 10:10 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Разрешимое сравнение
Сообщение02.08.2014, 13:32 


24/12/13
351
А как доказывается разрешимость сравнении

$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$ есть хороший материал?

 Профиль  
                  
 
 Re: Разрешимое сравнение
Сообщение02.08.2014, 20:39 
Аватара пользователя


14/08/09
1140
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}$

 Профиль  
                  
 
 Re: Разрешимое сравнение
Сообщение03.08.2014, 13:03 
Заслуженный участник


08/04/08
8556
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$ есть хороший материал?
Не знаю :roll: Айрленд Роузен Классическое введение в современную ТЧ + можно почитать про алгебраические числа и конечные поля. И задачки порешать. Я сам не знаю.

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}$)
Ааа, блин, значит переусложнил доказательство. Факт делимости от подстановки-то не зависит :roll:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group