Два произведения по модулю простого числа

[nnosipov]

Пусть $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. Возможно, что что-то подобное уже было, но не припоминаю.

[waxtep]

Только смутные догадки, решить у меня, к сожалению, культуры не хватает; пусть

$$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}$. Как понять, плюс или минус единица, у меня тоже пробел

[waxtep]

waxtep в сообщении #1387954 писал(а):

Чтобы найти $B\bmod{p}$, будем рассматривать произведения при $x+y=\operatorname{const}$

ага, похоже, удобнее рассматривать произведения при $x-y=\operatorname{const}$; каждое из них - степень тройки, и все вместе они дают $3^{2(p-1)}\equiv1\pmod{p}$

[nnosipov]

waxtep в сообщении #1387962 писал(а):

похоже, удобнее рассматривать произведения при $x-y=\operatorname{const}$

Возможно, но побольше бы деталей (я так не пробовал). А для $A$ почему не работает?

[waxtep]

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$-ая степень не выглядит естественно в данной задаче

[nnosipov]

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

[waxtep]

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$) выглядит перестановкой произведения в знаменателе, с минусом в случае нечетной перестановки. Доказать пока не пробовал

[nnosipov]

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

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

[waxtep]

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$

[nnosipov]

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

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

[Sergic Primazon]

Пусть : $\ \ \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}}$$

[nnosipov]

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}}$$

Вот, решения с многочленами нам действительно не хватает.

[nnosipov]

Sergic Primazon
Вы не могли бы пояснить первое из Ваших равенств (с буквой $A$)? У меня

$$A=\prod_{1 \leqslant x<y \leqslant p-1}(x^2+xy+y^2)$$

и при $p=5$ равенства нет. Это у Вас опечатки или я неправильно вычислил?

[nnosipov]

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

[nnosipov]

На всякий случай сообщу, что задачу можно решать в общей постановке (иногда это проще). Именно, пусть $\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$.