Функция Эйлера n го порядка по составному модулю M = p# равна
φ_n(M) = П φ_n(p) = П(р - n) р/M
Прежде чем определять число групп вычетов n - го порядка (n - число вычетов в группе) в ПСВ
по модулю M = p# надо определить, существует ли данная группа в ПСВ.
Для этого у нас есть функция " проходимость" K(p) = φ_n(p) + m(p) = p + m(p) - n.
По каким р надо проверять проходимость группы ? Приняв m(p) = 0 при р > n K(p) > o.
В этом случае по модулю р проходимость проверять не надо.
Если p < n, то проверка обязательна, но по модулю р = 2 проверять не надо, т.к. вычеты группы
четные числа, число их равно n - 1 и все они сравнимы с первым вычетом равным 0.
т.е. m(2) = n - 1 и K(2) = 2 + n - 1 - n = 1.
Определение числа групп n - го порядка в ПСВ(М).
Для этого необходимо определить коэффициент A_n к функции φ_n(M) . Он равен
A_n = П k(p)/φ_n(p)
Здесь проходимость К(р) определяется по всем р, по которым возможны сравнения вычетов группы
между собой , но только по тем, которые есть в модуле М. Коэффициент A_n показывает насколько
отличается фактическое число групп от функции Эйлера.
φ_n(p) - определяется по тем же р, что и К(р).
Число групп n - го порядка определяется по формуле
N(Q[n]) = A_n φ_n(M)
Примеры. Берем группу 4 - го порядка с разностями между вычетами (4, 2, 4).
Приведенная группа D[4] = (0, 4, 6, 10)
Проходимость по модулю р = 3. Имеем два сравнимых вычета 0 - 6 и 4 - 10.
m(3) = 2, K(3) = 3 + 2 - 4 = 1.
Этого достаточно, чтобы утверждать, что данная группа существует в любой ПСВ(М),
т.к. р = 5 > n и K(5) > 0.
Но для определения числа групп в ПСВ надо определить коэффициент А_n
Проходимость по модулю р = 5. Имеем один сравнимый вычет 0 - 10.
m(5) = 1, K(5) = 5 + 1 - 4 = 2.
φ_4(3) = 1, φ_4(5) = 1, A_4 = K(3)K(5) = 2.
N(D{4]) = 2 φ_4(M)
В ПСВ(30), φ_4(30) = 1, N(D{4]) = 2, это (7, 11, 13, 17) и (13, 17, 19, 23).
В ПСВ(210), φ_4(210) = 3, N(D{4]) = 6, это (13, 17, 19, 23),(37, 41, 43, 47)
(97, 101, 103, 107),(103, 107, 109, 113),(163, 167, 169, 173),(187, 191, 193, 197).
