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:
n: int

A positive integer.

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\).

See also

euler_phi, totatives, is_cyclic

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