galois.euler_phi(n: int) → int

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\).

See also

carmichael_lambda, totatives, is_cyclic

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 - 1big)$$

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

References

Examples

Compute \(\phi(20)\).

In [1]: n = 20

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

Find the totatives that are coprime with \(n = 20\). The number of totatives of \(n\) is \(\phi(n)\).

In [3]: x = galois.totatives(n); x
Out[3]: [1, 3, 7, 9, 11, 13, 17, 19]

In [4]: len(x) == phi
Out[4]: True

For prime \(n\), \(\phi(n) = n - 1\).

In [5]: n = 13

In [6]: galois.euler_phi(n)
Out[6]: 12