galois.is_primitive_root¶
- galois.is_primitive_root(g, n)¶
Determines if \(g\) is a primitive root modulo \(n\).
- Parameters
- Returns
True
if \(g\) is a primitive root modulo \(n\).- Return type
Notes
\(g\) is a primitive root 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} = \{g^0, g^1, 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]: galois.primitive_roots(7) Out[3]: [3, 5]