Множество из кв. вычетов и невычетов [Теория чисел]

[Whitaker]

Здравствуйте, уважаемые друзья!

Множество $\{1, 2, \dots, p-1\}$ разбито на два подмножества непустых, причем имеют место следующие свойства:
а) Произведение двух чисел одного подмножества сравнимо по модулю $p$ с числом первого подмножества.
б) Произведение двух чисел различных подмножеств сравнимо по модулю $p$ с числом второго подмножества.
Доказать, что это будет тогда и только тогда, когда первое подмножество состоит из квадратичных вычетов, а второе - из
квадратичных невычетов.

Достаточность является очевидным.
Необходимость: Обозначим первое множество через $A$ и пусть $A=\{a_1, a_2, \dots, a_k\}$, а второе - через $B$ и
пусть $B=\{a_{k+1}, a_{k+2}, \dots, a_{p-1}\}$.
Из свойства а) сразу понятно, что $A$ содержит числа сравнимые по модулю $p$ c $1^2, 2^2, \dots, \left(\dfrac{p-1}{2}\right)^2$, т.е.
в $A$ есть ВСЕ кв. вычеты по модулю $p$. Также понятно, что в $B$ не может быть кв. вычетов. Значит, в $B$ есть только
кв. невычеты. Покажем, что в $A$ ТОЛЬКО кв. вычеты. Пусть в нем есть кв. невычет. Пусть это будет $a'$ и $b\in B$, тогда
$a'b$ - кв. вычет и он сравним по модулю $p$ с каким-то элементом из B. Значит, в $B$ есть кв. вычет. Противоречие. Отсюда получаем то, что нам нужно.

Скажите пожалуйста правильны ли мои рассуждения?

С уважением, Whitaker.

[nnosipov]

Whitaker в сообщении #890538 писал(а):

Из свойства а) сразу понятно, что $A$ содержит числа сравнимые по модулю $p$ c $1^2, 2^2, \dots, \left(\dfrac{p-1}{2}\right)^2$, т.е.
в $A$ есть ВСЕ кв. вычеты по модулю $p$.

А почему понятно?

[Whitaker]

Постараюсь изложить как я сам понял.
У нас дано такое свойство:

Цитата:

а) Произведение двух чисел одного подмножества сравнимо по модулю $p$ с числом первого подмножества.

Так как $A=\{a_1, a_2, \dots, a_k\}$ и $B=\{a_{k+1}, a_{k+2}, \dots, a_{p-1}\}$ из свойства а) получаем, что $a_1\cdot a_1=a_1^2$ сравнимо с каким-то числом из $A$ и так далее $a_k\cdot a_k=a_k^2$ также сравнимо с каким-то число из А. Такую же процедуру применяем к элементам множества $B$ и получаем, что $a_{j}^2$ сравнимо с каким-то числом из $A$ при $j\in \{k+1, \dots, p-1\}$. Итого получаем, что в $A$ есть числа, сравнимые с $\{1^2, 2^2, \dots, (p-1)^2\}$, но так как $r^2\equiv (p-r)^2 \pmod p$, то можно взять множество $\{1^2, 2^2, \dots, \left(\frac{p-1}{2}\right)^2\}$. Также нетрудно показать эти числа попарно несравнимы по модулю $p$. А в приведенной системе вычетов по модулю $p$ квадратичные вычеты сравнимы как раз с числами множества $\{1^2, 2^2, \dots, \left(\frac{p-1}{2}\right)^2\}$. Т.е. в $A$ есть ВСЕ кв. вычеты по модулю $p$.

[nnosipov]

Ну да, я почему-то подумал, что по условию свойством а) обладает только множество $A$.

[Whitaker]

nnosipov
Спасибо за то, что посмотрели тему
После Вашего вопроса еще лучше разобрался.