galois.is_primitive_root

galois.is_primitive_root(g: int, n: int) → bool

Determines if $g$ is a primitive root modulo $n$ .

Parameters:¶

g: int¶: A positive integer.
n: int¶: positive integer.

Returns:¶

True if $g$ is a primitive root modulo $n$ .

Notes¶

The integer $g$ is a primitive root modulo $n$ if the totatives of $n$ , the positive integers $1 \leq a < n$ that are coprime with $n$ , can be generated by powers of $g$ .

Alternatively said, $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ ,

(Z / n Z)^{\times} = {1, g, g^{2}, \dots, g^{ϕ (n) - 1}}

where $ϕ (n)$ is order of the group.

If $(Z / n Z)^{\times}$ is cyclic, the number of primitive roots modulo $n$ is given by $ϕ (ϕ (n))$ .

Examples¶

In [1]: list(galois.primitive_roots(7))
Out[1]: [3, 5]

In [2]: galois.is_primitive_root(2, 7)
Out[2]: False

In [3]: galois.is_primitive_root(3, 7)
Out[3]: True