первообразный корень

Ответ от Math_help_student[гуру]
Перебором. С помощью Вольфрама.
φ(71) = 71 − 1 = 70 ⇒ 70 = 2·5·7, т. е простые делители порядка группы (Z/71Z)*: q₁ = 2, q₂ = 5, q₃ = 7.
Для первообразного корня по модулю 71 значения g^[φ(71)/qᵢ] ≢ 1 (mod 71).
Нужно найти элемент группы (Z/71Z)*, удовлетворяющий следующим условиям:
{g³⁵ ≢ 1 (mod 71)
{g¹⁴ ≢ 1 (mod 71)
{g¹⁰ ≢ 1 (mod 71)
g = 7 подходит. Убедись в этом сама, пробив значения 2^35 (mod 71), 2^14 (mod 71), 2^10 (mod 71) в вольфраме (они, действительно, будут отличны от единицы) . Кстати, первообразный корень g = 7 по модулю 71 является наименьшим. Число всевозможных первообразных корней в (Z/71Z)* равно φ(φ(71)) = φ(70) = 24.
Аналогично можно найти первообразный корень по модулю 191. Только перебор уже сложнее.
Порядок группы (Z/191Z)* равен φ(191) = 191 − 1 = 190 ⇒ 190 = 2·5·19, т. е q₁ = 2, q₂ = 5, q₃ = 19.
Для первообразного корня по модулю 191 значения g^[φ(191)/qᵢ] ≢ 1 (mod 191).
{g⁹⁵ ≢ 1 (mod 191)
{g³⁸ ≢ 1 (mod 191)
{g¹⁰ ≢ 1 (mod 191)
g = 19 подходит. Он же наименьший.
Итак: g = 7, g = 19.
http://www.wolframalpha.com/