galois.carmichael_lambda

galois.carmichael_lambda(n: int) → int

Finds the smallest positive integer $m$ such that $a^{m} \equiv 1 (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 (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 $λ (n)$ .

References¶

https://oeis.org/A002322

Examples¶

The Carmichael $λ (n)$ function and Euler $ϕ (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$ , $ϕ (n) = λ (n) = n - 1$ . And for most composite $n$ , $ϕ (n) = λ (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 $ϕ (n) \neq λ (n)$ , the multiplicative group $(Z / n 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