galois.euler_phi

galois.euler_phi(n: int) → int

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

Parameters:¶

Returns:¶

The number of totatives that are coprime to $n$ .

Notes

This function implements the Euler totient function

ϕ (n) = n \prod_{p | n} (1 - \frac{1}{p}) = \prod_{i = 1}^{k} p_{i}^{e_{i} - 1} (p_{i} - 1)

for prime $p$ and the prime factorization $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ .

References

Examples

Compute $ϕ (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 $ϕ (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$ , $ϕ (n) = n - 1$ .

In [5]: n = 13

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