# galois.is_primitive_root¶

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

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

Parameters
g

A positive integer.

n

A 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 \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]: galois.is_primitive_root(2, 7)
Out[1]: False

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

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


Last update: Jul 12, 2022