galois.is_primitive_root¶

galois.is_primitive_root(g, n)¶

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

Parameters¶

g : int¶

A positive integer that may be a primitive root modulo $n$.

n : int¶

A positive integer.

Returns¶

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

Return type¶

bool

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^{\varphi (n)-1}\}$$

where $\varphi (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 $\varphi (\varphi (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]: galois.primitive_roots(7)
Out[3]: [3, 5]