galois.carmichael

class 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 [465]: n = 20

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

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

In [468]: 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 [469]: galois.euler_totient(13), galois.carmichael(13)
Out[469]: (12, 12)