# galois.is_cyclic¶

galois.is_cyclic(n)

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.

Return type

bool

Notes

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 $$\{g^0, g^1, 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}/n\mathbb{Z}){^\times}$$ are the positive integers less than $$n$$ that are coprime with $$n$$. For example, $$(\mathbb{Z}/14\mathbb{Z}){^\times} = \{1, 3, 5, 9, 11, 13\}$$.

# n is of type 2*p^e, which is cyclic
In : n = 14

In : galois.is_cyclic(n)
Out: True

In : Znx = set(galois.totatives(n)); Znx
Out: {1, 3, 5, 9, 11, 13}

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

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

# The primitive roots are the elements in Znx that multiplicatively generate the group
In : for a in Znx:
...:     span = set([pow(a, i, n) for i in range(1, phi + 1)])
...:     primitive_root = galois.is_primitive_root(a, n)
...:     print("Element: {:2d}, Span: {:<20}, Primitive root: {}".format(a, str(span), primitive_root))
...:
Element:  1, Span: {1}                 , Primitive root: False
Element:  3, Span: {1, 3, 5, 9, 11, 13}, Primitive root: True
Element:  5, Span: {1, 3, 5, 9, 11, 13}, Primitive root: True
Element:  9, Span: {9, 11, 1}          , Primitive root: False
Element: 11, Span: {9, 11, 1}          , Primitive root: False
Element: 13, Span: {1, 13}             , Primitive root: False

# Find the smallest primitive root
In : galois.primitive_root(n)
Out: 3

# Find all primitive roots
In : roots = galois.primitive_roots(n); roots
Out: [3, 5]

# Euler's totient function ϕ(ϕ(n)) counts the primitive roots of n
In : len(roots) == galois.euler_phi(phi)
Out: True


A counterexample is $$n = 15 = 3 \cdot 5$$, which doesn’t fit the condition for cyclicness. $$(\mathbb{Z}/15\mathbb{Z}){^\times} = \{1, 2, 4, 7, 8, 11, 13, 14\}$$. Since the group is not cyclic, it has no primitive roots.

# n is of type p1^e1 * p2^e2, which is not cyclic
In : n = 15

In : galois.is_cyclic(n)
Out: False

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

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

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

# The primitive roots are the elements in Znx that multiplicatively generate the group
In : for a in Znx:
....:     span = set([pow(a, i, n) for i in range(1, phi + 1)])
....:     primitive_root = galois.is_primitive_root(a, n)
....:     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

# Find the smallest primitive root
In : galois.primitive_root(n)

# Find all primitive roots
In : roots = galois.primitive_roots(n); roots
Out: []

# Note the max order of any element is 4, not 8, which is Carmichael's lambda function
In : galois.carmichael_lambda(n)
Out: 4


For prime $$n$$, a primitive root modulo $$n$$ is also a primitive element of the Galois field $$\mathrm{GF}(n)$$. A primitive element is a generator of the multiplicative group $$\mathrm{GF}(p)^{\times} = \{1, 2, \dots, p-1\} = \{g^0, g^1, g^2, \dots, g^{\phi(n)-1}\}$$.

# n is of type p, which is cyclic
In : n = 7

In : galois.is_cyclic(n)
Out: True

In : Znx = set(galois.totatives(n)); Znx
Out: {1, 2, 3, 4, 5, 6}

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

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

# The primitive roots are the elements in Znx that multiplicatively generate the group
In : for a in Znx:
....:     span = set([pow(a, i, n) for i in range(1, phi + 1)])
....:     primitive_root = galois.is_primitive_root(a, n)
....:     print("Element: {:2d}, Span: {:<18}, Primitive root: {}".format(a, str(span), primitive_root))
....:
Element:  1, Span: {1}               , Primitive root: False
Element:  2, Span: {1, 2, 4}         , Primitive root: False
Element:  3, Span: {1, 2, 3, 4, 5, 6}, Primitive root: True
Element:  4, Span: {1, 2, 4}         , Primitive root: False
Element:  5, Span: {1, 2, 3, 4, 5, 6}, Primitive root: True
Element:  6, Span: {1, 6}            , Primitive root: False

# Find the smallest primitive root
In : galois.primitive_root(n)
Out: 3

# Find all primitive roots
In : roots = galois.primitive_roots(n); roots
Out: [3, 5]

# Euler's totient function ϕ(ϕ(n)) counts the primitive roots of n
In : len(roots) == galois.euler_phi(phi)
Out: True