- galois.is_primitive_root(g: int, n: int) bool
Determines if \(g\) is a primitive root modulo \(n\).
See also
Notes¶
Let \((\mathbb{Z}/n\mathbb{Z})^\times\) denote the multiplicative group of units modulo \(n\):
\[ (\mathbb{Z}/n\mathbb{Z})^\times = \{ [a]_n : 1 \le a < n,\ \gcd(a, n) = 1 \}, \]with group operation given by multiplication modulo \(n\). Its order is Euler’s totient:
\[ \left|(\mathbb{Z}/n\mathbb{Z})^\times\right| = \varphi(n). \]An integer \(g\) is a primitive root modulo \(n\) if its residue class \([g]_n\) generates \((\mathbb{Z}/n\mathbb{Z})^\times\):
\[ (\mathbb{Z}/n\mathbb{Z})^\times = \{ [g^0]_n, [g^1]_n, \dots, [g^{\varphi(n)-1}]_n \}. \]Equivalently, the multiplicative order of \(g\) modulo \(n\) is \(\varphi(n)\):
\[ \operatorname{ord}_n(g) = \varphi(n). \]If \((\mathbb{Z}/n\mathbb{Z})^\times\) is cyclic, the number of primitive roots modulo \(n\) is \(\varphi(\varphi(n))\). See
is_cyclic()for the classification of which \(n\) admit primitive roots.This function uses the standard order test. Let \(\varphi(n)\) have prime factorization
\[ \varphi(n) = \prod_{i=1}^k q_i^{f_i}. \]Then \(g\) is a primitive root modulo \(n\) if and only if
\[ g^{\varphi(n)} \equiv 1 \pmod{n} \quad\text{and}\quad g^{\varphi(n)/q_i} \not\equiv 1 \pmod{n} \quad\text{for all distinct primes } q_i. \]In particular, if \(\gcd(g, n) \ne 1\), then \(g\) cannot be a primitive root.
Examples¶
Primitive roots modulo 7 and membership checks.
In [1]: list(galois.primitive_roots(7)) Out[1]: [3, 5] In [2]: assert not galois.is_primitive_root(2, 7) In [3]: assert galois.is_primitive_root(3, 7)