Найти образующие группы

[vpb]

$F^\ast_p=F_p\setminus\{0\}$ --- это всего лишь ее определение, а не то свойство, которое я имел в виду. Однако же,
по первому сообщению темы вижу, что таки знаете. Тогда такое задание, для выполнения которого Вы необходимы сведения имеете. Покажите, что если $p=4k+1$, то квадратный корень из $-1$ в $F^\ast_p$ есть, а если $p=4k-1$, то нет. Здесь $p$ --- любое нечетное простое число.

Или даже давайте еще подскажу. Пусть $Z_m$ --- циклическая группа порядка $m$, где $m$ четное, а $t$ --- элемент порядка $2$ в $Z_m$. Когда существует квадратный корень из $t$ в $Z_m$ ?

[wooddii]

vpb в сообщении #1313708 писал(а):

$F^\ast_p=F_p\setminus\{0\}$ --- это всего лишь ее определение, а не то свойство, которое я имел в виду. Однако же,
по первому сообщению темы вижу, что таки знаете. Тогда такое задание, для выполнения которого Вы необходимы сведения имеете. Покажите, что если $p=4k+1$, то квадратный корень из $-1$ в $F^\ast_p$ есть, а если $p=4k-1$, то нет. Здесь $p$ --- любое нечетное простое число.

Или даже давайте еще подскажу. Пусть $Z_m$ --- циклическая группа порядка $m$, где $m$ четное, а $t$ --- элемент порядка $2$ в $Z_m$. Когда существует квадратный корень из $t$ в $Z_m$ ?

Вспоминаю теоретико-числовые методы в криптографии.
$m = 2^k \cdot p^{\alpha_1}_1\cdot ... \cdot p^{\alpha_n}_n$, где $p_i - $ различные простые числа, не равные двум.
Квадратный корень из $t$ существует, если разрешимо сравнение $x^2 \equiv t (\mod m )$.
Такое сравнение разрешимо, если разрешимы все сравнения вида $x^2 \equiv t (\mod p^{\alpha_i}_i )$.
Каждое из них разрешимо, если $t$ - квадратичный вычет по модулю.
Порядок $t$ равен двум, значит $t^2 = 1$, то есть $t \equiv \pm 1 (\mod m)$.

Но теперь не об этом.
$F^*_p - $ циклическая группа. Её порядок равен $p-1$. Так как $p -$простое, любой элемент кроме единичного $-$ образующий. То есть порядок такого элемента также равен $p-1$. Рассмотрим $p=4k+1$. Если квадратный корень из $-1$ (обозначим его $i$) есть в $F^*_p$, то $i^{p-1} = i^{4k} = 1$, верно. В случае же $p=4k-1$, порядок $i$ равен $i^{4k-2}$, но $i^{4k-2} = -1$.
То есть если $p=4k+1$, то квадратный корень из $-1$ в $F^\ast_p$ есть, а если $p=4k-1$, то нет.

Верно?

[vpb]

Во-первых, Вы излагаете свои рассуждения недостаточно аккуратно. Более аккуратно --- это, например, так.
"Покажем, что если $p=4k-1$, то $F_p$ не содержит квадратного корня из $-1$. Предположим противное, и
пусть $i$ --- какой-либо корень. Поскольку $F^\ast_p$ --- группа порядка $p-1=4k-2$, то $i^{4k-2}=1$. С другой стороны, $i^{4k-2}=(i^4)^k(i^2)^{-1}=1^k(-1)^{-1}=-1$; противоречие. Значит, квадратного корня из $-1$ в $F_p$ нет."

Заметьте, что это рассуждение к случаю $p=4k+1$ никак приспособить нельзя.

Во-вторых, Вы путаете аддитивную и мультипликативную структуру на $Z_p$. Вообще, чтоб не было путаницы, лучше циклическую группу порядка $m$ обозначать $Z_m$ или $C_m$, кольцо вычетов по модулю $m$ --- ${\mathbb Z}_m$,
поле из $q$ элементов $F_q$ или ${\mathbb F}_q$. И не путать, в случае чего, одно с другим. Хотя, часто, для экономии, символ $Z_p$ употребляют во всех трех смыслах, но по контексту и ситуации обычно понятно, рассматриваем мы его как группу, как кольцо, или как поле.

Если $G$ --- группа, то корнем $n$-й степени из элемента $g\in G$ называют любой элемент $x$ такой, что $x^n=g$. Он может быть не единственен. Когда я задавал вопрос про корень в $Z_m$, я подразумевал именно группу, а не кольцо.
Короче, замените в том вопросе $Z_m$ на $C_m$, и переосмыслите его опять.

Про квадратичные вычеты Вы помните правильно, только это не совсем по делу.

wooddii в сообщении #1313731 писал(а):

Её порядок равен $p-1$. Так как $p -$простое, любой элемент кроме единичного $-$ образующий. То есть порядок такого элемента также равен $p-1$

Неверное утверждение. Возьмите хоть $p=5$.

[wooddii]

vpb в сообщении #1313855 писал(а):

wooddii в сообщении #1313731 писал(а):

Её порядок равен $p-1$. Так как $p -$простое, любой элемент кроме единичного $-$ образующий. То есть порядок такого элемента также равен $p-1$

Неверное утверждение. Возьмите хоть $p=5$.

Снова все напутал. Это верно для циклической группы порядка $p$, где $p -$ простое. А у нас порядок группы равен $2^s-2$.

Теперь про корни.
$t -$ элемент порядка 2, значит $t^2 = e$.
Пусть $x -$ квадратный корень из $t$. Значит $x^2 = t$, то есть $x^4 = e$. Это говорит о том, что в группе должен быть элемент порядка 4, то есть $4 | m$.

Ага!
Теперь, если у нас $p=4k+1$, то порядок группы $F^*_p$ равен $4k$, то есть в нём могут быть элементы порядка 4 по теореме Лагранжа. А если $p=4k-1$, то порядок группы $F^*_p$ равен $4k-2$, по этой же теореме там элементов порядка 4 нет, то есть нет и корня квадратного из $-1$.
Так?

-- 21.05.2018, 21:27 --

А у нас $p = 2^s - 1$. Это ведь $4k-1$ и есть, так как по условию $p -$ простое.

-- 21.05.2018, 21:29 --

То есть в $F^*_p$ нет элементов порядка 4,а в $F^*_q -$есть, если я правильно рассуждал выше.

[vpb]

wooddii в сообщении #1313940 писал(а):

Это говорит о том, что в группе должен быть элемент порядка 4, то есть $4 | m$

Является ли это условие достаточным ?

wooddii в сообщении #1313940 писал(а):

в нём могут быть элементы порядка 4 по теореме Лагранжа.

Могут быть, или наверняка есть ?

wooddii в сообщении #1313940 писал(а):

а в $F^*_q -$есть, если я правильно рассуждал выше.

Почему ?

[wooddii]

vpb в сообщении #1313951 писал(а):

wooddii в сообщении #1313940 писал(а):

Это говорит о том, что в группе должен быть элемент порядка 4, то есть $4 | m$

Является ли это условие достаточным ?

wooddii в сообщении #1313940 писал(а):

в нём могут быть элементы порядка 4 по теореме Лагранжа.

Могут быть, или наверняка есть ?

wooddii в сообщении #1313940 писал(а):

а в $F^*_q -$есть, если я правильно рассуждал выше.

Почему ?

Отвечаю по порядку.
Думаю оно является достаточным.

Наверняка есть! Так как группа порядка $4k$, то $a^{4k} = e$, или же $a^{k^4} = e$, то есть элемент $a^k$ имеет порядок 4.

Потому что порядок группы равен $(2^s-1)^2-1=2^s(2^s-2)$, то есть делится на 4.

-- 21.05.2018, 23:50 --

Худо-бедно на вопросы отвечаю, в единую картину все никак не сложится пока(

[vpb]

wooddii в сообщении #1313971 писал(а):

Худо-бедно на вопросы отвечаю, в единую картину все никак не сложится пока(

Если бы Вы имели привычку к чтению книжек и самостоятельной работе, то поняли бы, что, как говорит пословица, "скоро только кошки родятся". Однако продолжим.

$(a^k)^4$, а не $a^{k^4}$. Должен еще напомнить, что, вообще говоря, утверждение, обратное теореме Лагранжа, неверно в произвольных группах. А для циклических --- таки верно.

Есть такое утверждение: конечная подгруппа в мультипликативной группе произвольного поля всегда циклическая. Знаете ли такую теорему ? Кроме того, знаете ли ее доказательство ?

Докажите следующее утверждение. Пусть $X$ --- циклическая группа порядка $2^sr$, где $r$ --- четное число; $Y<X$ --- подгруппа порядка $r$ . Пусть $ a\in X$ --- элемент такой, что $a^{2^s}$ порождает $Y$. Тогда $a$ --- порождающий для $X$.

[wooddii]

Теорема была мне неизвестна. Ознакомился с её доказательством.

Теперь доказательство утверждения.
$a^{2^s}$ порождающий элемент $Y$, значит $(a^{2^s})^r = e$. То есть $a^{2^sr} = e$. Это означает, что $a -$ образующий элемент $X$, если $2^sr -$ это такое наименьшее натуральное число, что $a$ в его степени равен $e$. Пусть $a^k -$ образующий элемент $X$. Тогда $(a^k)^{2^sr} = a^{2^srk}$. Число $2^srk -$ натуральное. Получается, что $2^sr$ наименьшее такое число, таким образом, утверждение доказано.

[vpb]

wooddii в сообщении #1313971 писал(а):

Думаю оно является достаточным

Если является, то приведите доказательство.

wooddii в сообщении #1314107 писал(а):

$a^{2^s}$ порождающий элемент $Y$, значит $(a^{2^s})^r = e$.

Равенство $(a^{2^s})^r = e$ верно безотносительно к тому, является ли $a^{2^s}$ порождающим элементом для $Y$.

wooddii в сообщении #1314107 писал(а):

Это означает, что $a -$ образующий элемент $X$, если $2^sr -$ это такое наименьшее натуральное число, что $a$ в его степени равен $e$

Слова "это означает" ни при чем. Это просто определение того, что такое образующий элемент циклической группы.

wooddii в сообщении #1314107 писал(а):

Пусть $a^k -$ образующий элемент $X$

Так ведь если $a^k$ --- образующий для $X$, то $a$ тоже непременно образующий, в любом случае!

wooddii в сообщении #1314107 писал(а):

Тогда $(a^k)^{2^sr} = a^{2^srk}$. Число $2^srk -$ натуральное. Получается, что $2^sr$ наименьшее такое число, таким образом, утверждение доказано.

Это вообще нечто невразумительное.

В общем, я думаю, Вы в том, что пишете, и в том, как думаете, сильно путаетесь. У Вас же были в школе уроке геометрии, где среди прочего учат связно рассуждать. Посмотрите, как в книжках хороших (Кострикин, например, или Калужнин) строят рассуждения. Кроме того, вот в этой теме (ближе к концу) я на примерах (более элементарных) показывал другому человеку, что такое аккуратное рассуждение. Можете также заглянуть в книжку В.А.Успенский, Простейшие примеры математических доказательств.

В общем, Вам стоит стараться рассуждать и писать более аккуратно, а то и обсуждать, по сути, нечего. Такие дела.

[wooddii]

Спасибо большое за помощь, подсказки пригодились!
После сегодняшней лекции все встало на свои места и решил прям у доски.
Сначала показал, что i нет в поле $F^*_p$. Далее, что $F^*_q=F_p[i]$. После этого показал, что $(a+bi)^{(p+1)}=a^2+b^2$. $q-1=p^2-1=(p-1)(p+1)$. Порядок $a^2+b^2 = p-1$. Отсюда следует, что порядок $(a+bi)$ равен $q-1$, значит $(a+bi) -$ это образующая $F^*_q$. А второй пункт решается на основе первого. Стоит показать, что $4^2+1^2$ и $3^2+2^2$ являются образующими для $F^*_{31}$. Это делается с помощью поиска символа Лежандра. Если он равен -1, то стоит возводить элемент в степень равную степеням подгрупп с целью найти его порядок. Например, $(3^2+2^2)^{15} = -1$, то есть порядок элемента равен 30. Это значит, что такой элемент - образующий группы $F^*_{31}$.