galois.is_cyclic(n: int) → bool

Determines whether the multiplicative group \((\mathbb{Z}/n\mathbb{Z})^\times\) is cyclic.

Parameters:
n: int

A positive integer.

Returns:

True if the multiplicative group \((\mathbb{Z}/n\mathbb{Z})^\times\) is cyclic.

See also

euler_phi, carmichael_lambda, totatives

Notes

For a positive integer \(n\), the multiplicative group of units modulo \(n\) is

\[ (\mathbb{Z}/n\mathbb{Z})^\times = \{ [a]_n : 1 \le a < n,\ \gcd(a, n) = 1 \}, \]

with multiplication induced by integer multiplication modulo \(n\). Its order is Euler’s totient:

\[ \left|(\mathbb{Z}/n\mathbb{Z})^\times\right| = \varphi(n). \]

The group \((\mathbb{Z}/n\mathbb{Z})^\times\) is cyclic if there exists an element \(g \in (\mathbb{Z}/n\mathbb{Z})^\times\) (a primitive root modulo \(n\)) such that

\[ (\mathbb{Z}/n\mathbb{Z})^\times = \{ g^0, g^1, \dots, g^{\varphi(n)-1} \}. \]

In that case, the number of primitive roots modulo \(n\) is \(\varphi(\varphi(n))\), and every element of \((\mathbb{Z}/n\mathbb{Z})^\times\) is some power of \(g\).

A classical theorem completely characterizes when \((\mathbb{Z}/n\mathbb{Z})^\times\) is cyclic:

  • The group \((\mathbb{Z}/n\mathbb{Z})^\times\) is cyclic if and only if

    \[ n \in \{1, 2, 4\} \quad \text{or} \quad n = p^k \text{ or } n = 2p^k \]

    for some odd prime \(p\) and integer \(k \ge 1\).

In particular:

  • For \(n = p\) prime, \((\mathbb{Z}/p\mathbb{Z})^\times\) is always cyclic of order \(p - 1\) and admits primitive roots modulo \(p\).

  • For \(n = 2, 4, p^k\), or \(2p^k\) (with \(p\) odd), there are primitive roots modulo \(n\).

  • For any other composite \(n\), \((\mathbb{Z}/n\mathbb{Z})^\times\) is not cyclic, so no primitive roots modulo \(n\) exist.

  • The trivial group \((\mathbb{Z}/1\mathbb{Z})^\times\) is cyclic by convention, and this function returns True for \(n = 1\).

Examples

The elements of \((\mathbb{Z}/14\mathbb{Z})^\times = \{1, 3, 5, 9, 11, 13\}\) are the totatives of 14.

In [1]: n = 14

In [2]: Znx = galois.totatives(n); Znx
Out[2]: [1, 3, 5, 9, 11, 13]

The Euler totient \(\varphi(n)\) function counts the totatives of \(n\), which is equivalent to the order of \((\mathbb{Z}/n\mathbb{Z})^\times\).

In [3]: phi = galois.euler_phi(n); phi
Out[3]: 6

In [4]: assert len(Znx) == phi

Since 14 is of the form \(2p^k\), the multiplicative group \((\mathbb{Z}/14\mathbb{Z})^\times\) is cyclic, meaning there exists at least one element that generates the group by its powers.

In [5]: assert galois.is_cyclic(n)

Find the smallest primitive root modulo 14. Observe that the powers of g uniquely represent each element in \((\mathbb{Z}/14\mathbb{Z})^\times\).

In [6]: g = galois.primitive_root(n); g
Out[6]: 3

In [7]: [pow(g, i, n) for i in range(0, phi)]
Out[7]: [1, 3, 9, 13, 11, 5]

Find the largest primitive root modulo 14. Observe that the powers of g also uniquely represent each element in \((\mathbb{Z}/14\mathbb{Z})^\times\), although in a different order.

In [8]: g = galois.primitive_root(n, method="max"); g
Out[8]: 5

In [9]: [pow(g, i, n) for i in range(0, phi)]
Out[9]: [1, 5, 11, 13, 9, 3]

A non-cyclic group is \((\mathbb{Z}/15\mathbb{Z})^\times = \{1, 2, 4, 7, 8, 11, 13, 14\}\).

In [10]: n = 15

In [11]: Znx = galois.totatives(n); Znx
Out[11]: [1, 2, 4, 7, 8, 11, 13, 14]

In [12]: phi = galois.euler_phi(n); phi
Out[12]: 8

Since 15 is not of the form \(2\), \(4\), \(p^k\), or \(2p^k\), the multiplicative group \((\mathbb{Z}/15\mathbb{Z})^\times\) is not cyclic, meaning no elements exist whose powers generate the group.

In [13]: assert not galois.is_cyclic(n)

Below, every element is tested to see if it spans the group.

In [14]: for a in Znx:
   ....:     span = set([pow(a, i, n) for i in range(0, phi)])
   ....:     primitive_root = span == set(Znx)
   ....:     print("Element: {:2d}, Span: {:<13}, Primitive root: {}".format(a, str(span), primitive_root))
   ....: 
Element:  1, Span: {1}          , Primitive root: False
Element:  2, Span: {8, 1, 2, 4} , Primitive root: False
Element:  4, Span: {1, 4}       , Primitive root: False
Element:  7, Span: {1, 4, 13, 7}, Primitive root: False
Element:  8, Span: {8, 1, 2, 4} , Primitive root: False
Element: 11, Span: {1, 11}      , Primitive root: False
Element: 13, Span: {1, 4, 13, 7}, Primitive root: False
Element: 14, Span: {1, 14}      , Primitive root: False

The Carmichael \(\lambda(n)\) function finds the maximum multiplicative order of any element, which is 4 and not 8.

In [15]: galois.carmichael_lambda(n)
Out[15]: 4

Observe that no primitive roots modulo 15 exist and a RuntimeError is raised.

In [16]: galois.primitive_root(n)
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
File /opt/hostedtoolcache/Python/3.13.11/x64/lib/python3.13/site-packages/galois/_primitive_root.py:307, in primitive_root(n, start, stop, method)
    306 if method == "min":
--> 307     root = next(primitive_roots(n, start, stop=stop))
    308 elif method == "max":

StopIteration: 

The above exception was the direct cause of the following exception:

RuntimeError                              Traceback (most recent call last)
Cell In[16], line 1
----> 1 galois.primitive_root(n)

File /opt/hostedtoolcache/Python/3.13.11/x64/lib/python3.13/site-packages/galois/_primitive_root.py:315, in primitive_root(n, start, stop, method)
    312     return root
    313 except StopIteration as e:
    314     # No primitive root found in the requested range (either non-cyclic group or range too small).
--> 315     raise RuntimeError(f"No primitive roots modulo {n} exist in the range [{start}, {stop}).") from e

RuntimeError: No primitive roots modulo 15 exist in the range [1, 15).

For prime \(n\), a primitive root modulo \(n\) is also a primitive element of the Galois field \(\mathrm{GF}(n)\).

In [17]: n = 31

In [18]: assert galois.is_cyclic(n)

A primitive element is a generator of the multiplicative group \(\mathrm{GF}(p)^\times = \{1, 2, \dots, p - 1\} = \{1, g, g^2, \dots, g^{\varphi(n)-1}\}\).

In [19]: GF = galois.GF(n)

In [20]: galois.primitive_root(n)
Out[20]: 3

In [21]: GF.primitive_element
Out[21]: GF(3, order=31)

The number of primitive roots/elements is \(\varphi(\varphi(n))\).

In [22]: list(galois.primitive_roots(n))
Out[22]: [3, 11, 12, 13, 17, 21, 22, 24]

In [23]: GF.primitive_elements
Out[23]: GF([ 3, 11, 12, 13, 17, 21, 22, 24], order=31)

In [24]: galois.euler_phi(galois.euler_phi(n))
Out[24]: 8