galois.carmichael

galois.carmichael(n)

Finds the smallest positive integer \(m\) such that \(a^m \equiv 1 (\textrm{mod}\ n)\) for every integer \(a\) in \(1 \le a < n\) that is coprime to \(n\).

Implements the Carmichael function \(\lambda(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 \le a < n\) that is coprime to \(n\).

Return type

int

References

• https://en.wikipedia.org/wiki/Carmichael_function

• https://oeis.org/A002322

Examples

In [326]: n = 20

In [327]: lambda_ = galois.carmichael(n); lambda_
Out[327]: 4

# Find the totatives that are relatively coprime with n
In [328]: totatives = [i for i in range(n) if math.gcd(i, n) == 1]; totatives
Out[328]: [1, 3, 7, 9, 11, 13, 17, 19]

In [329]: for a in totatives:
   .....:     result = pow(a, lambda_, n)
   .....:     print("{:2d}^{} = {} (mod {})".format(a, lambda_, result, n))
   .....: 
 1^4 = 1 (mod 20)
 3^4 = 1 (mod 20)
 7^4 = 1 (mod 20)
 9^4 = 1 (mod 20)
11^4 = 1 (mod 20)
13^4 = 1 (mod 20)
17^4 = 1 (mod 20)
19^4 = 1 (mod 20)

# For prime n, phi and lambda are always n-1
In [330]: galois.euler_totient(13), galois.carmichael(13)
Out[330]: (12, 12)