galois.totatives

class galois.totatives(n)

Returns the positive integers (totatives) in \(1 \le k < n\) that are coprime with \(n\), i.e. \(\mathrm{gcd}(n, k) = 1\).

The totatives of \(n\) form the multiplicative group \(\mathbb{Z}{_n^\times}\).

Parameters

n (int) – A positive integer.

Returns

The totatives of \(n\).

Return type

list

References

• https://en.wikipedia.org/wiki/Totative

• https://oeis.org/A000010

Examples

In [689]: n = 20

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

In [691]: phi = galois.euler_totient(n); phi
Out[691]: 8

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