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

\[\phi(n) = n \prod_{p \mid 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¶

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