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 \(\{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}/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 [1]: n = 14

In [2]: galois.is_cyclic(n)
Out[2]: True

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

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

In [5]: len(Znx) == phi
Out[5]: True

# The primitive roots are the elements in Znx that multiplicatively generate the group
In [6]: 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 [7]: galois.primitive_root(n)
Out[7]: 3

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

# Euler's totient function ϕ(ϕ(n)) counts the primitive roots of n
In [9]: len(roots) == galois.euler_phi(phi)
Out[9]: 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 [10]: n = 15

In [11]: galois.is_cyclic(n)
Out[11]: False

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

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

In [14]: len(Znx) == phi
Out[14]: True

# The primitive roots are the elements in Znx that multiplicatively generate the group
In [15]: 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 [16]: galois.primitive_root(n)

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

# Note the max order of any element is 4, not 8, which is Carmichael's lambda function
In [18]: galois.carmichael_lambda(n)
Out[18]: 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\} = \{1, g, g^2, \dots, g^{\phi(n)-1}\}\).

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

In [20]: galois.is_cyclic(n)
Out[20]: True

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

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

In [23]: len(Znx) == phi
Out[23]: True

# The primitive roots are the elements in Znx that multiplicatively generate the group
In [24]: 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 [25]: galois.primitive_root(n)
Out[25]: 3

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

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