Totative

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 ≤ 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 ⋯ < a ϕ ( n ) < n , {\displaystyle 0<a_{1}<a_{2}\cdots <a_{\phi (n)}<n,}

the mean square gap satisfies

∑ i = 1 ϕ ( n ) − 1 ( a i + 1 − a i ) 2 < C n 2 / ϕ ( n ) {\displaystyle \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]

See also

  • Reduced residue system

References

  1. ^ 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.

Further reading

  • Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, pp. 242–250, ISBN 1-4020-2546-7, Zbl 1079.11001

External links

  • Weisstein, Eric W. "Totative". MathWorld.
  • totative at PlanetMath.


  • v
  • t
  • e