galois.is_cyclic¶
- galois.is_cyclic(n)¶
Determines whether the multiplicative group \(\mathbb{Z}{_n^\times}\) is cyclic.
The multiplicative group \(\mathbb{Z}{_n^\times}\) is the set of positive integers \(1 \le a < n\) that are coprime with \(n\). \(\mathbb{Z}{_n^\times}\) being cyclic means that some primitive root (or generator) \(g\) can generate the group \(\mathbb{Z}{_n^\times} = \{g, g^2, \dots, g^k\}\), where \(k\) is order of the group. The order of the group is defined by Euler’s totient function, \(\phi(n) = k\). If \(\mathbb{Z}{_n^\times}\) is cyclic, the number of primitive roots is found by \(\phi(k)\) or \(\phi(\phi(n))\).
\(\mathbb{Z}{_n^\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.
- Parameters
n (int) – A positive integer.
- Returns
True
if the multiplicative group \(\mathbb{Z}{_n^\times}\) is cyclic.- Return type
References
Examples
The elements of \(\mathbb{Z}{_n^\times}\) are the positive integers less than \(n\) that are coprime with \(n\). For example when \(n = 14\), then \(\mathbb{Z}{_{14}^\times} = \{1, 3, 5, 9, 11, 13\}\).
# n is of type 2*p^k, which is cyclic In [351]: n = 14 In [352]: galois.is_cyclic(n) Out[352]: True # The congruence class coprime with n In [353]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[353]: {1, 3, 5, 9, 11, 13} # Euler's totient function counts the "totatives", positive integers coprime with n In [354]: phi = galois.euler_totient(n); phi Out[354]: 6 In [355]: len(Znx) == phi Out[355]: True # The primitive roots are the elements in Znx that multiplicatively generate the group In [356]: for a in Znx: .....: span = set([pow(a, i, n) for i in range(1, phi + 1)]) .....: primitive_root = span == Znx .....: 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 In [357]: roots = galois.primitive_roots(n); roots Out[357]: [3, 5] # Euler's totient function phi(phi(n)) counts the primitive roots of n In [358]: len(roots) == galois.euler_totient(phi) Out[358]: True
A counterexample is \(n = 15 = 3*5\), which doesn’t fit the condition for cyclicness. \(\mathbb{Z}{_{15}^\times} = \{1, 2, 4, 7, 8, 11, 13, 14\}\).
# n is of type p1^k1 * p2^k2, which is not cyclic In [359]: n = 15 In [360]: galois.is_cyclic(n) Out[360]: False # The congruence class coprime with n In [361]: Znx = set([a for a in range(1, n) if math.gcd(n, a) == 1]); Znx Out[361]: {1, 2, 4, 7, 8, 11, 13, 14} # Euler's totient function counts the "totatives", positive integers coprime with n In [362]: phi = galois.euler_totient(n); phi Out[362]: 8 In [363]: len(Znx) == phi Out[363]: True # The primitive roots are the elements in Znx that multiplicatively generate the group In [364]: for a in Znx: .....: span = set([pow(a, i, n) for i in range(1, phi + 1)]) .....: primitive_root = span == 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 In [365]: roots = galois.primitive_roots(n); roots Out[365]: [] # Note the max order of any element is 4, not 8, which is Carmichael's lambda function In [366]: galois.carmichael(n) Out[366]: 4