Найти все порождающие элементы в мультипликативной группе поля Z7. Если можно, немного подробней, пожалуйста.

задан 11 Янв 10:31

10|600 символов нужно символов осталось
2

В таких случаях один порождающий находится подбором, а потом уже все остальные легко найти по простому правилу. Общая процедура такова: дано нечётное простое p. Для каждого a мы можем составить список степеней a, начиная с нулевой. То есть взять числа 1,a,a^2,... , где каждое предыдущее число домножаем на a и берём остаток от деления на p. Надо дождаться первого появления 1, и посмотреть на длину периода. Если она равна p-1, то порождающий найден.

Итак, пусть p=7. Берём a=2. Степени получаются такие: 1,2,4,1 (4 удвоили, получили 8, заменили на остаток 1). Длина периода равна 3, а надо 6. Пробуем следующее число a=3. Здесь получается 1,3,2,6,4,5,1. Мы каждое число утраивааем и берём остаток. Здесь длина периода равна 6. Значит, a=3 подходит (является первообразным корнем по модулю 7). Его степени исчерпывают все значения ненулевых остатков, то есть мы имеем порождающий мультипликативной группы.

Теперь у нас есть список 1,a,a^2,...,a^{p-2} из p-1 элемента. Остальные порождающие находятся как остатки a^k, где k взаимно просто с p-1. Их будет ровно ф(p-1), где ф -- функция Эйлера. В данном случае это ф(6)=2, а значения для k равны 1 и 5: именно они взаимно просты с 6. Это даёт два порождающих: a^1=3 и a^5=5.

ссылка

отвечен 11 Янв 11:51

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,044

задан
11 Янв 10:31

показан
64 раза

обновлен
11 Янв 11:51

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru