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$.

References¶

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

• https://oeis.org/A000010

Examples¶

Find the totatives that are coprime with $n=20$.

In [1]: n = 20

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

The number of totatives of $n$ is $\varphi (n)$.

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

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