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

A positive integer.

Returns

True if \(g\) is a primitive root modulo \(n\).

See also

primitive_root, primitive_roots, is_cyclic, euler_phi

Notes

The integer \(g\) is a primitive root modulo \(n\) if the totatives of \(n\), the positive integers \(1 \le 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\),

\[(\mathbb{Z}/n\mathbb{Z}){^\times} = \{1, g, g^2, \dots, g^{\phi(n)-1}\}\]

where \(\phi(n)\) is order of the group.

If \((\mathbb{Z}/n\mathbb{Z}){^\times}\) is cyclic, the number of primitive roots modulo \(n\) is given by \(\phi(\phi(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