Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.Leonhard Euler introduced the function in 1763. However, he did not at that time choose any specific symbol to denote it. In a 1784 publication, Euler studied the function further, choosing the Greek letter π to denote it: he wrote πD for 'the multitude of numbers less than D, and which have no common divisor with it'. This definition varies from the current definition for the totient function at D = 1 but is otherwise the same. The now-standard notation φ(A) comes from Gauss's 1801 treatise Disquisitiones Arithmeticae, although Gauss didn't use parentheses around the argument and wrote φA. Thus, it is often called Euler's phi function or simply the phi function.There are several formulas for computing φ(n).The first 143 values (sequence A000010 in the OEIS) are shown in the table and graph below:This states that if a and n are relatively prime thenIn 1965 P. Kesava Menon provedThe Dirichlet series for φ(n) may be written in terms of the Riemann zeta function as:In the words of Hardy & Wright, the order of φ(n) is “always ‘nearly n’.”In 1950 Somayajulu provedA totient number is a value of Euler's totient function: that is, an m for which there is at least one n for which φ(n) = m. The valency or multiplicity of a totient number m is the number of solutions to this equation. A nontotient is a natural number which is not a totient number. Every odd integer exceeding 1 is trivially a nontotient. There are also infinitely many even nontotients, and indeed every positive integer has a multiple which is an even nontotient.In the last section of the Disquisitiones Gauss proves that a regular n-gon can be constructed with straightedge and compass if φ(n) is a power of 2. If n is a power of an odd prime number the formula for the totient says its totient can be a power of two only if n is a first power and n − 1 is a power of 2. The primes that are one more than a power of 2 are called Fermat primes, and only five are known: 3, 5, 17, 257, and 65537. Fermat and Gauss knew of these. Nobody has been able to prove whether there are any more.If p is prime, then φ(p) = p − 1. In 1932 D. H. Lehmer asked if there are any composite numbers n such that φ(n) | n − 1. None are known.The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of Gauss' papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.