galois.totatives¶
- galois.totatives(n: int) list[int] ¶
Returns the positive integers (totatives) in \([1, n)\) that are coprime to \(n\).
The totatives of \(n\) form the multiplicative group \((\mathbb{Z}/n\mathbb{Z}){^\times}\).
See also
References
Section 2.4.3 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf
Examples
Find the totatives that are coprime with \(n = 20\).
In [1]: n = 20 In [2]: totatives = galois.totatives(n); totatives Out[2]: [1, 3, 7, 9, 11, 13, 17, 19]
Compute \(\phi(20)\).
In [3]: phi = galois.euler_phi(n); phi Out[3]: 8
The number of totatives of \(n\) is \(\phi(n)\).
In [4]: len(totatives) == phi Out[4]: True
Last update:
Apr 21, 2022