Как найти Наибольший порядок элемента в кольце вычетов для составного делителя

задан 14 Май 15:56

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

Понятие порядка элемента вводится не для колец, а для групп. Если дано кольцо с единицей, то с ним можно связать две группы: аддитивную (для которой в случае колец вычетов всё устроено очень просто), и мультипликативную, то есть группу обратимых элементов этого кольца. Последнюю принято обозначать в виде $%R^{\ast}$%. В данной задаче речь идёт о наибольшем значении порядка элемента группы $%\mathbb Z_n^{\ast}$%. Если $%n=p$% простое, то группа циклична по теореме о первообразном корне, и искомое значение равно $%p-1$%.

Пусть $%n$% составное. Рассмотрим каноническое разложение $%n=p_1^{k_1}\ldots p_r^{k_r}$%. Из теории известно, что группа $%\mathbb Z_n^{\ast}$% изоморфна прямому произведению мультипликативных групп сомножителей (это следствие китайской теоремы об остатках). То есть речь идёт о группе $%\mathbb Z_{p_1^{k_1}}^{\ast}\times\cdots\times\mathbb Z_{p_r^{k_r}}^{\ast}$%.

Известно (см., например, учебник Кострикина), что для степени простого числа группа $%\mathbb Z_{p^k}^{\ast}$% также является циклической, и её порядок равен $%\varphi(p^k)=p^{k-1}(p-1)$%. Для элементов прямого произведения, порядок равен НОК порядков компонент. Чтобы это значение было наибольшим, надо в каждой компоненте взять элемент наибольшего порядка. Это даст значение $%НОК(p_1^{k_1-1}(p_1-1),\ldots,p_r^{k_r-1}(p_r-1))$%.

По данной формуле искомое значение порядка легко вычисляется. Например, при $%n=100=2^25^2$% получается $%НОК(2,20)=20$%. Можно привести список начальных значений для $%n\ge2$% (включая простой и составной случай): 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 2, 12, 6, 4, 8, ... и так далее.

ссылка

отвечен 14 Май 19:29

большое спосибо

(17 Май 8:33) vaxtang
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×762

задан
14 Май 15:56

показан
32 раза

обновлен
17 Май 8:33

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

по почте:

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

по RSS:

Ответы

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

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