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

Euler’s totient function counts residue classes modulo n that are coprime to n.

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