force
Удален
|
    
Подскажите, можно ли как-то вычислить кол-во элементов максимального порядка (те.е хотя найти как часто они появляются)? Например, для 15 максимальный порядок 4, но ведь есть и элементы с более низкими порядками. напримерЖ
число-порядок
2 - 4
4 - 2
7 - 4
8 - 4
11 - 2
Т.е. как часто появляются элементы именно с порядком 4?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 16 нояб. 2005 23:48 | IP
|
|
force
Удален
|
Чисел мксимального порядка будет f(m)/2, где f(m) - функция Эйлера. Т.е. ровно половина элементов в приведенной системе вычетов по модулю m. Вот только как это доказать???
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 18 нояб. 2005 17:00 | IP
|
|
Guest
Новичок
|
Цитата: force написал 18 нояб. 2005 17:00
Чисел мксимального порядка будет f(m)/2, где f(m) - функция Эйлера.
это справедливо только для следующий чисел: 10 15 16 17 20 21 28 30 32 34 36 40 42 48 51 57 ...
а все остальные являются контр-примерами.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 19 нояб. 2005 4:17 | IP
|
|
force
Удален
|
2Guest
А как для остальных модулей вычислить, сколько чисел максимального порядка? Или в какой книжке про это можно почитать?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 19 нояб. 2005 21:58 | IP
|
|
force
Удален
|
Я так понимаю, нужно просто найти кол-во решений сравнения
x^m = 1 (mod n), где m - максимальный порядок по модулю n.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 19 нояб. 2005 23:40 | IP
|
|
Guest
Новичок
|
Нет. Нужно считать только такие решения, для которых x^k != 1 (mod n) для k < m.
Простой формулы здесь не получится, так как функция "количество элементов максимального порядка" даже не является мультипликативной. Но алгоритм придумать можно. А вам зачем?
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 20 нояб. 2005 0:55 | IP
|
|
force
Удален
|
Мне это особо никуда не нужно. Ради собствнного интереса так сказать (заинтересовало во время решения другой задачки). Спасибо за советы. Буду думать.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 20 нояб. 2005 13:35 | IP
|
|
Jilian
Удален
|
Цитата: force написал 20 нояб. 2005 13:35
Мне это особо никуда не нужно. Ради собствнного интереса так сказать (заинтересовало во время решения другой задачки). Спасибо за советы. Буду думать.
Во народ пошел!!! Ради собственного интереса такие задачи решают...
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 20 нояб. 2005 22:34 | IP
|
|
Форум
Максимальный порядок по модулю
