Как вычислить Первообразный корень

Первообразный корень — число n, показатель степени которого составляют все остатки до n-1.

Пример:

число 3 является первообразным корнем по модулю 7, так как расчеты от 3^1 mod 7 до З^6 mod 7 дают все числа от 1 до 6

З^6 mod 7 = 1

З^2 mod 7 = 2

3^1 mod 7 = 3

З^4 mod 7 = 4

З^5 mod 7 = 5

З^3 mod 7 = 6