Returns the integers (totatives) in \([1, n)\) that are coprime to \(n\).

Parameters:¶

n: int¶

A positive integer.

Returns:¶

A list of the totatives of \(n\), sorted in increasing order. For \(n > 1\), this is the set

\[ \{ t \in \mathbb{Z} : 1 \le t < n,\ \gcd(t, n) = 1 \}. \]

For \(n = 1\), the function returns [0], representing the unique residue class modulo \(1\) (and ensuring the length of the list equals \(\varphi(1) = 1\)).

Notes¶

For \(n > 1\), the totatives of \(n\) are precisely the integers in \([1, n)\) that are coprime to \(n\):

Modulo \(n\), these correspond to the units in the ring \(\mathbb{Z}/n\mathbb{Z}\), and under multiplication modulo \(n\) they form the multiplicative group of units \((\mathbb{Z}/n\mathbb{Z})^\times.\)

The number of totatives of \(n\) is Euler’s totient function \(\varphi(n)\), so len(totatives(n)) == euler_phi(n) for all \(n \ge 1\). For \(n = 1\), the ring \(\mathbb{Z}/1\mathbb{Z}\) has a single residue class, and this implementation represents that class by the integer 0, hence the special case [0].

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]: assert len(x) == phi