Totative

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

0<a_{1}<a_{2}\cdots <a_{\phi (n)}<n,

the mean square gap satisfies

\sum _{i=1}^{\phi (n)-1}(a_{i+1}-a_{i})^{2}<Cn^{2}/\phi (n)

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

gollark: Oh, that too.

gollark: Well, yes, I could make it just a proxy table, but then pairs would break.

gollark: So even less immutable. Oh well!

gollark: Unfortunately, I can't block *that* due to metatable limitations.

gollark: See, this is done entirely with plain metatables!

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.