2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Два произведения по модулю простого числа
Сообщение15.04.2019, 21:11 
Заслуженный участник


20/12/10
8858
Пусть $p=6k-1$ --- простое число. Положим $$A=\prod_{1 \leqslant x<y \leqslant p-1}(x^2+xy+y^2), \quad B=\prod_{1 \leqslant x<y \leqslant p-1}(x^2-xy+y^2).$$ Докажите, что $A \equiv (-1)^k \pmod{p}$, а $B \equiv 1 \pmod{p}$.

P.S. Возможно, что что-то подобное уже было, но не припоминаю.

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение16.04.2019, 01:55 
Аватара пользователя


07/01/16
1426
Аязьма
Только смутные догадки, решить у меня, к сожалению, культуры не хватает; пусть $$A=\prod_{1 \leqslant x<y \leqslant p-1}(x^2+xy+y^2),B=\prod_{1 \leqslant x,y \leqslant p-1}(x^2+xy+y^2)$$тогда $$B=A^2\prod\limits_{1 \leqslant  x\leqslant p-1}3x^2=A^23^{p-1}(p-1)!^2\equiv A^2\pmod{p}$$по теореме Вильсона и МТФ. Чтобы найти $B\bmod{p}$, будем рассматривать произведения при $x+y=\operatorname{const}$; они... выстраиваются неким чудодейственным образом... и дают $B\equiv1\pmod{p}\Rightarrow A\equiv\pm1\pmod{p}$. Как понять, плюс или минус единица, у меня тоже пробел

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение16.04.2019, 03:46 
Аватара пользователя


07/01/16
1426
Аязьма
waxtep в сообщении #1387954 писал(а):
Чтобы найти $B\bmod{p}$, будем рассматривать произведения при $x+y=\operatorname{const}$
ага, похоже, удобнее рассматривать произведения при $x-y=\operatorname{const}$; каждое из них - степень тройки, и все вместе они дают $3^{2(p-1)}\equiv1\pmod{p}$

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение16.04.2019, 04:00 
Заслуженный участник


20/12/10
8858
waxtep в сообщении #1387962 писал(а):
похоже, удобнее рассматривать произведения при $x-y=\operatorname{const}$
Возможно, но побольше бы деталей (я так не пробовал). А для $A$ почему не работает?

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение17.04.2019, 01:02 
Аватара пользователя


07/01/16
1426
Аязьма
nnosipov в сообщении #1387964 писал(а):
А для $A$ почему не работает?
Да, переход к $B$ совершенно лишний, при $x-y=\operatorname{const}$ можно прямо работать с $A$. Но, к сожалению, похоже все это никуда не ведет :-( то есть, конечно, любое ненулевое число по модулю $p$ эквивалентно тройке в некоторой натуральной степени, но закономерность в этих степенях мне, видимо, только почудилась. Например, одно из произведений для $p=17$, $$\prod_{y=x+12}(x^2+xy+y^2)\equiv2\equiv3^{14}\pmod{17}$$а кхм $14$-ая степень не выглядит естественно в данной задаче

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение17.04.2019, 06:38 
Заслуженный участник


20/12/10
8858
waxtep
Давайте хотя бы с $B$ разберемся. Напишите, пожалуйста, более подробно, как именно получаются степени тройки и с какими показателями. (Пытался, но не смог понять.) Ситуация с $B$ технически проще (с точки зрения той общей идеи, с помощью которой решаются оба пункта), но вдруг с $B$ можно справиться и принципиально проще?

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение18.04.2019, 00:21 
Аватара пользователя


07/01/16
1426
Аязьма
nnosipov в сообщении #1388187 писал(а):
Давайте хотя бы с $B$ разберемся.
С тройками ничего внятного у меня не получается, может быть, вот так:$$A=\prod_{1 \leqslant x<y \leqslant p-1}(x^2+xy+y^2)=\frac{\prod\limits_{1 \leqslant x<y \leqslant p-1}(y^3-x^3)}{\prod\limits_{1 \leqslant x<y \leqslant p-1}(y-x)}=\frac{\prod\limits_{1 \leqslant x<y \leqslant p-1}(y^3-x^3)}{\prod\limits_{1 \leqslant x\leqslant p-2}x!}$$Произведение в числителе (с сомножителями, взятыми по модулю $p$) выглядит перестановкой произведения в знаменателе, с минусом в случае нечетной перестановки. Доказать пока не пробовал

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение18.04.2019, 06:50 
Заслуженный участник


20/12/10
8858
Идея понятна (перестановки --- идея доказательства квадратичного взаимности по Золотареву), но вот реализация не очевидна.

Лично меня эта задача удивляет тем, что для $A$ и $B$ получаются разные ответы, хотя, казалось бы, "из соображений симметрии" они не должны отличаться.

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение20.04.2019, 03:03 
Аватара пользователя


07/01/16
1426
Аязьма
nnosipov в сообщении #1388362 писал(а):
Идея понятна (перестановки --- идея доказательства квадратичного взаимности по Золотареву), но вот реализация не очевидна.
Попытаюсь завершить, правда, в строгости рассуждения у меня некоторые сомнения:
1. Для любой последовательности $a_i,1\leqslant i\leqslant n$ произведение $\prod\limits_{1\leqslant i<j\leqslant n}(a_j-a_i)$ сохранит абсолютную величину и поменяет знак при перестановке любых двух соседних членов; значит, любая четная перестановка членов сохранит величину данного произведения, а нечетная - поменяет знак.
2. Последовательность $(x^3\bmod p), x\in\mathbb{N},  1\leqslant x\leqslant p-1$ при $p\in\mathbb{P}, p\ne3$ - перестановка последовательности $(x)$; значит, $A\equiv\pm1\pmod p$ (как отношение произведений из п.1), в зависимости от четности перестановки $(x^3\bmod p)$; достаточно рассмотреть $2\leqslant x\leqslant p-2$, поскольку $x=1$ и $x=p-1$ останутся на своих местах.
3. Посмотрим на последовательность чисел, остатки от деления которых на $p$ совпадают с $(x^3\bmod p),2\leqslant x\leqslant p-2$:$$8,27,64,\ldots,-64,-27,-8$$Чтобы упорядочить эту последовательность по абсолютной величине, необходимо перенести $3k-2$ чисел на $6k-5$ позиций каждое; т.е. четность этой перестановки $(3k-2)(6k-5)\bmod2$ равна четности числа $k$ и $A\equiv(-1)^k\pmod p$

-- 20.04.2019, 03:12 --

nnosipov в сообщении #1388362 писал(а):
Лично меня эта задача удивляет тем, что для $A$ и $B$ получаются разные ответы, хотя, казалось бы, "из соображений симметрии" они не должны отличаться.
Елки-палки, я еще и Ваше $B$ нечаянно переобозначил, извините; только сейчас заметил. В общем, я пытался решить только задачу для $A$, и в моих обозначениях $B$ совсем не то же, что у Вас

-- 20.04.2019, 03:24 --

Ага, тогда, если мое рассуждение для $A$ можно "дотянуть" до уровня математической строгости, то для $B$ (в Ваших обозначениях) еще проще: срабатывает то, что произведение $\prod\limits_{1\leqslant i<j\leqslant n}(a_j+a_i)$ сохраняет величину (и не меняет знак) при перестановке любых двух соседних членов; значит, $B\equiv1\pmod p$

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение20.04.2019, 04:02 
Заслуженный участник


20/12/10
8858
waxtep
если это довести до ума, то получится очень симпатичное решение. Пока не готов комментировать более детально.

С $A$ и $B$ --- это я виноват, свои $A$ и $B$ я добавил позже, первоначально в условии задачи их не было (я подумал, что у Вас опечатка, а Вы имели в виду совсем другое).

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение20.04.2019, 20:41 


30/03/08
196
St.Peterburg
Пусть : $\  \ \varepsilon_1= e^{\frac{\pi i}{3}}\ , \  \varepsilon_2= e^{\frac{2\pi i}{3}}$

$ f(z)=(1+z)(2+z) \ .\ .\ .\ ((p-1)+z)$

Тогда :
$$\dfrac{f(\varepsilon_1)\cdot f(2\varepsilon_1)  \ \ .\   \   .\  \    . \      f((p-1)\varepsilon_1)}{(p-1)! \cdot (1+\varepsilon_1)^{p-1}}= A\  \cdot \ \varepsilon_1^{\frac{(p-1)(p-2)}{2}}\ , \ \ \ \ \  \dfrac{f(\varepsilon_2)\cdot f(2\varepsilon_2)  \  \ .  \  \  .\   \ . \    f((p-1)\varepsilon_2)}{(p-1)! \cdot (1+\varepsilon_2)^{p-1}}= B\ \cdot \ \varepsilon_2^{\frac{(p-1)(p-2)}{2}}$$

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение20.04.2019, 21:58 
Заслуженный участник


20/12/10
8858
Sergic Primazon в сообщении #1388759 писал(а):
Пусть : $\  \ \varepsilon_1= e^{\frac{\pi i}{3}}\ , \  \varepsilon_2= e^{\frac{2\pi i}{3}}$

$ f(z)=(1+z)(2+z) \ .\ .\ .\ ((p-1)+z)$

Тогда :
$$\dfrac{f(\varepsilon_1)\cdot f(2\varepsilon_1)  \ \ .\   \   .\  \    . \      f((p-1)\varepsilon_1)}{(p-1)! \cdot (1+\varepsilon_1)^{p-1}}= A\  \cdot \ \varepsilon_1^{\frac{(p-1)(p-2)}{2}}\ , \ \ \ \ \  \dfrac{f(\varepsilon_2)\cdot f(2\varepsilon_2)  \  \ .  \  \  .\   \ . \    f((p-1)\varepsilon_2)}{(p-1)! \cdot (1+\varepsilon_2)^{p-1}}= B\ \cdot \ \varepsilon_2^{\frac{(p-1)(p-2)}{2}}$$
Вот, решения с многочленами нам действительно не хватает.

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение08.07.2019, 06:13 
Заслуженный участник


20/12/10
8858
Sergic Primazon
Вы не могли бы пояснить первое из Ваших равенств (с буквой $A$)? У меня $$A=\prod_{1 \leqslant x<y \leqslant p-1}(x^2+xy+y^2)$$и при $p=5$ равенства нет. Это у Вас опечатки или я неправильно вычислил?

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение02.08.2019, 08:51 
Заслуженный участник


20/12/10
8858
Так я и не смог разобраться в тексте от Sergic Primazon. Может кто-нибудь пояснить, что там написано? Автор что-то молчит.

 Профиль  
                  
 
 Re: Два произведения по модулю простого числа
Сообщение03.08.2019, 07:26 
Заслуженный участник


20/12/10
8858
На всякий случай сообщу, что задачу можно решать в общей постановке (иногда это проще). Именно, пусть $\alpha x^2+\beta xy+\gamma y^2$ --- квадратичная форма с дискриминантом $\delta=\beta^2-4\alpha\gamma$. Предположим, что простое число $p>2$ таково, что $(\delta/p)=-1$. Требуется вычислить произведение
$$
P=\prod_{0<x<y<p}(\alpha x^2+\beta xy+\gamma y^2)
$$
по модулю $p$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

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



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

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


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

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