galois.euler_phi

galois.euler_phi(n)

Counts the positive integers (totatives) in \([1, n]\) that are coprime to \(n\).

Parameters

n (int) – A positive integer.

Returns

The number of totatives that are coprime to \(n\).

Return type

int

Notes

This function implements the Euler totient function

\[\phi(n) = n \prod_{p\ |\ n} \bigg(1 - \frac{1}{p}\bigg) = \prod_{i=1}^{k} p_i^{e_i-1} \big(p_i - 1\big)\]

for prime \(p\) and the prime factorization \(n = p_1^{e_1} \dots p_k^{e_k}\).

References

Examples

In [1]: n = 20

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

# Find the totatives that are coprime with n
In [3]: totatives = [k for k in range(n) if math.gcd(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, ϕ(n) = n - 1
In [5]: galois.euler_phi(13)
Out[5]: 12