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

Ответ от Alexсашка[новичек]
Ты понял правильно, но дело в том, что у числа по модулю p есть много первообразных корней. вот например для p = 17 это числа 3,10,5,11,14,7,12,6. как это посчитать: вот ты нашел первый первообразный корень, для данного случая g=3. Далее возводишь 3 в степени от 1 до F(p), где F функция эйлера. берешь, ясен пень по модулю p. вот получил строчку из чисел - степеней тройки по mod p. затем зачеркиваешь все числа в этом ряду под четными номерами, а также числа, не взаимно простые с F(p). все числа не зачеркнутые будут твоими искомыми первообразными корнями. я долго ржал над: "а затем найти первое число ОТ ПОСЛЕ единицы". вот ты грамотей!:)
Источник: Семинарист