Finds the smallest positive integer \(m\) such that \(a^m \equiv 1 \pmod{n}\) for every integer \(a\) in \([1, n)\) that is coprime to \(n\).

Parameters:¶

n: int¶

A positive integer.

Returns:¶

The Carmichael function \(\lambda(n)\), i.e., the smallest positive integer \(m\) such that \(a^m \equiv 1 \pmod{n}\) for every integer \(a\) with \(1 \le a < n\) and \(\gcd(a, n) = 1\).

Notes¶

The Carmichael function \(\lambda(n)\) is defined as the least positive integer \(m\) such that

for all integers \(a\) with \(\gcd(a, n) = 1\). In group-theoretic terms, if \((\mathbb{Z}/n\mathbb{Z})^\times\) denotes the multiplicative group of units modulo \(n\), then \(\lambda(n)\) is the exponent of this group:

This function is closely related to Euler’s totient function \(\varphi(n)\):

• One always has \(\lambda(n) \mid \varphi(n)\).

• If \((\mathbb{Z}/n\mathbb{Z})^\times\) is cyclic, then \(\lambda(n) = \varphi(n)\), and there exists a generator (a primitive root modulo \(n\)).

• If \((\mathbb{Z}/n\mathbb{Z})^\times\) is not cyclic, then \(\lambda(n) < \varphi(n)\), and no single element generates all units.

The Carmichael function can be computed from the prime factorization

as follows. First, compute \(\lambda(p_i^{e_i})\) for each prime power; then

For each prime power \(p^e\):

• If \(p\) is odd or \((p = 2\) and \(e \le 2)\), then

  \[ \lambda(p^e) = \varphi(p^e) = p^{e - 1}(p - 1). \]

• If \(p = 2\) and \(e \ge 3\), then

  \[ \lambda(2^e) = 2^{e - 2} = \frac{\varphi(2^e)}{2}. \]

This implementation uses the above formulas: it computes \(\lambda(p^e)\) from \(\varphi(p^e)\), with the factor-of-two adjustment for \(2^e\) when \(e > 2\), and then returns the least common multiple of the resulting values.

The special case \(n = 1\) is defined by convention as \(\lambda(1) = 1\), which is consistent with the view that \(\mathbb{Z}/1\mathbb{Z}\) has a trivial (one-element) multiplicative structure.

References¶

• https://oeis.org/A002322

Examples¶

The Carmichael \(\lambda(n)\) function and Euler \(\varphi(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\), \(\varphi(n) = \lambda(n) = n - 1\). And for many composite \(n\), \(\varphi(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]: assert galois.is_cyclic(n)

When \(\varphi(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]: assert not galois.is_cyclic(n)