galois.euler_totient

class galois.euler_totient(n)

Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(\mathrm{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

int

References

• https://en.wikipedia.org/wiki/Euler%27s_totient_function

• https://oeis.org/A000010

Examples

In [476]: n = 20

In [477]: phi = galois.euler_totient(n); phi
Out[477]: 8

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

# The number of totatives is phi
In [479]: len(totatives) == phi
Out[479]: True

# For prime n, phi is always n-1
In [480]: galois.euler_totient(13)
Out[480]: 12