Euler's totient function

Number of integers coprime to and less than n Not to be confused with Euler function. without a subscript base should be interpreted as a natural logarithm, also commonly written as ln ⁡ ( x ) {\displaystyle \ln(x)} or log e ⁡ ( x ) {\displaystyle \log _{e}(x)} . The first thousand values of φ(n). The points on the top line represent φ(p) when p is a prime number, which is p − 1. In number theory, Euler's totient function counts the positive integers up to a given integer n {\displaystyle n} that are relatively prime to n {\displaystyle n} . It is written using the Greek letter phi as φ ( n ) {\displaystyle \varphi (n)} or ϕ ( n ) {\displaystyle \phi (n)} , and may also be called Euler's phi function. In other words, it is the number of integers k {\displaystyle k} in the range 1 ≤ k ≤ n {\displaystyle 1\leq k\leq n} for which the greatest common divisor gcd ( n , k ) {\displaystyle \gcd(n,k)} is equal to 1. The integers k {\displaystyle k} of this form are sometimes referred to as totatives of n {\displaystyle n} . For example, the totatives of n = 9 {\displaystyle n=9} are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three n