$\varphi (m) = m\left(1 — \frac12\right)\left(1 — \frac1{p_1}\right)\cdot \ldots \cdot \left(1 — \frac1{p_ k}\right)$ (если $\alpha _0 > 0$).
Рассмотрим случай $m = p_1p_2$.
$\varphi (m) = (p_1 — 1)(p_2 — 2)$.
$\varphi (p_1) = p_1 — 1$,
$\varphi (p_2) = p_2 — 1$.
$\mbox{НОК}[\varphi(p_1)\varphi(p_2)] \lt \varphi(m).$
Задача. Завершить доказательство пункта (6) в общем случае.
3. Первообразные корни . Кому нужна математика? Понятная книга о том, как устроен цифровой мир
Есть такая теорема Эйлера: если х и m взаимно просты, то g?(m) ? 1. Здесь a ? b, если a ? b делится на m. Другими словами, у а и b одинаковый остаток от деления на m. А ?(m) это функция Эйлера, равная количеству чисел, не превосходящих m и взаимно простых с ним.
Например, если m = p, где р
Условие теоремы Эйлера достаточное, но не необходимое. Вполне может случиться и так, что xa ? 1 (mod m), хотя a < ?(m). Самый простой пример такой ситуации – это, конечно, x = 1. Действительно, xa ? 1 (mod m) для любых натуральных a и m. Но есть и менее тривиальные примеры. Скажем, p = 5, а 4? = 16 ? 1(mod 5), хотя 2 < p ? 1 = 4.
Формально число g называется первообразным корнем по модулю m, если
g?(m) ? 1 (mod m), но ga ? 1 (mod m) при всех a < ?(m) и a ? 0.
Пример (отсутствие первообразных корней у m = 2k ).
Возьмем m = 2k при k ? 3. В этом случае можно показать, что для любого натурального х выполняется
При этом ?(m) = 2k?1, потому что числа, взаимно простые со степенью двойки, – это все нечетные числа, а их ровно 2k?1. Значит, для любого х нашлось число
a = 2k?2 < 2k?1 = ?(m),
для которого выполняется xa ? 1 (mod m). Получается, что у m = 2k при k ? 3 первообразных корней нет.
Теперь мы можем объяснить, почему в качестве m удобно брать простое число р. Для простого р всегда существуют первообразные корни. На самом деле мы уже говорили о них выше, в приложении 2 к главе 6, только не называли этим термином. Это те самые числа 
15). Например, при p = 3 это g = 2, при p = 5 это g = 2, а при p = 7 это g = 3. В нашем примере в тексте главы число g = 2 – это один из первообразных корней числа p = 19.
Итак, если g – первообразный корень p, то все остатки в (П.15) разные и каждому остатку соответствует единственная степень х (дискретный логарифм, он же индекс), при которой такой остаток получается. Ничего подобного мы не можем сделать, если будем брать остаток от деления на число m, для которого первообразного корня нет. Именно поэтому работают с простыми числами.
Заметим, что первообразные корни есть еще для m = 4, m = pk и m = 2pk. Но все равно с простыми числами работать проще.
Назад к Главе 6
Нахождение первообразного корня простого числа
Общей формулы для нахождения первообразного корня не существует.
{s/p_i}\mod p$ для всех $i=1\ldots k$, и если вы найдете $1$ среди остатков, то это НЕ первообразный корень, в противном случае это так. 9{40}\эквив-263\мод 761$ ура!
Таким образом, наименьший первообразный корень числа 761 равен 6.
Как вы выбираете
Как правило, вы выбираете либо наугад, либо начиная с 2 и увеличивая (например, при поиске наименьшего первообразного корня), или в любой другой последовательности в зависимости от ваших потребностей.
Обратите внимание, что при случайном выборе чем больше простых множителей в $\phi(p)$, тем меньше вероятность случайного нахождения одного из них. Кроме того, будет больше возможностей для тестирования.
Например, если вы выберете случайное число, чтобы проверить, является ли оно первообразным корнем из $761$, то вероятность его нахождения примерно равна $\frac{1}{2}\times\frac{4}{5}\ times\frac{18}{19}$ или 38%, и нужно проверить 3 степени. Но если вы ищете первообразные корни, скажем, из $2311$, то вероятность случайного нахождения одного корня составляет около 20%, и нужно проверить 5 степеней.