galois.totatives

galois.totatives(n)

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

Parameters

n (int) – A positive integer.

Returns

The totatives of \(n\).

Return type

list

References

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

• https://oeis.org/A000010

Examples

In [1]: n = 20

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

In [3]: phi = galois.euler_phi(n); phi
Out[3]: 8

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