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

$$\varphi (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

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

• https://oeis.org/A000010

Examples

Compute $\varphi (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 $\varphi (n)$.

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

For prime $n$, $\varphi (n)=n-1$.

In [5]: n = 13

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