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

int

References

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

• https://oeis.org/A000010

Examples

In [1]: n = 20

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

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

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

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