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.

The multiplicative group $$(\mathbb{Z}/n\mathbb{Z}){^\times}$$ is the set of positive integers $$1 \le a < n$$ that are coprime with $$n$$. $$(\mathbb{Z}/n\mathbb{Z}){^\times}$$ being cyclic means that some primitive root of $$n$$, or generator, $$g$$ can generate the group $$\{1, g, g^2, \dots, g^{\phi(n)-1}\}$$, where $$\phi(n)$$ is Euler’s totient function and calculates the order of the group. If $$(\mathbb{Z}/n\mathbb{Z}){^\times}$$ is cyclic, the number of primitive roots is found by $$\phi(\phi(n))$$.

$$(\mathbb{Z}/n\mathbb{Z}){^\times}$$ is cyclic if and only if $$n$$ is 2, 4, $$p^k$$, or $$2p^k$$, where $$p$$ is an odd prime and $$k$$ is a positive integer.

Examples

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

In : n = 14

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


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

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

In : len(Znx) == phi
Out: True


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 : galois.is_cyclic(n)
Out: True


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 : g = galois.primitive_root(n); g
Out: 3

In : [pow(g, i, n) for i in range(0, phi)]
Out: [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 : g = galois.primitive_root(n, method="max"); g
Out: 5

In : [pow(g, i, n) for i in range(0, phi)]
Out: [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 : n = 15

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

In : phi = galois.euler_phi(n); phi
Out: 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 : galois.is_cyclic(n)
Out: False


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

In : 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 : galois.carmichael_lambda(n)
Out: 4


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

In : galois.primitive_root(n)
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
File ~/checkouts/readthedocs.org/user_builds/galois/envs/stable/lib/python3.8/site-packages/galois/_modular.py:559, in primitive_root(n, start, stop, method)
558 if method == "min":
--> 559     root = next(primitive_roots(n, start, stop=stop))
560 elif method == "max":

StopIteration:

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

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

File ~/checkouts/readthedocs.org/user_builds/galois/envs/stable/lib/python3.8/site-packages/galois/_modular.py:566, in primitive_root(n, start, stop, method)
564     return root
565 except StopIteration as e:
--> 566     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 : n = 31

In : galois.is_cyclic(n)
Out: True


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

In : GF = galois.GF(n)

In : galois.primitive_root(n)
Out: 3

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


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

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

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

In : galois.euler_phi(galois.euler_phi(n))
Out: 8