Подсказка по показателям, простые вида 3k+2

1 симпатия

Попробуй доказать следующую лемму:

Если простое p=3k+2 делит a^2+ab+b^2, то a,b делятся на p.

Доказательство: Допустим противное. БОО a не делится на p. Тогда имеем, что a^2+ab+b^2 \equiv 0 \iff (a+2b)^2 \equiv -3a^2 \pmod{p}. Следовательно -3a^2 квадратичный вычет по модулю p. Выходит, что и -3 квадратичный вычет по модулю p=3k+2. А это противоречит квадратичному закону взаимности.

3 симпатии

Другое доказательство этой леммы. ИМХО более естественное для люда знакомых с показателями. Отсюда кстати сразу вытекает сама задача.

В кольце вычетов \mathbb{Z}^{\times}_{p} существует элемент b^{-1} такой, что b \cdot b^{-1} \equiv 1 \pmod{p}. Тогда из a^3 \equiv b^3 \pmod{p}, имеем, что (ab^{-1})^3 \equiv (bb^{-1})^3 \equiv 1 \pmod{p}. Теперь рассмотрим два случая.

Если ab^{-1} \not\equiv 1 \pmod{p}, то показатель ab^{-1} по модулю p равен 3. Следовательно 3 делит p-1 (из малой теоремы Ферма). А это противоречит условию, что p вида 3k+2.

Если ab^{-1} \equiv 1 \pmod{p}, то умножая это сравнение на b получаем, что a \equiv b \pmod{p} \implies a^2+ab+b^2\equiv 3b^2 \pmod{p} \implies 3b^2\ \vdots\ p. А это возможно только в том случае, когда b\ \vdots\ p. Аналогично доказываем, что a\ \vdots\ p.

3 симпатии

что ето значить

Это значит, что для всякого ненулевого остатка b, среди всех ненулевых остатков при делении на p, есть такой остаток, назовем его b^{-1}, который при умножении на b дает остаток 1 по модулю p. А \mathbb{Z}^{\times}_{p} – просто короткий способ обозначить множество ненулевых остатков по модулю p, т.е. \{1,2,\dots, p-1\}.

Например, если рассмотрим \mathbb{Z}^{\times}_{7}, то для числа 2 существует остаток 2^{-1} = 4 такой, что их произведение даст единичный елемент кольца, то есть 2 \cdot 4 \equiv 1 \pmod{7}.

Ответил на вопрос? :thinking: :upside_down_face:

3 симпатии
© 2021 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)