galois.euler_totient¶
- galois.euler_totient(n)¶
Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(gcd(n, k) = 1\).
Implements the Euler Totient function \(\phi(n)\).
- Parameters
n (int) – A positive integer.
- Returns
The number of totatives that are relatively prime to \(n\).
- Return type
References
Examples
In [337]: n = 20 In [338]: phi = galois.euler_totient(n); phi Out[338]: 8 # Find the totatives that are coprime with n In [339]: totatives = [k for k in range(n) if math.gcd(k, n) == 1]; totatives Out[339]: [1, 3, 7, 9, 11, 13, 17, 19] # The number of totatives is phi In [340]: len(totatives) == phi Out[340]: True # For prime n, phi is always n-1 In [341]: galois.euler_totient(13) Out[341]: 12