- galois.carmichael_lambda(n: int) int
Finds the smallest positive integer \(m\) such that \(a^m \equiv 1\ (\textrm{mod}\ n)\) for every integer \(a\) in \([1, n)\) that is coprime to \(n\).
- Parameters:¶
- Returns:¶
The smallest positive integer \(m\) such that \(a^m \equiv 1\ (\textrm{mod}\ n)\) for every \(a\) in \([1, n)\) that is coprime to \(n\).
Notes
This function implements the Carmichael function \(\lambda(n)\).
References
Examples
The Carmichael \(\lambda(n)\) function and Euler \(\phi(n)\) function are often equal. However, there are notable exceptions.
In [1]: [galois.euler_phi(n) for n in range(1, 20)] Out[1]: [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18] In [2]: [galois.carmichael_lambda(n) for n in range(1, 20)] Out[2]: [1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, 2, 12, 6, 4, 4, 16, 6, 18]
For prime \(n\), \(\phi(n) = \lambda(n) = n - 1\). And for most composite \(n\), \(\phi(n) = \lambda(n) < n - 1\).
In [3]: n = 9 In [4]: phi = galois.euler_phi(n); phi Out[4]: 6 In [5]: lambda_ = galois.carmichael_lambda(n); lambda_ Out[5]: 6 In [6]: totatives = galois.totatives(n); totatives Out[6]: [1, 2, 4, 5, 7, 8] In [7]: for power in range(1, phi + 1): ...: y = [pow(a, power, n) for a in totatives] ...: print("Power {}: {} (mod {})".format(power, y, n)) ...: Power 1: [1, 2, 4, 5, 7, 8] (mod 9) Power 2: [1, 4, 7, 7, 4, 1] (mod 9) Power 3: [1, 8, 1, 8, 1, 8] (mod 9) Power 4: [1, 7, 4, 4, 7, 1] (mod 9) Power 5: [1, 5, 7, 2, 4, 8] (mod 9) Power 6: [1, 1, 1, 1, 1, 1] (mod 9) In [8]: galois.is_cyclic(n) Out[8]: True
When \(\phi(n) \ne \lambda(n)\), the multiplicative group \((\mathbb{Z}/n\mathbb{Z}){^\times}\) is not cyclic. See
is_cyclic()
.In [9]: n = 8 In [10]: phi = galois.euler_phi(n); phi Out[10]: 4 In [11]: lambda_ = galois.carmichael_lambda(n); lambda_ Out[11]: 2 In [12]: totatives = galois.totatives(n); totatives Out[12]: [1, 3, 5, 7] In [13]: for power in range(1, phi + 1): ....: y = [pow(a, power, n) for a in totatives] ....: print("Power {}: {} (mod {})".format(power, y, n)) ....: Power 1: [1, 3, 5, 7] (mod 8) Power 2: [1, 1, 1, 1] (mod 8) Power 3: [1, 3, 5, 7] (mod 8) Power 4: [1, 1, 1, 1] (mod 8) In [14]: galois.is_cyclic(n) Out[14]: False