Euler's totient 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.

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".

It counts the number of positive integers less than or equal to n that have at least one prime factor in common with n. There are several formulae for computing φ(n).

It states where the product is over the distinct prime numbers dividing n. (For notation, see Arithmetical function.)

Proof outline: Let A, B, C be the sets of positive integers which are coprime to and less than m, n, mn, respectively, so that |A| = φ(m), etc.

An alternative proof that does not require the multiplicative property instead uses the inclusion-exclusion principle applied to the set

, excluding the sets of integers divisible by the prime divisors.

Unlike the Euler product and the divisor sum formula, this one does not require knowing the factors of n. However, it does involve the calculation of the greatest common divisor of n and every positive integer less than n, which suffices to provide the factorization anyway.

The property established by Gauss,[18] that where the sum is over all positive divisors d of n, can be proven in several ways.

Thus the set of twenty fractions is split into subsets of size φ(d) for each d dividing 20.

A similar argument applies for any n. Möbius inversion applied to the divisor sum formula gives where μ is the Möbius function, the multiplicative function defined by

The first 100 values (sequence A000010 in the OEIS) are shown in the table and graph below: In the graph at right the top line y = n − 1 is an upper bound valid for all n other than one, and attained if and only if n is a prime number.

, which is rather loose: in fact, the lower limit of the graph is proportional to ⁠n/log log n⁠.

This follows from Lagrange's theorem and the fact that φ(n) is the order of the multiplicative group of integers modulo n. The RSA cryptosystem is based on this theorem: it implies that the inverse of the function a ↦ ae mod n, where e is the (public) encryption exponent, is the function b ↦ bd mod n, where d, the (private) decryption exponent, is the multiplicative inverse of e modulo φ(n).

The difficulty of computing φ(n) without knowing the factorization of n is thus the difficulty of computing d: this is known as the RSA problem which can be solved by factoring n. The owner of the private key knows the factorization, since an RSA private key is constructed by choosing n as the product of two (randomly chosen) large primes p and q.

(where γ is the Euler–Mascheroni constant).In 1965 P. Kesava Menon proved where d(n) = σ0(n) is the number of divisors of n. The following property, which is part of the « folklore » (i.e., apparently unpublished as a specific result:[26] see the introduction of this article in which it is stated as having « long been known ») has important consequences.

This is an elementary consequence of the fact that the sum of the reciprocals of the primes congruent to 1 modulo

diverges, which itself is a corollary of the proof of Dirichlet's theorem on arithmetic progressions.

The Dirichlet series for φ(n) may be written in terms of the Riemann zeta function as:[27] where the left-hand side converges for

The "Big O" stands for a quantity that is bounded by a constant times the function of n inside the parentheses (which is small compared to n2).

This result can be used to prove[38] that the probability of two randomly chosen numbers being relatively prime is ⁠6/π2⁠.

[46][47] Ford (1999) proved that for every integer k ≥ 2 there is a totient number m of multiplicity k: that is, for which the equation φ(n) = m has exactly k solutions; this result had previously been conjectured by Wacław Sierpiński,[48] and it had been obtained as a consequence of Schinzel's hypothesis H.[44] Indeed, each multiplicity that occurs, does so infinitely often.

In the last section of the Disquisitiones[50][51] Gauss proves[52] that a regular n-gon can be constructed with straightedge and compass if φ(n) is a power of 2.

Thus, a regular n-gon has a straightedge-and-compass construction if n is a product of distinct Fermat primes and any power of 2.

The first few such n are[53] Setting up an RSA system involves choosing large prime numbers p and q, computing n = pq and k = φ(n), and finding two numbers e and d such that ed ≡ 1 (mod k).

A message, represented by an integer m, where 0 < m < n, is encrypted by computing S = me (mod n).

Euler's Theorem can be used to show that if 0 < t < n, then t = m. The security of an RSA system would be compromised if the number n could be efficiently factored or if φ(n) could be efficiently computed without factoring n. If p is prime, then φ(p) = p − 1.

In 1932 D. H. Lehmer asked if there are any composite numbers n such that φ(n) divides n − 1.

[54] In 1933 he proved that if any such n exists, it must be odd, square-free, and divisible by at least seven primes (i.e. ω(n) ≥ 7).

The German edition includes all of Gauss's 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.