galois.euler_phi¶

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 - 1\big)\]

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

References

• Section 2.4.1 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf

• https://oeis.org/A000010

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

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 of \(n\) is \(\phi(n)\).

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

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

In [5]: n = 13

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