Euler's φ function

The first thousand values ${displaystyle scriptstyle varphi (n)}$.

The Euler function φ (also called the Euler indicator function or totient function ) is an important function in number theory. If n is a positive integer, then φ(n) is defined as the number of positive integers less than n and we coprime with n, that is, it can be formally defined as:

${displaystyle varphi (n)=associated{min mathbb {N} ⋅ mleq n land mathrm {mcd} (m,n)=1}$

where |·| means the cardinality of the described set.

Another way of defining the tociente of a natural number n is to indicate that it is the number of positive integers less than n such that the greatest common factor with respect to n is equal to 1.

The φ function is important mainly because it provides the size of the multipliative group of integers module n. More precisely, ${displaystyle varphi (n)}$ is the order of the ring unit group ${displaystyle mathbb {Z} /nmathbb {Z} }$. In fact, along with the Lagrange theorem of the possible subgroup sizes of a group, it provides a demonstration of the Euler theorem that says that ${displaystyle a^{varphi (n)}equiv 1{pmod {n}}$ for everything a copress with n. The φ function also plays a key role in defining the RSA encryption system.

History, terminology and notation

Leonhard Euler introduced the function in 1763. However, at the time he did not choose any specific symbol to denote it. In a 1784 publication, Euler studied the function again further, choosing the Greek letter π to denote it: he wrote πD for "the multitude of numbers less than D< /span>, and that they do not have a common divisor with it". This definition varies from the current definition of the totient function at D = 1 but is otherwise the same. The now standard notation φ(A) comes from Carl Friedrich Gauss's 1801 treatise Disquisitiones arithmeticae , although Gauss did not use parentheses around the argument and wrote φA. Therefore, it is often called the Euler phi function or simply the phi function.

In 1879, J. J. Sylvester coined the term totient for this function, which is why it is also known as the Euler totient function, totient of Euler, or Euler's totient. Jordan's totient is a generalization of Euler's idea.

The cototient of ${displaystyle n}$ defined as ${displaystyle n-varphi (n)}$. Counts the number of positive integers less or equal to ${displaystyle n}$ that have at least one prime factor in common with ${displaystyle n}$.

First properties and calculation of the function

Follows the definition that ${displaystyle varphi (1)=1}$therefore the element ${displaystyle 1}$ It can only be copressed with itself. For other numbers it is fulfilled that:

1. ${displaystyle varphi (p)=p-1}$ Yeah. ${displaystyle p}$ He's a cousin.
2. ${displaystyle varphi (p^{k})=(p-1)p^{k-1}}$ Yeah. ${displaystyle p}$ He's a cousin. ${displaystyle k}$ It's a natural number.
3. ${displaystyle varphi }$ is a multipliative function: yes ${displaystyle m}$ and ${displaystyle n}$ They're coprimos, then ${displaystyle varphi (mn)=varphi (m)varphi (n)}$.

La first property is shown easily, because a prime number is co-pressed with all its previous numbers. And therefore they exist ${displaystyle p-1}$ coprimos elements ${displaystyle p}$. In other words, like ${displaystyle p}$ he is a cousin only to have of divisors himself and the unity, which is present in the ${displaystyle p-1}$ previous numbers ${displaystyle p}$.

For the Second propertyWe must observe that if ${displaystyle p}$ He's a cousin only his multiples. ${displaystyle np}$ minors or equals ${displaystyle p^{k}}$ present a common divider with ${displaystyle p^{k}}$ different from one. This is, ${displaystyle 1p,2p,3p,...,(p^{k-1}p}$ are the only numbers ${displaystyle m}$ such that ${displaystyle mathrm {mcd} (p^{k},m)neq 1}$. As in total ${displaystyle p^{k-1}$ numbers that satisfy this property, the rest of numbers between ${displaystyle 1}$ and ${displaystyle p^{k}}$ They only have ${displaystyle 1}$ as a common divider with ${displaystyle p^{k}}$. This is, ${displaystyle varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}}}$. (Note that this second property is fulfilled because ${displaystyle p}$ He's a cousin. Indeed, if there was a ${displaystyle mneq np}$, ${displaystyle mgeq 2}$ such as ${displaystyle mathrm {mcd} (p^{k},m)=aneq 1}$, then ${displaystyle a}$ would be splitter ${displaystyle p^{k}=pcdot p... p}$ (${displaystyle k}$ sometimes); i.e., ${displaystyle a}$ would be a power (and therefore multiple) ${displaystyle p}$contradicting the initial assumption ${displaystyle mneq np}$).

To demonstrate third property, be it ${displaystyle A}$, ${displaystyle B}$, ${displaystyle C}$ the sets of positive integers that are coprimos and less than ${displaystyle m}$, ${displaystyle n}$, ${displaystyle mn}$ respectively (then $(m)}$, $(n)}$ and $(mn)$). Then, for the Chinese Theorem of Resto there is a bijection between ${displaystyle C}$ and ${displaystyle Atimes B}$, which implies that ${displaystyle varphi (mn)=varphi (m)varphi (n)}$.

With this, the value of ${displaystyle varphi (n)}$ can be calculated using the Fundamental Theorem of Arithmetic: if

${displaystyle n=p_{1}^{k_{1}}cdots p_{r}{k_{r}}}}}{k$

where the p_j are distinct prime numbers, then

${displaystyle varphi (n)=(p_{1}-1)p_{1}^{k_{1}}-1cdots (p_{r}-1)p_{r}^{k_{r}-1}. !$

This formula can be rewritten as follows (known as the Euler Product Formula):

${displaystyle varphi (n)=nprod _{pąn}left(1-{frac {1}{p}}}right)}$

where the ${displaystyle p}$ are the different cousins who divide to ${displaystyle n}$.

Calculation example

${displaystyle varphi (36)=varphi left(3^{2}2^{2}{2right)=36left(1-{frac {1}{3}}}right)left(1-{frac} {1}{1}{2}{2}{2}{2}{2}{2}{2}{2}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{2}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{1}{2}{frac}}}}}}}}}}}{1}}}{1}{1}}}}}}{ !$

Also,

${displaystyle varphi (36)=varphi left(3^{2}2^{2right)=(3-1)3^{(2-1)}(2-1)2^{(2-1)}}=2cdot 3cdot 1cdot 2=12. !$

You can manually check that the numbers coprime with 36 (that is, they are not divisible by 2 or 3) are twelve: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, and 35.

Fourier transform

The totient is the discrete Fourier transform of the gcd, evaluated at 1. Let

${displaystyle {mathcal {F}}{mathbf {x}}{m]=sum limits _{k=1}^{n}x_{k}cdot e^{{{{{-2pi i}{frac {mk}{n}}}}}}}}{cdot e^$

where x_k = gcd(k,n)< /span> for k ∈ {1,..., n}. So

${displaystyle varphi (n)={mathcal {F}}{mathbf {x}}}[1]=sum limits _{k=1}^{n}operatorname {mcd} (k,n)e^{-2pi i{frac {k}{n}}}}}}{. !$

The real part of this formula is

${displaystyle varphi (n)=sum limits _{k=1}^{n}operatorname {mcd} (k,n)cos {tfrac {2pi k}{n}}}}}}}$

Unlike the Euler product and divisor sum formula, this one doesn't require knowing the factors of n. However, it involves computing the greatest common factor of n and any positive integer less than n, which is enough to provide the factorization anyway.

Sum of its divisors

The property established by Gauss, that

${displaystyle sum _{dmid n}varphi (d)=n,}$

where the sum is over all positive divisors d of n, can be demonstrated in several ways (see arithmetic function for notation conventions).

One proof is to note that φ(d) is also equal to the number of possible generators of the cyclic group < span class="texhtml">C_d; specifically, if C_d = ⟨g⟩ with g^d= 1, so g^k is a generator for each coprime of k a d. Since each element of C_n generates a cyclic subgroup, and all subgroups < span class="texhtml">C_d ⊆ C_n are generated precisely by φ(d) elements of C_n, the formula is as follows. Equivalently, the formula can be derived using the same argument applied to the multiplicative group of the roots of unity nth roots of unity and d-th primitives.

The formula can also be derived from elementary arithmetic. For example, let n = 20 and consider positive fractions up to 1 with denominator twenty:

${cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFFFF}{cHFFFFFFFF}{cHFFFFFF}{cHFFFF}{cHFFFFFF}{cHFFFFFFFFFFFF}{cH00}{cH00}{cH00}{cH00}{cH00}{cH00}{cH00}{cHFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF}{cH00}{cH00}{cH00}{cH00}{cH00}{cHFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF}{cH00}{cH00}{cH00}{c !$

Reducing them to smallest terms:

${cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFFFF}{cHFFFF}{cHFFFFFF}{cH00}{cH00}{cHFFFFFFFFFFFFFFFFFF}{cH00}{cH00}{cH00}{cH00}{cH00}{cHFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF}{cH00}{cH00}{cH00}{cH00}{cH00}{cHFFFFFFFFFFFFFFFFFF}{cH00}{cH00}{cH00}{cH00}{cHFFFFFFFFFFFFFFFFFFFFFF$

These twenty fractions are all k/ d ≤ positive 1 whose denominators are the divisors d = 1, 2, 4, 5, 10, 20. 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 and 19/20. By definition, this is the φ(20) fractions with denominator 20. Similarly, there are φ(10) fractions with denominator 10 and φ(5) fractions with denominator 5, etc. Therefore, the set of twenty fractions is divided into subsets of size φ(d) for each d that divides 20. A similar argument applies for any n.

The Möbius inversion formula applied to the divisor sum formula gives

${displaystyle varphi (n)=sum _{dmid n}mu left(dright)cdot {frac {n}{d}}}=nsum _{dmid n}{frac {mu (d)}{{d}}}}{,}$

where μ is the function of Möbius, the multipliative function defined by ${displaystyle mu (p)=-1}$ and ${displaystyle mu (p^{k})=0}$ for every cousin p and k ≥ 2. This formula can also be derived from the product formula multiplying ${textstyle prod _{pmid n}(1-{frac {1}{p}})}$ to get ${textstyle sum _{dmid n}{frac {mu (d)}{d}}. !$

An example:

${displaystyle {begin{aligned}varphi (20) stranger=mu (1)cdot 20+mu (2)cdot 10+mu (4)cdot 5+mu (5)cdot 4+mu (10)cdot 2+mu (20)cdot 1.5em}{1cdot 20-1cdot 10+0$

Some values

Graphical representation of the first 100 values. Note that the lower limit marked by the straight and = 4n/15 is not the lower limit of the function globally, but for multiples of 30.

The first 99 values of the function are written in the following table, as well as graphically.

${displaystyle varphi (n)}$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Euler's Theorem

Euler's theorem states that if a and n are coprime numbers, so

${displaystyle a^{varphi (n)}equiv 1mod n. !$

The special case where n is prime is known as Fermat's little theorem.

This follows from Lagrange's theorem and from the fact that φ(n) is the order of the group multiplicative of integers modulo n.

The RSA encryption system is based on this theorem: it implies that the inverse of the function a ↦ a^e mod n, where e is the encryption exponent (public), is the function b ↦ b^d mod n, where d, the decryption (private) exponent, is the multiplicative inverse of e module φ(n). The difficulty of calculating φ(n) without knowing the factorization of n is therefore 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 prime numbers large (chosen at random) p and q. Only n is publicly disclosed, and given the difficulty of factoring very large numbers, you are guaranteed that no one else will know about the factorization.

Other formulas

• ${displaystyle amid bimplies varphi (a)mid varphi (b)}$
• ${displaystyle nmid varphi (a^{n}-1)}$ (${displaystyle n,ain mathbb {N} }$ ${displaystyle ageq 2}$): Sea ${displaystyle m=a^{n}-1}$. Then we have to:

${displaystyle qquad operatorname {mcd} (a,m)=operatorname {mcd} (a,a^{n}-1)=operatorname {mcd} (a,1)=1 ♪♪ ♪♪ ♪♪ ♪♪ ♪♪ ♪♪ ♪♪ ♪♪ ♪♪ ♪♪ ♪♪♪♪ ♪♪♪♪♪♪♪ ♪♪ ♪♪ ♪♪♪♪♪ ♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪♪ Rightarrow ≤1⁄4⁄4⁄2⁄2⁄2⁄2⁄2⁄2⁄2⁄2⁄2a}}{,}$. Then, by the Theorem of Lagrange, ${displaystyle أعربية}$ divide a ${displaystyle 日本語 mathbb {Z} _{m}^{*},$.

${displaystyle qquad }$But ${displaystyle a^{k}{m}$ Yeah. ${displaystyle krivn Rightarrow a regula=n}$ and also ${displaystyle 日本語 mathbb {Z} _{m}^{*},$.

${displaystyle qquad }$So, ${displaystyle nmid varphi (m)Rightarrow nmid varphi (a^{n}-1}}$

• ${displaystyle varphi (mn)=varphi (m)varphi (n)cdot {frac {d}{varphi}}}}}}$ where ${displaystyle d=operatorname {mcd} (m,n)}$

${displaystyle qquad }$Note the special cases:

• ${displaystyle varphi (2m)={begin{cases}2varphi (m) fake{text{}{text{ es par}}}}\varphi (m) pretend{text{ if }m{text{ is impar}}}{end{cases}}}}}$
• ${displaystyle varphi left(n^{m}right)=n^{m-1}varphi (n)}$
• ${displaystyle varphi (operatorname {mcm} (m,n))cdot varphi (operatorname {mcd} (m,n))=varphi (m)cdot varphi (n)}$

${displaystyle qquad rightarrow }$ Share this with the formula ${displaystyle operatorname {mcm} (m,n)cdot operatorname {mcd} (m,n)=mcdot n}$ (see minimum common multiple (mcm) and maximum common divider (mcd)).

• φ(n) It's a pair. n ≥ 3. Besides, if n It has r different odd prime factors, 2^r 日本語 φ(n)
• For any a ▪ 1 and n ▪ 6 such as 4 n There is a l ≥ 2n such as l 日本語 φ(aⁿ (1).
• ${displaystyle {frac {varphi}{n}}}={frac {varphi (operatorname {rad}}{operatorname {rad}{operatorname {rad}}}}}}$

${displaystyle qquad }$where rad(n) is the radical of n (the product of all different cousins that divide n).

• ${displaystyle sum _{dmid n}{frac {mu ^{2}{}{varphi}}}}{frac {n}{varphi (n)}}}}}}}}$
• ${displaystyle sum _{1leq kleq n atop (k,n)=1}!!k={tfrac {1}{2}nvarphi (n)quad {text{ para }}n literal1}$
• ${displaystyle sum _{k=1}{n}varphi (k)={tfrac {1}{2}{2}{2}{1+sum _{k=1}{n}{n}{n}{x1}{2}{2⁄2}{ph}{f}{c(s)}{c(s)}{c(s)}{c(s)}{c)}{c(s)}{c)}{c(s)}{c)}{c(s)}{c)}{c(s)}{c(s)}{c(s)}{c(s)}{c(s)}{c(s)}{c(s)}{c)}{c(s)}{c(s)}{c(s)}{c(s)}{c)}{c(s)}{c(s)}{c(s)$(quoted in)
• ${displaystyle sum _{k=1}{n}{frac {varphi}{k}}}=sum _{k=1}{n}{frac {mu(k)}{k}{x1}{x1}{x1}{x1}{x1⁄2}{x1⁄2}{f}{c(s)}{b1⁄2⁄2⁄2}{f}}}{c(s)}{f)}{c(s)}{c(s)}{c)}{c(s)}{c(s)}{c(s)}{c(s)}{c(s)}{c(s)}{c(s)}{c(s)}{c(s)}{c)}{c(s)}{c(s)}{c)}{c(s)}{c(s)}{c)}{c)}{$
• ${displaystyle sum _{k=1}^{n}{frac {k}{varphi (k)}}}={frac {315,zeta (3)}{2pi ^{4}}}n-{frac {log n}{2}}}} +Oleft(log n)^{frac {2}{3}{3}{right}$
• ${displaystyle sum _{k=1}{n}{frac {1}{varphi (k)}}{frac {315,zeta (3)}{2pi ^{4}}{1}{left(log n+gamma -sum _{p{text{ prime}}}{frac {ft}{ft {c(1⁄2}{x1⁄2}}}{c)}{x1⁄2}{x1⁄2}}}{c)}{x1⁄2}{x1⁄2}{x1⁄2}}}}{c)}{x1⁄2}{x1⁄2}{cd}}}}{cd)}}}{cd)}}{cd)}{cd)}}{cd)}{$

${displaystyle qquad }$where γ is the constant of Euler-Mascheroni.

• ${displaystyle sum _{stackrel {1leq kleq n}{operatorname {mcd} (k,m)=1}!!!1=n{frac {varphi}{m}}}} +Oleft(2^{omega (m)}right}}}$

${displaystyle qquad }$where m ▪ 1 is a positive integer and ω(m) is the number of prime factors other than m.

Menon's identity

In 1965, P. Kesava Menon showed that

${displaystyle sum _{stackrel {1leq kleq n}{operatorname {mcd} (k,n)=1}!!operatorname {mcd} (k-1,n)=varphi(n)d(n)}$

where d(n) = σ0(n) is the number of divisors of n.

Formulas involving the golden ratio

Schneider found a pair of identities connecting the totient function, the golden ratio and the Möbius function μ(n) . In this section, φ(n) is the totient function and ϕ = 1 + √5/2 = 1.618... is the golden ratio.

You have to:

${displaystyle phi =-sum _{k=1}{infty }{frac {varphi}{k}}}{k}}log left(1-{frac {1}{phi ^{k}}}}{right)}$

and

${displaystyle {frac {1}{phi }}}=-sum _{k=1^{infty }{frac {mu (k)}{k}}log left(1-{frac {1}{phi ^{k}}}}{right). !$

If they are subtracted, you get

${displaystyle sum _{k=1}^{infty }{frac {mu (k)-varphi (k)}{k}}{k}{log left(1-{frac {1}{phi ^{k}}}}}{right)=1. !$

Applying the exponential function to both sides of the above identity produces an infinite product formula linked to e:

${displaystyle e=prod _{k=1}^{infty }left(1-{frac {1}{phi ^{k}}}}}{right)!^{frac {mu (k)-varphi (k)}{k}}}}{. !$

The proof is based on the following two formulas

${displaystyle {begin{aligned}sum _{k=1}{infty }{frac {varphi}{k}{k}}{left(-log left(1-x^{k}{k}{ right)}{fracd}{1-x}{ft$

Generating functions

The Dirichlet series for φ(n) can be written in terms of the Riemann zeta function as:

${displaystyle sum _{n=1}^{infty }{frac {varphi(n)}{n^{s}}}}{frac {zeta (s-1)}{zeta (s)}}}}$

where the left side converges ${displaystyle Re spur2}$.

The generating function of the Lambert series is

${displaystyle sum _{n=1}^{infty }{frac {varphi(n)q^{n}}{1-q^{n}}}}{frac {q}{(1-q)^{2}}}}}}$

which converges for | q | < 1.

Both formulas are proved by manipulations of elementary series and the formulas for φ(n).

Growth rate

In the words of Hardy & Wright, the order of φ(n) is "almost always n»".

First

${displaystyle lim sup {frac {varphi(n)}{n}}}=1,}$

but since n tends to infinity, for all δ > 0

${displaystyle {frac {varphi(n)}{n^{1-delta}}rightarrow infty. !$

These two formulas can be proved using little more than the formulas for φ(n) and the function sum σ(n) divisors.

In fact, during the proof of the second formula, the inequality

${displaystyle {frac {6}{pi ^{2}}}}}}{frac {varphi(n)sigma}{n^{2}}}}}{excluding}}}}}{n,}}$

true for n > 1, is proven.

You also have to

${displaystyle lim inf {frac {varphi}{n}}}}log log n=e^{-gamma }.}$

Here γ is Euler's constant, γ = 0.577215665..., so e^γ = 1.7810724... and e^−γ = 0.56145948....

Proving this does not require the Prime Number Theorem at all. Since log log n tends to infinity, this formula shows that

${displaystyle lim inf {frac {varphi}{n}}}=0. !$

And indeed, more properties are checked, such as

${displaystyle varphi (n) supposed{frac {n}{e^{gamma };log log n+{frac {3}{log log n}}}}}}}}{quad {text{ for }}n literal2}$

and

${displaystyle varphi (n) implied{frac {n}{e^{gamma}log log n}}quad {text{ for infinitely many}n. !$

The second inequality was proved by Jean-Louis Nicolas. Ribenboim noted that: "The proof method is interesting, since the inequality is shown first under the assumption that the Riemann hypothesis is true, and then under the opposite assumption".

For the average order, one has to

${displaystyle varphi (1)+varphi (2)+cdots +varphi (n)={frac {3n^{2}}{pi ^{2}}}+Oleft(n(log n)^{frac}{2}{3}{3}{log n)^{frac {4ft}{right}{text}{quad}$

This result, due to Arnold Walfisz, was proved by exploiting the estimates on exponential sums due to I. M. Vinogradov and N. M. Korobov.

Using a combination of the methods of van der Corput and Vinogradov, H.-Q. Liu (On the Euler function. Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) improved the error term to

${displaystyle Oleft(n(log n)^{frac {2}{3}{3}(log log n)^{frac {1}{3}}{3}}}right)}}$

(this is currently the best known estimate of this type). The "Big O" represents a quantity that is bounded by a constant multiplied by the function of n inside the parentheses (which is small compared to < span class="texhtml">n²).

This result can be used to show that the probability that two randomly chosen numbers are relatively prime is 6/π².

Relation between consecutive values

In 1950, Somayajulu proved that

${displaystyle {begin{aligned}lim inf {frac {varphi (n+1)}{varphi (n)}}}{quad {text{y}}[5px]lim sup {frac {varphi(n+1)}{varphi (n)}{varphi}}{infty.$

In 1954 Schinzel and Sierpiński strengthened this proposition, proving that the set

${displaystyle left{frac {varphi(n+1)}{varphi(n)}}}},;n=1,2,ldots right}}}$

is dense in the positive real numbers. They also proved that the set

${displaystyle left{frac {varphi(n)}{n}}}},;n=1,2,ldots right}}}$

is dense on the interval (0,1).

Totient numbers

A totient number is a value of the Euler totient function: that is, an m for which there is at least one n for which φ(n) = m. The valence or multiplicity of a totient number m is the number of solutions of this equation. A non-bearing number is a natural number that is not a bearing number. Every odd integer that exceeds 1 is trivially a non-counting number. There is also an infinite number of even non-totents, and, in fact, every positive integer has a multiple that is an even non-totent.

The number of numbers up to a given limit x is

${displaystyle {frac {x}{log x}}}e^{{{big (}C+o(1){big)}(log log x)^{2}}}}}}}$

for a constant C = 0.8178146....

If counted according to their multiplicity, the number of counting numbers up to a given limit x is

${displaystyle {Big vert }{n:varphi (n)leq x}{Big vert }={frac {zeta (2)zeta (3)}{zeta (6)}}{cdot x+R(x)}}$

where the error term R is of order at most < span class="sfrac nowrap" style="display:inline-block; vertical-align:-0.5em; font-size:85%; text-align:center">x/(log x)^k for any positive k.

It is known that the multiplicity of m exceeds m^δ infinitely often for any δ < 0.55655.

Ford's Theorem

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

However, there is no known number m with multiplicity k = 1. The Carmichael totient function conjecture is the statement that there is no such thing as m.

Perfect Tontient Numbers

The perfect totients are those that are equal to the sum of their successive totients. There is a family of these numbers related to the powers of three, as well as the products of these powers by some prime numbers.

Applications

Cyclotomy

In the last section of the Disquisitions, Gauss proved that a n-regular agon can be constructed with rule and time signature if φ(n) is a power of 2. If n is a power of an odd prime number, the formula for totient says that its totient can be a power of two only if n is a prime power and n − 1 is a power of 2. Prime numbers that are one more than a power of 2 are called Fermat prime numbers and only five are known: 3, 5, 17, 257 and 65537. Fermat and Gauss knew this data, and subsequently no one has been able to verify if there are more than these numbers.

Therefore, 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 n are

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... (A003401 Succession in OEIS).

Prime number theorem for arithmetic progressions

The RSA Cryptosystem

Setting up an RSA system involves choosing two large primes p and q, calculate n = pq and k = φ(n) and find two numbers e and d such that ed ≡ 1 (mod k). The numbers n and e (the "encryption key") are disclosed to the public and d (the "encryption key of decryption") is kept private.

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

And it is deciphered by calculating t = S^d (mod < i>n). Euler's theorem can be used to show that if 0 < t < n, so t = m.

The security of an RSA system would be compromised if the number n could be factored efficiently or if φ(n) could be computed efficiently without factoring n< /span>.

Unresolved issues

Lehmer's conjecture

If p is prime, then φ(< i>p) = p − 1. In 1932 Derrick Henry Lehmer raised the question of whether there is any composite number n such that φ(n) divides n − 1. None known.

In 1933 he proved that if there exists such a n, it must be odd, without squares, and divisible by at least seven prime numbers (that is, ω(n) ≥ 7). In 1980 Cohen and Hagis proved that n > 10²⁰ and that ω(n) ≥ 14. In addition, Hagis proved that if 3 divides n, then n > 10^1937042 and ω(n) ≥ 298848.

Carmichael's Conjecture

This statement states that there is no number n with the property that for all other numbers m, m ≠ n, φ(m) ≠ φ(n). See Ford's theorem above.

As stated in the main article, if there is a single counterexample to this conjecture, there must be an infinite number of counterexamples, with the smallest having at least ten billion base-10 digits.

Riemann Hypothesis

The Riemann hypothesis is true if and only if the inequality

${displaystyle {frac {n}{varphi (n)}}}{gamma }{log log n+{frac {e^{gamma }(4+gamma -log 4pi)}{sqrt {log n}}}}}}}{$

is true for all n ≥ p₁₂₀₅₆₉#, where γ is the Euler-Mascheroni constant and p_{120569< /sub>#} is the product of the first 120569 prime numbers.