galois.euler_phi(n: int) → int

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

Parameters:
n: int

A positive integer.

Returns:

The Euler totient \(\varphi(n)\), the number of integers \(k\) with \(1 \le k \le n\) and \(\gcd(k, n) = 1\).

See also

carmichael_lambda, totatives, is_cyclic

Notes

The Euler totient function \(\varphi(n)\) is defined by

\[ \varphi(n) = \left|\{ k \in \mathbb{Z} : 1 \le k \le n,\ \gcd(k, n) = 1 \}\right|. \]

Equivalently, for \(n > 1\), it counts the totatives of \(n\) in \([1, n)\), so for all \(n \ge 1\):

\[ \varphi(n) = \lvert \texttt{totatives}(n) \rvert. \]

The function is multiplicative in the sense that if \(\gcd(m, n) = 1\), then

\[ \varphi(mn) = \varphi(m)\,\varphi(n). \]

Given the prime factorization

\[ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, \]

the totient can be computed as

\[ \varphi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right) = \prod_{i=1}^{k} p_i^{e_i - 1}(p_i - 1), \]

where the product over \(p \mid n\) runs over the distinct primes dividing \(n\). This implementation uses the latter formula.

The special case \(n = 1\) is defined by convention as \(\varphi(1) = 1\), since the ring \(\mathbb{Z}/1\mathbb{Z}\) has a single residue class, which is counted as one “unit” in this context.

Group-theoretically, \(\varphi(n)\) is the size of the multiplicative group of units

\[ \varphi(n) = \left|(\mathbb{Z}/n\mathbb{Z})^\times\right|. \]

References

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 = 20\). The number of totatives of \(n\) is \(\varphi(n)\).

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

In [4]: assert len(x) == phi

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

In [5]: n = 13

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