Totative

Short description: A coprime number less than a given integer

In number theory, a totative of a given positive integer $n$ is an integer $k$ such that $0 < k \leq n$ and $k$ is coprime to $n$ . Euler's totient function φ(n) counts the number of totatives of n. The totatives under multiplication modulo n form the multiplicative group of integers modulo n.

Distribution

The distribution of totatives has been a subject of study. Paul Erdős conjectured that, writing the totatives of n as

[math]\displaystyle{ 0 \lt a_1 \lt a_2 \cdots \lt a_{\phi(n)} \lt n , }[/math]

the mean square gap satisfies

[math]\displaystyle{ \sum_{i=1}^{\phi(n)-1} (a_{i+1}-a_i)^2 \lt C n^2 / \phi(n) }[/math]

for some constant C, and this was proven by Bob Vaughan and Hugh Montgomery.^[1]

↑ Montgomery, H.L.; Vaughan, R.C. (1986). "On the distribution of reduced residues". Ann. Math.. 2 123: 311–333. doi:10.2307/1971274.

Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. B40. ISBN 978-0-387-20860-2.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Totative. Read more