In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
, a totative of a given positive integer is an integer such that and is
coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to .
Euler's totient function
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
φ(''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
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
conjectured that, writing the totatives of ''n'' as
:
the mean square gap satisfies
:
for some constant ''C'', and this was proven by
Bob Vaughan
Robert Charles "Bob" Vaughan FRS (born 24 March 1945) is a British mathematician, working in the field of analytic number theory.
Life
Since 1999 he has been Professor at Pennsylvania State University, and since 1990 Fellow of the Royal Societ ...
and
Hugh Montgomery.
See also
*
Reduced residue system
In mathematics, a subset ''R'' of the integers is called a reduced residue system modulo ''n'' if:
#gcd(''r'', ''n'') = 1 for each ''r'' in ''R'',
#''R'' contains φ(''n'') elements,
#no two elements of ''R'' are congruent modulo ''n''.
Here φ d ...
References
*
Further reading
*
External links
*
*
Modular arithmetic
{{Numtheory-stub