{"history":[],"article":{"id":"9edd4184-73a4-47fe-af7e-9e515c6c5bbe","title":"Euler's totient function","slug":"euler-s-totient-function","content":":::summary\n:::\n\n# \n[[Image:EulerPhi.svg|thumb|The first thousand values of\nφ(n)\n. The points on the top line represent\nφ(p)\nwhen p is a prime number, which is\np − 1.\n]]\nIn [number theory](https://bliptext.com/articles/number-theory), **Euler's totient function** counts the positive integers up to a given integer n that are [relatively prime](https://bliptext.com/articles/relatively-prime) to n. It is written using the Greek letter [phi](https://bliptext.com/articles/phi) as \\var[phi](https://bliptext.com/articles/phi)(n) or \\[phi](https://bliptext.com/articles/phi)(n), and may also be called **Euler's [phi](https://bliptext.com/articles/phi) function**.\nIn other words, it is the number of integers k in the range\n1 ≤ k ≤ n\nfor which the [greatest common divisor](https://bliptext.com/articles/greatest-common-divisor)\ngcd(n, k)\nis equal to 1.\nThe integers k of this form are sometimes referred to as [totatives](https://bliptext.com/articles/totative) of n.\nFor example, the totatives of\nn = 9\nare the six numbers 1, 2, 4, 5, 7 and 8.\nThey are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since\ngcd(9, 3) = gcd(9, 6) = 3\nand\ngcd(9, 9) = 9\n. Therefore,\nφ(9) = 6\n. As another example,\nφ(1) = 1\nsince for\nn = 1\nthe only integer in the range from 1 to n is 1 itself, and\ngcd(1, 1) = 1\n.\nEuler's totient function is a [multiplicative function](https://bliptext.com/articles/multiplicative-function), meaning that if two numbers m and n are relatively prime, then\nφ(mn) = φ(m)φ(n)\n. This function gives the [order](https://bliptext.com/articles/order-[group](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n)-theory) of the [multiplicative group of integers modulo n](https://bliptext.com/articles/multiplicative-[group](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n)-of-integers-modulo-n) (the [group](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n) of [units](https://bliptext.com/articles/unit-[ring](https://bliptext.com/articles/ring-algebra)-theory) of the [ring](https://bliptext.com/articles/ring-algebra) \\Z/n\\Z).\nIt is also used for defining the [RSA encryption system](https://bliptext.com/articles/rsa-cryptosystem).\n\n# History, terminology, and notation\n[Leonhard Euler](https://bliptext.com/articles/leonhard-euler) introduced the function in 1763.\nHowever, he did not at that time choose any specific symbol to denote it.\nIn a 1784 publication, Euler studied the function further, choosing the Greek letter π to denote it: he wrote\nπD\nfor \"the multitude of numbers less than D, and which have no common divisor with it\".\nThis definition varies from the current definition for the totient function at\nD = 1\nbut is otherwise the same.\nThe now-standard notation\nφ(A)\ncomes from [Gauss](https://bliptext.com/articles/gauss)'s 1801 treatise [Disquisitiones Arithmeticae](https://bliptext.com/articles/disquisitiones-arithmeticae), although [Gauss](https://bliptext.com/articles/gauss) did not use parentheses around the argument and wrote\nφA\n. Thus, it is often called **Euler's **phi function**** or simply the **phi function**.\nIn 1879, [J. J. Sylvester](https://bliptext.com/articles/james-joseph-sylvester) coined the term **totient** for this function, so it is also referred to as Euler's **totient** function, the Euler **totient**, or Euler's **totient**.\n[Jordan's totient](https://bliptext.com/articles/jordan-s-totient-function) is a generalization of Euler's.\nThe **cototient** of n is defined as\nn − φ(n)\n. It counts the number of positive integers less than or equal to n that have at least one [prime factor](https://bliptext.com/articles/prime-number) in common with n.\n\n# Computing Euler's totient function\nThere are several formulae for computing\nφ(n)\n.\n\n## Euler's product formula\nIt states\nwhere the product is over the distinct [prime numbers](https://bliptext.com/articles/prime-number) dividing n. (For notation, see [Arithmetical function](https://bliptext.com/articles/arithmetical-function).)\nAn equivalent formulation is where is the [prime factorization](https://bliptext.com/articles/prime-factorization) of n (that is, are distinct prime numbers).\nThe proof of these formulae depends on two important facts.\n\n### Phi is a multiplicative function\nThis means that if\ngcd(m, n) = 1\n, then\nφ(m) φ(n) = φ(mn)\n. Proof outline: Let A, B, C be the sets of positive integers which are [coprime](https://bliptext.com/articles/coprime) to and less than m, n, mn, respectively, so that\nA\n, etc. Then there is a [bijection](https://bliptext.com/articles/bijection) between\nA × B\nand C by the [Chinese remainder theorem](https://bliptext.com/articles/chinese-remainder-theorem).\n\n### Value of phi for a prime power argument\nIf p is prime and\nk ≥ 1\n, then\nProof: Since p is a prime number, the only possible values of\ngcd(pk, m)\nare\n1, p, p2, ..., pk\n, and the only way to have\ngcd(pk, m) > 1\nis if m is a multiple of p, that is,\nm ∈\n, and there are\npk − 1\nsuch multiples not greater than\npk\n. Therefore, the other\npk − pk − 1\nnumbers are all relatively prime to\npk\n.\n\n### Proof of Euler's product formula\nThe [fundamental theorem of arithmetic](https://bliptext.com/articles/fundamental-theorem-of-arithmetic) states that if\nn > 1\nthere is a unique expression where\np1 < p2 < ...\n< pr\nare [prime numbers](https://bliptext.com/articles/prime-number) and each\nki ≥ 1\n. (The case\nn = 1\ncorresponds to the empty product.) Repeatedly using the multiplicative property of φ and the formula for\nφ(pk)\ngives\nThis gives both versions of Euler's product formula.\nAn alternative proof that does not require the multiplicative property instead uses the [inclusion-exclusion principle](https://bliptext.com/articles/inclusion-exclusion-principle) applied to the set, excluding the sets of integers divisible by the prime divisors.\n\n### Example\nIn words: the distinct prime factors of 20 are 2 and 5; half of the twenty integers from 1 to 20 are divisible by 2, leaving ten; a fifth of those are divisible by 5, leaving eight numbers coprime to 20; these are: 1, 3, 7, 9, 11, 13, 17, 19.\nThe alternative formula uses only integers:\n\n## Fourier transform\nThe totient is the [discrete Fourier transform](https://bliptext.com/articles/discrete-fourier-transform) of the [gcd](https://bliptext.com/articles/greatest-common-divisor), evaluated at 1.\nLet\nwhere\nfor\nk ∈ {1, ..., n}\n. Then\nThe real part of this formula is\nFor example, using and :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.\n\n## Divisor sum\nThe property established by Gauss, that\nwhere the sum is over all positive divisors d of n, can be proven in several ways.\n(See [Arithmetical function](https://bliptext.com/articles/arithmetical-function) for notational conventions.)\nOne proof is to note that\nφ(d)\nis also equal to the number of possible generators of the [cyclic group](https://bliptext.com/articles/cyclic-group)\nCd\n; specifically, if\nwith\ngd = 1\n, then\ngk\nis a generator for every k coprime to d. Since every element of\nCn\ngenerates a cyclic [subgroup](https://bliptext.com/articles/subgroup), and each [subgroup](https://bliptext.com/articles/subgroup)\nCd ⊆ Cn\nis generated by precisely\nφ(d)\nelements of\nCn\n, the formula follows.\nEquivalently, the formula can be derived by the same argument applied to the [multiplicative group of the nth roots of unity](https://bliptext.com/articles/root-of-unity) and the [primitive dth roots of unity](https://bliptext.com/articles/primitive-root-of-unity).\nThe formula can also be derived from elementary arithmetic.\nFor example, let\nand consider the positive fractions up to 1 with denominator 20:\nPut them into lowest terms:\nThese twenty fractions are all the positive k⁄d ≤ 1 whose denominators are the divisors\n. The fractions with 20 as denominator are those with numerators relatively prime to 20, namely 1⁄20, 3⁄20, 7⁄20, 9⁄20, 11⁄20, 13⁄20, 17⁄20, 19⁄20; by definition this is\nφ(20)\nfractions.\nSimilarly, there are\nφ(10)\nfractions with denominator 10, and\nφ(5)\nfractions with denominator 5, etc. Thus the set of twenty fractions is split into subsets of size\nφ(d)\nfor each\nd\ndividing 20.\nA similar argument applies for any n.\n[Möbius inversion](https://bliptext.com/articles/m-bius-inversion) applied to the divisor sum formula gives\nwhere μ is the [Möbius function](https://bliptext.com/articles/m-bius-function), the [multiplicative function](https://bliptext.com/articles/multiplicative-function) defined by \\mu(p) = -1 and for each prime\np\nand\nk ≥ 2\n. This formula may also be derived from the product formula by multiplying out to get\nAn example:\n\n# Some values\nThe first 100 values are shown in the table and graph below:\nφ(n)\nfor\n1 ≤ n ≤ 100\n! + ! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 ! 0 ! 10 ! 20 ! 30 ! 40 ! 50 ! 60 ! 70 ! 80 ! 90\nIn the graph at right the top line\nis an [upper bound](https://bliptext.com/articles/upper-bound) valid for all n other than one, and attained if and only if n is a prime number.\nA simple lower bound is, which is rather loose: in fact, the [lower limit](https://bliptext.com/articles/limit-superior-and-limit-inferior) of the graph is proportional to\nn⁄log log n\n.\n# [Graph of the first 100 values | upload.wikimedia.org/wikipedia/commons/f/f3/EulerPhi100.svg]\n\n# Euler's theorem\nThis states that if a and n are [relatively prime](https://bliptext.com/articles/relatively-prime) then\nThe special case where n is prime is known as [Fermat's little theorem](https://bliptext.com/articles/fermat-s-little-theorem).\nThis follows from [Lagrange's theorem](https://bliptext.com/articles/lagrange-s-theorem-group-theory) and the fact that\nφ(n)\nis the [order](https://bliptext.com/articles/order-group-theory) of the [multiplicative group of integers modulo n](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n).\nThe [RSA cryptosystem](https://bliptext.com/articles/rsa-algorithm) is based on this theorem: it implies that the [inverse](https://bliptext.com/articles/inverse-function) of the function\na ↦ ae mod n\n, where e is the (public) encryption exponent, is the function\nb ↦ bd mod n\n, where d, the (private) decryption exponent, is the [multiplicative inverse](https://bliptext.com/articles/multiplicative-inverse) of e modulo\nφ(n)\n. The difficulty of computing\nφ(n)\nwithout knowing the factorization of n is thus the difficulty of computing d: this is known as the [RSA problem](https://bliptext.com/articles/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. Only n is publicly disclosed, and given the [difficulty to factor large numbers](https://bliptext.com/articles/integer-factorization) we have the guarantee that no one else knows the factorization.\n\n# Other formulae\n

\nIn particular:\n
\nCompare this to the formula (see [least common multiple](https://bliptext.com/articles/least-common-multiple)).\n
\nφ(n)\nis even for\nn ≥ 3\n. Moreover, if n has r distinct odd prime factors,\n2r\n
For any\na > 1\nand\nn > 6\nsuch that\n4 ∤ n\nthere exists an\nl ≥ 2n\nsuch that\nl\n.
\nwhere\nrad(n)\nis the [radical of n](https://bliptext.com/articles/radical-of-an-integer) (the product of all distinct primes dividing n).\n
( cited in )
[Liu (2016)]
(where γ is the [Euler–Mascheroni constant](https://bliptext.com/articles/euler-mascheroni-constant)).\n

\n\n## Menon's identity\nIn 1965 P. Kesava Menon proved\nwhere\nd(n) = σ0(n)\nis the number of divisors of n.\n\n## Divisibility by any fixed positive integer\nThe following property, which is part of the « folklore » (i.e., apparently unpublished as a specific result: see the introduction of this article in which it is stated as having « long been known ») has important consequences.\nFor instance it rules out uniform distribution of the values of \\varphi(n) in the arithmetic progressions modulo q for any integer q>1.\nThis is an elementary consequence of the fact that the sum of the reciprocals of the primes congruent to 1 modulo q diverges, which itself is a corollary of the proof of [Dirichlet's theorem on arithmetic progressions](https://bliptext.com/articles/dirichlet-s-theorem-on-arithmetic-progressions).\n\n# Generating functions\nThe [Dirichlet series](https://bliptext.com/articles/dirichlet-series) for\nφ(n)\nmay be written in terms of the [Riemann zeta function](https://bliptext.com/articles/riemann-zeta-function) as:\nwhere the left-hand side converges for \\Re (s)>2.\nThe [Lambert series](https://bliptext.com/articles/lambert-series) generating function is\nwhich converges for\n.\nBoth of these are proved by elementary series manipulations and the formulae for\nφ(n)\n.\n\n# Growth rate\nIn the words of Hardy & Wright, the order of\nφ(n)\nis \"always 'nearly n'.\"\nFirst\nbut as n goes to infinity, for all\nδ > 0\nThese two formulae can be proved by using little more than the formulae for\nφ(n)\nand the [divisor sum function](https://bliptext.com/articles/divisor-function)\nσ(n)\n.\nIn fact, during the proof of the second formula, the inequality\ntrue for\nn > 1\n, is proved.\nWe also have\nHere γ is [Euler's constant](https://bliptext.com/articles/euler-mascheroni-constant),\n, so\nand\ne−γ = 0.56145948...\n.\nProving this does not quite require the [prime number theorem](https://bliptext.com/articles/prime-number-theorem).\nSince\nlog log n\ngoes to infinity, this formula shows that\nIn fact, more is true.\nand\nThe second inequality was shown by [Jean-Louis Nicolas](https://bliptext.com/articles/jean-louis-nicolas).\nRibenboim says \"The method of proof is interesting, in that the inequality is shown first under the assumption that the [Riemann hypothesis](https://bliptext.com/articles/riemann-hypothesis) is true, secondly under the contrary assumption.\"\nFor the average order, we have\ndue to [Arnold Walfisz](https://bliptext.com/articles/arnold-walfisz), its proof exploiting estimates on exponential sums due to [I. M. Vinogradov](https://bliptext.com/articles/ivan-matveevich-vinogradov) and [N. M. Korobov](https://bliptext.com/articles/n-m-korobov).\nBy a combination of van der Corput's and Vinogradov's methods, H.-Q.\nLiu (On Euler's function.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775)\nimproved the error term to (this is currently the best known estimate of this type).\nThe [\"Big O\"](https://bliptext.com/articles/big-o-notation) stands for a quantity that is bounded by a constant times the function of n inside the parentheses (which is small compared to\nn2\n).\nThis result can be used to prove that [the probability of two randomly chosen numbers being relatively prime](https://bliptext.com/articles/coprime-integers) is 6⁄π2.\n\n# Ratio of consecutive values\nIn 1950 Somayajulu proved\nIn 1954 [Schinzel](https://bliptext.com/articles/andrzej-schinzel) and [Sierpiński](https://bliptext.com/articles/wac-aw-sierpi-ski) strengthened this, proving that the set\nis [dense](https://bliptext.com/articles/dense-set) in the positive real numbers.\nThey also proved that the set\nis dense in the interval (0,1).\n\n# Totient numbers\nA **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. The valency or multiplicity of a totient number m is the number of solutions to this equation.\nA [nontotient](https://bliptext.com/articles/nontotient) is a natural number which is not a totient number.\nEvery odd integer exceeding 1 is trivially a nontotient.\nThere are also infinitely many even nontotients, and indeed every positive integer has a multiple which is an even nontotient.\nThe number of totient numbers up to a given limit x is\nfor a constant\n.\nIf counted accordingly to multiplicity, the number of totient numbers up to a given limit x is\nwhere the error term R is of order at most\nx⁄(log x)k\nfor any positive k.\nIt is known that the multiplicity of m exceeds\nmδ\ninfinitely often for any\nδ < 0.55655\n.\n\n## Ford's theorem\nproved that for every integer\nk ≥ 2\nthere is a totient number m of multiplicity k: that is, for which the equation\nhas exactly k solutions; this result had previously been conjectured by [Wacław Sierpiński](https://bliptext.com/articles/wac-aw-sierpi-ski), and it had been obtained as a consequence of [Schinzel's hypothesis H](https://bliptext.com/articles/schinzel-s-hypothesis-h).\nIndeed, each multiplicity that occurs, does so infinitely often.\nHowever, no number m is known with multiplicity\n. [Carmichael's totient function conjecture](https://bliptext.com/articles/carmichael-s-totient-function-conjecture) is the statement that there is no such m.\n\n## Perfect totient numbers\nA perfect totient number is an integer that is equal to the sum of its iterated totients.\nThat is, we apply the totient function to a number n, apply it again to the resulting totient, and so on, until the number 1 is reached, and add together the resulting sequence of numbers; if the sum equals n, then n is a perfect totient number.\n\n# Applications\n\n## Cyclotomy\nIn the last section of the Disquisitiones Gauss proves that a regular n-gon can be constructed with straightedge and compass if\nφ(n)\nis a power of 2.\nIf 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\nn − 1\nis a power of 2.\nThe primes that are one more than a power of 2 are called [Fermat primes](https://bliptext.com/articles/fermat-prime), and only five are known: 3, 5, 17, 257, and 65537.\nFermat and Gauss knew of these.\nNobody has been able to prove whether there are any more.\nThus, a regular n-gon has a straightedge-and-compass construction if n is a product of distinct Fermat primes and any power of 2.\nThe first few such n are\n\n## Prime number theorem for arithmetic progressions\n\n## The RSA cryptosystem\nSetting up an RSA system involves choosing large prime numbers p and q, computing\nand\n, and finding two numbers e and d such that\ned ≡ 1 (mod k)\n. The numbers n and e (the \"encryption key\") are released to the public, and d (the \"decryption key\") is kept private.\nA message, represented by an integer m, where\n0 < m < n\n, is encrypted by computing\n.\nIt is decrypted by computing\n. Euler's Theorem can be used to show that if\n0 < t < n\n, then\n.\nThe security of an RSA system would be compromised if the number n could be efficiently factored or if\nφ(n)\ncould be efficiently computed without factoring n.\n\n# Unsolved problems\n\n## Lehmer's conjecture\nIf p is prime, then\n. In 1932 [D. H. Lehmer](https://bliptext.com/articles/d-h-lehmer) asked if there are any composite numbers n such that\nφ(n)\ndivides\nn − 1\n. None are known.\nIn 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ω(n) ≥ 7\n). In 1980 Cohen and Hagis proved that\nn > 1020\nand that\nω(n) ≥ 14\n. Further, Hagis showed that if 3 divides n then\nn > 101937042\nand\nω(n) ≥ 298848\n.\n\n## Carmichael's conjecture\nThis states that there is no number n with the property that for all other numbers m,\nm ≠ n\n,\nφ(m) ≠ φ(n)\n. See [Ford's theorem](https://bliptext.com/articles/) above.\nAs stated in the main article, if there is a single counterexample to this conjecture, there must be infinitely many counterexamples, and the smallest one has at least ten billion digits in base 10.\n\n## Riemann hypothesis\nThe [Riemann hypothesis](https://bliptext.com/articles/riemann-hypothesis) is true if and only if the inequality\nis true for all\nn ≥ p120569#\nwhere γ is [Euler's constant](https://bliptext.com/articles/euler-s-constant) and\np120569#\nis the [product of the first](https://bliptext.com/articles/primorial)\n120569\nprimes.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T17:38:00.237Z","updated_at":"2025-01-25T17:38:00.237Z","search_vector":"'euler':1 'function':4 'totient':3","search_content":" \n \n\n# \n[[Image:EulerPhi.svg|thumb|The first thousand values of\nφ(n)\n. The points on the top line represent\nφ(p)\nwhen p is a prime number, which is\np − 1.\n]]\nIn [number theory](https://bliptext.com/articles/number-theory), **Euler's totient function** counts the positive integers up to a given integer n that are [relatively prime](https://bliptext.com/articles/relatively-prime) to n. It is written using the Greek letter [phi](https://bliptext.com/articles/phi) as \\var[phi](https://bliptext.com/articles/phi)(n) or \\[phi](https://bliptext.com/articles/phi)(n), and may also be called **Euler's [phi](https://bliptext.com/articles/phi) function**.\nIn other words, it is the number of integers k in the range\n1 ≤ k ≤ n\nfor which the [greatest common divisor](https://bliptext.com/articles/greatest-common-divisor)\ngcd(n, k)\nis equal to 1.\nThe integers k of this form are sometimes referred to as [totatives](https://bliptext.com/articles/totative) of n.\nFor example, the totatives of\nn = 9\nare the six numbers 1, 2, 4, 5, 7 and 8.\nThey are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since\ngcd(9, 3) = gcd(9, 6) = 3\nand\ngcd(9, 9) = 9\n. Therefore,\nφ(9) = 6\n. As another example,\nφ(1) = 1\nsince for\nn = 1\nthe only integer in the range from 1 to n is 1 itself, and\ngcd(1, 1) = 1\n.\nEuler's totient function is a [multiplicative function](https://bliptext.com/articles/multiplicative-function), meaning that if two numbers m and n are relatively prime, then\nφ(mn) = φ(m)φ(n)\n. This function gives the [order](https://bliptext.com/articles/order-[group](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n)-theory) of the [multiplicative [group](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n) of integers modulo n](https://bliptext.com/articles/multiplicative-[group](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n)-of-integers-modulo-n) (the [group](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n) of [units](https://bliptext.com/articles/unit-[ring](https://bliptext.com/articles/ring-algebra)-theory) of the [ring](https://bliptext.com/articles/ring-algebra) \\Z/n\\Z).\nIt is also used for defining the [RSA encryption system](https://bliptext.com/articles/rsa-cryptosystem).\n\n# History, terminology, and notation\n[Leonhard Euler](https://bliptext.com/articles/leonhard-euler) introduced the function in 1763.\nHowever, he did not at that time choose any specific symbol to denote it.\nIn a 1784 publication, Euler studied the function further, choosing the Greek letter π to denote it: he wrote\nπD\nfor \"the multitude of numbers less than D, and which have no common divisor with it\".\nThis definition varies from the current definition for the totient function at\nD = 1\nbut is otherwise the same.\nThe now-standard notation\nφ(A)\ncomes from [Gauss](https://bliptext.com/articles/gauss)'s 1801 treatise [Disquisitiones Arithmeticae](https://bliptext.com/articles/disquisitiones-arithmeticae), although [Gauss](https://bliptext.com/articles/gauss) did not use parentheses around the argument and wrote\nφA\n. Thus, it is often called **Euler's **phi function**** or simply the **phi function**.\nIn 1879, [J. J. Sylvester](https://bliptext.com/articles/james-joseph-sylvester) coined the term **totient** for this function, so it is also referred to as Euler's **totient** function, the Euler **totient**, or Euler's **totient**.\n[Jordan's totient](https://bliptext.com/articles/jordan-s-totient-function) is a generalization of Euler's.\nThe **cototient** of n is defined as\nn − φ(n)\n. It counts the number of positive integers less than or equal to n that have at least one [prime factor](https://bliptext.com/articles/prime-number) in common with n.\n\n# Computing Euler's totient function\nThere are several formulae for computing\nφ(n)\n.\n\n## Euler's product formula\nIt states\nwhere the product is over the distinct [prime numbers](https://bliptext.com/articles/prime-number) dividing n. (For notation, see [Arithmetical function](https://bliptext.com/articles/arithmetical-function).)\nAn equivalent formulation is where is the [prime factorization](https://bliptext.com/articles/prime-factorization) of n (that is, are distinct prime numbers).\nThe proof of these formulae depends on two important facts.\n\n### Phi is a multiplicative function\nThis means that if\ngcd(m, n) = 1\n, then\nφ(m) φ(n) = φ(mn)\n. Proof outline: Let A, B, C be the sets of positive integers which are [coprime](https://bliptext.com/articles/coprime) to and less than m, n, mn, respectively, so that\nA\n, etc. Then there is a [bijection](https://bliptext.com/articles/bijection) between\nA × B\nand C by the [Chinese remainder theorem](https://bliptext.com/articles/chinese-remainder-theorem).\n\n### Value of phi for a prime power argument\nIf p is prime and\nk ≥ 1\n, then\nProof: Since p is a prime number, the only possible values of\ngcd(pk, m)\nare\n1, p, p2, ..., pk\n, and the only way to have\ngcd(pk, m) > 1\nis if m is a multiple of p, that is,\nm ∈\n, and there are\npk − 1\nsuch multiples not greater than\npk\n. Therefore, the other\npk − pk − 1\nnumbers are all relatively prime to\npk\n.\n\n### Proof of Euler's product formula\nThe [fundamental theorem of arithmetic](https://bliptext.com/articles/fundamental-theorem-of-arithmetic) states that if\nn > 1\nthere is a unique expression where\np1 \n \n \n \nIn particular:\n \nCompare this to the formula (see [least common multiple](https://bliptext.com/articles/least-common-multiple)).\n \n \nφ(n)\nis even for\nn ≥ 3\n. Moreover, if n has r distinct odd prime factors,\n2r\n \n For any\na > 1\nand\nn > 6\nsuch that\n4 ∤ n\nthere exists an\nl ≥ 2n\nsuch that\nl\n. \n \nwhere\nrad(n)\nis the [radical of n](https://bliptext.com/articles/radical-of-an-integer) (the product of all distinct primes dividing n).\n \n \n \n ( cited in ) \n [Liu (2016)] \n \n \n (where γ is the [Euler–Mascheroni constant](https://bliptext.com/articles/euler-mascheroni-constant)).\n \n \n\n## Menon's identity\nIn 1965 P. Kesava Menon proved\nwhere\nd(n) = σ0(n)\nis the number of divisors of n.\n\n## Divisibility by any fixed positive integer\nThe following property, which is part of the « folklore » (i.e., apparently unpublished as a specific result: see the introduction of this article in which it is stated as having « long been known ») has important consequences.\nFor instance it rules out uniform distribution of the values of \\varphi(n) in the arithmetic progressions modulo q for any integer q>1.\nThis is an elementary consequence of the fact that the sum of the reciprocals of the primes congruent to 1 modulo q diverges, which itself is a corollary of the proof of [Dirichlet's theorem on arithmetic progressions](https://bliptext.com/articles/dirichlet-s-theorem-on-arithmetic-progressions).\n\n# Generating functions\nThe [Dirichlet series](https://bliptext.com/articles/dirichlet-series) for\nφ(n)\nmay be written in terms of the [Riemann zeta function](https://bliptext.com/articles/riemann-zeta-function) as:\nwhere the left-hand side converges for \\Re (s)>2.\nThe [Lambert series](https://bliptext.com/articles/lambert-series) generating function is\nwhich converges for\n.\nBoth of these are proved by elementary series manipulations and the formulae for\nφ(n)\n.\n\n# Growth rate\nIn the words of Hardy & Wright, the order of\nφ(n)\nis \"always 'nearly n'.\"\nFirst\nbut as n goes to infinity, for all\nδ > 0\nThese two formulae can be proved by using little more than the formulae for\nφ(n)\nand the [divisor sum function](https://bliptext.com/articles/divisor-function)\nσ(n)\n.\nIn fact, during the proof of the second formula, the inequality\ntrue for\nn > 1\n, is proved.\nWe also have\nHere γ is [Euler's constant](https://bliptext.com/articles/euler-mascheroni-constant),\n, so\nand\ne−γ = 0.56145948...\n.\nProving this does not quite require the [prime number theorem](https://bliptext.com/articles/prime-number-theorem).\nSince\nlog log n\ngoes to infinity, this formula shows that\nIn fact, more is true.\nand\nThe second inequality was shown by [Jean-Louis Nicolas](https://bliptext.com/articles/jean-louis-nicolas).\nRibenboim says \"The method of proof is interesting, in that the inequality is shown first under the assumption that the [Riemann hypothesis](https://bliptext.com/articles/riemann-hypothesis) is true, secondly under the contrary assumption.\"\nFor the average order, we have\ndue to [Arnold Walfisz](https://bliptext.com/articles/arnold-walfisz), its proof exploiting estimates on exponential sums due to [I. M. Vinogradov](https://bliptext.com/articles/ivan-matveevich-vinogradov) and [N. M. Korobov](https://bliptext.com/articles/n-m-korobov).\nBy a combination of van der Corput's and Vinogradov's methods, H.-Q.\nLiu (On Euler's function.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775)\nimproved the error term to (this is currently the best known estimate of this type).\nThe [\"Big O\"](https://bliptext.com/articles/big-o-notation) stands for a quantity that is bounded by a constant times the function of n inside the parentheses (which is small compared to\nn2\n).\nThis result can be used to prove that [the probability of two randomly chosen numbers being relatively prime](https://bliptext.com/articles/coprime-integers) is 6⁄π2.\n\n# Ratio of consecutive values\nIn 1950 Somayajulu proved\nIn 1954 [Schinzel](https://bliptext.com/articles/andrzej-schinzel) and [Sierpiński](https://bliptext.com/articles/wac-aw-sierpi-ski) strengthened this, proving that the set\nis [dense](https://bliptext.com/articles/dense-set) in the positive real numbers.\nThey also proved that the set\nis dense in the interval (0,1).\n\n# Totient numbers\nA **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. The valency or multiplicity of a totient number m is the number of solutions to this equation.\nA [nontotient](https://bliptext.com/articles/nontotient) is a natural number which is not a totient number.\nEvery odd integer exceeding 1 is trivially a nontotient.\nThere are also infinitely many even nontotients, and indeed every positive integer has a multiple which is an even nontotient.\nThe number of totient numbers up to a given limit x is\nfor a constant\n.\nIf counted accordingly to multiplicity, the number of totient numbers up to a given limit x is\nwhere the error term R is of order at most\nx⁄(log x)k\nfor any positive k.\nIt is known that the multiplicity of m exceeds\nmδ\ninfinitely often for any\nδ 1020\nand that\nω(n) ≥ 14\n. Further, Hagis showed that if 3 divides n then\nn > 101937042\nand\nω(n) ≥ 298848\n.\n\n## Carmichael's conjecture\nThis states that there is no number n with the property that for all other numbers m,\nm ≠ n\n,\nφ(m) ≠ φ(n)\n. See [Ford's theorem](https://bliptext.com/articles/) above.\nAs stated in the main article, if there is a single counterexample to this conjecture, there must be infinitely many counterexamples, and the smallest one has at least ten billion digits in base 10.\n\n## Riemann hypothesis\nThe [Riemann hypothesis](https://bliptext.com/articles/riemann-hypothesis) is true if and only if the inequality\nis true for all\nn ≥ p120569#\nwhere γ is [Euler's constant](https://bliptext.com/articles/euler-s-constant) and\np120569#\nis the [product of the first](https://bliptext.com/articles/primorial)\n120569\nprimes.","revisionCount":0},"hasMore":false,"nextCursor":null}