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$$.

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