Euler totient function ($\phi (n)$)

Euler's totient function is the arithmetic functionIt counts the congruence classes modulo $n$ represented by integers coprime to $n$. In particular, $\phi (1)=1$, since $\gcd (1,1)=1$. For $12$, the coprime integers among $1,\dots ,12$ are $1,5,7,11$, so $\phi (12)=4$; they form a reduced residue system. ^[ref]

Counting these congruence classes is useful because they are exactly the classes with modular multiplicative inverses. Their number supplies the exponent in Euler theorem. Möbius inversion gives the product formulawhere $p$ runs over distinct prime factors of $n$. Thus $\phi (p^a)=p^{a-1}(p-1)$ for prime powers with $a\ge 1$, and $\phi (12)=12(1-1/2)(1-1/3)=4$. The product for $n=1$ is an empty product, so it gives the same convention $\phi (1)=1$.

The prime-power formula and multiplicativity of Euler's totient function imply $\varphi (mn)\varphi (\gcd (m,n))=\varphi (m)\varphi (n)\gcd (m,n)$. For a prime with positive exponents $a,b$ in the inputs, both local products equal $p^{a+b+\min (a,b)-2}(p-1{)}^2$. If one exponent is zero, the equality is immediate from $\varphi (1)=1$.

The totient divisor-sum identity and multiplication of absolutely convergent Dirichlet series give the quotient for $\mathrm{Re}s>2$. The bound $\varphi (n)\le n$ proves convergence there. The simple pole of the Riemann zeta function at one makes the quotient unbounded as real $s\downarrow 2$. Since the coefficients are nonnegative, convergence at two would bound all these larger-real-part values, a contradiction. Thus the abscissa of absolute convergence of a Dirichlet series is two.

Given a positive integer $m$, find all positive integers $n$ satisfying $\phi (n)=m$. For every prime divisor $p$ of a solution, $p-1$ divides $m$, so the possible primes lie in the finite set $\{d+1:d\mid m,d+1\text{ is prime}\}$. Search can then combine the prime powers whose totient contributions multiply to $m$.

The summatory totient function is $\Phi (x)={\sum }_{n\le x}\phi (n)$. It counts the coprime ordered pairs $(a,b)$ with $1\le a\le b\le x$. The identity ${\sum }_{d\mid n}\phi (d)=n$ yields ${\sum }_{j=1}^x\Phi (\lfloor x/j\rfloor )=x(x+1)/2$ for a positive integer $x$.

A smoothed form of the summatory totient function satisfiesUse the Dirichlet series $\zeta (s-1)/\zeta (s)$ and the kernel $x^s/[s(s+1)]$ to write the left side as a vertical contour integral. Move the line from real part greater than two to $3/2$. The only crossed pole is at two, with residue $x^3/(6\zeta (2))=x^3/{\pi }^2$; the remaining vertical integral is $O(x^{5/2})$ by the standard zeta bounds in the half-strip. If $A(x)={\sum }_{n\le x}\phi (n)$ and $S(x)={\int }_0^{x}A(t)dt$, positivity of the summands makes $A$ nondecreasing. The backward and forward difference quotients of $S$ bound $A(x)$. Insert $S(x)\sim x^3/{\pi }^2$, then let the relative difference-quotient step tend to zero, proving the displayed asymptotic. This monotone integral Tauberian lemma justifies the passage from a smoothed estimate to an unsmoothed one.

For an integer $n>1$, define $C(n)=(n-\phi (n))/(n-1)$, the complementary proportion to the resilience of a denominator. For composite numbers, asking when this is a unit fraction is equivalent to the divisibility condition $n-\phi (n)\mid n-1$.

For an integer $d>1$, the proportion of proper fractions $1/d,\dots ,(d-1)/d$ already in lowest terms. There are $\phi (d)$ such fractions, so $R(d)=\phi (d)/(d-1)$. The prime factorization of $d$ gives $R(d)=\frac{d}{d-1}{\prod }_{p\mid d}(1-1/p)$.

The sequence $n,\phi (n),\phi (\phi (n)),\dots ,1$ obtained by iterating Euler's totient function on a positive integer. Since $1\le \phi (n)<n$ for $n>1$, the sequence reaches 1. Counting both endpoints gives the length recurrence relation $L(1)=1$ and $L(n)=1+L(\phi (n))$; increasing order of $n$ therefore suffices for dynamic programming.

The divisor sum of Euler's totient function is the identity arithmetic function:Equivalently, $\phi \ast 1=\mathrm{id}$ under Dirichlet convolution, with $1$ the constant-one arithmetic function. ^[ref]

To see why, group the integers $j=1,\dots ,n$ by $h=\gcd (j,n)$. Each $h$ is a positive integer divisor of $n$. Within its group, $j=ha$ with $1\le a\le n/h$ and $\gcd (a,n/h)=1$, by the scaling identity for greatest common divisors. Dividing by $h$ gives a bijection with the integers counted by $\phi (n/h)$. The groups form a partition of a set, soFor $n=12$, the groups with greatest common divisor $h=1,2,3,4,6,12$ are respectively $\{1,5,7,11\},\{2,10\},\{3,9\},\{4,8\},\{6\},\{12\}$. Their sizes are $4,2,2,2,1,1$, totaling $12$. Möbius inversion reverses this divisor sum to recover Euler's totient function from $g(n)=n$.

The map $j\mapsto n-j$ is a bijection of the integers between one and $n-1$ that are coprime to $n$. If their sum is $S$, this bijection gives $S=n\phi (n)-S$, so $S=n\phi (n)/2$. This works even at $n=2$, where the single residue is fixed. The same identity follows from the weighted inclusion-exclusion principle by excluding multiples of the prime factors of $n$.

If $n>1$ is odd, its Euler totient function is even and cannot divide $n$. Otherwise write $n=2^c{\prod }_{j=1}^r{p}_j^{a_j}$ with odd primes $p_j$ and $c\ge 1$. Comparing powers of two in $\phi (n)\mid n$ gives ${\sum }_j{v}_2(p_j-1)\le 1$. Thus there is at most one odd prime $p$, with $v_2(p-1)=1$. Since $p-1$ divides $\phi (n)$, it divides $n$, and is coprime to $p$; with only the prime factors $2,p$ available it must be a power of two. Hence $p-1=2$ and $p=3$. Conversely, for $c\ge 1$ the prime-power totient formula verifies divisibility for $2^c{3}^d$, and $n=1$ is immediate.

Write $n=\prod p^{a_p}$ and $d=\prod p^{b_p}$, with $0\le b_p\le a_p$. The prime-power formula for the Euler totient function gives an integer contribution to $\phi (n)/\phi (d)$ from each prime: it is $p^{a_p-b_p}$ when $b_p>0$, and $p^{a_p-1}(p-1)$ when $b_p=0<a_p$. Multiplying proves the divisibility assertion, including $d=1$ with $\phi (1)=1$.

For $n\ge 3$, this explicit lower bound on the Euler totient function implies $\phi (n)/n=\Omega (1/\log \log n)$ as $n\to \infty$. Here ${\gamma }_E$ is the Euler--Mascheroni constant. The prime-product formula also gives $\phi (r)/r\ge \phi (N)/N$ whenever $r\mid N$, making the bound useful for certified quantum period finding. The relevant statement is a lower bound: the claimed universal upper estimate $\phi (n)=O(n/\log \log n)$ would fail at primes. Equations (3.41)–(3.42) of Theorem 15 provide the primary bound: denisevellachemla.eu/Rosser-Schoenfeld-1962.pdf .

List the $k$ distinct prime divisors of $r$ in increasing order. The $j$th is at least $j+1$, and $k\le {\log }_{2}r$. The Euler totient function product formula gives $\phi (r)/r\ge {\prod }_{j=1}^{k}j/(j+1)=1/(k+1)$. This elementary bound is sufficient to show inverse-polynomial success probability for coprime phase labels in quantum order finding.

If a is coprime to n, then a raised to the power phi(n) is congruent to one modulo n.

Multiplication by a unit $a$ permutes the reduced residue classes modulo $n$. Multiplying all classes before and after this permutation and cancelling their unit product proves $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$.

For coprime positive integers m and n, the Chinese remainder theorem gives phi(mn)=phi(m)phi(n).

For each positive integer $k$, only finitely many $n$ satisfy $\phi (n)=k$. Indeed, every prime $p\mid n$ has $p-1\mid k$, and the exponent of $p$ in $n$ is bounded because $p^{a-1}\mid k$.