# Totient function

## Definitions

Symbol: Totient $\varphi(n)$ Euler totient function

## Tables

Table of $\varphi(n)$ for $0 \le n \le 100$

## Counting

$\varphi(n) = \# \left\{ k : k \in \{1, 2, \ldots, n\} \,\mathbin{\operatorname{and}}\, \gcd\!\left(n, k\right) = 1 \right\}$

## Factorization

$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$
$\varphi\!\left({2}^{n}\right) = {2}^{n - 1}$
$\varphi(p) = p - 1$
$\varphi\!\left({p}^{k}\right) = {p}^{k - 1} \left(p - 1\right)$
$\left(\gcd\!\left(m, n\right) = 1\right) \;\implies\; \left(\varphi\!\left(m n\right) = \varphi(m) \varphi(n)\right)$
$\varphi\!\left(m n\right) = \frac{\varphi(m) \varphi(n) \gcd\!\left(m, n\right)}{\varphi\!\left(\gcd\!\left(m, n\right)\right)}$
$\varphi\!\left({m}^{n}\right) = {m}^{n - 1} \varphi(m)$
$\varphi\!\left(2 n\right) = \begin{cases} 2 \varphi(n), & n \text{ even}\\\varphi(n), & n \text{ odd}\\ \end{cases}$
$\varphi\!\left(\prod_{k=1}^{m} p_{k}^{{e}_{k}}\right) = \prod_{k=1}^{m} \varphi\!\left(p_{k}^{{e}_{k}}\right)$
$\varphi\!\left(\operatorname{lcm}\!\left(m, n\right)\right) \varphi\!\left(\gcd\!\left(m, n\right)\right) = \varphi(m) \varphi(n)$
$\varphi\!\left(-n\right) = \varphi(n)$

## Divisibility

$\begin{cases} \varphi(n) \text{ odd}, & n \in \left\{1, 2\right\}\\\varphi(n) \text{ even}, & \text{otherwise}\\ \end{cases}$
$\left(m \mid n\right) \;\implies\; \left(\varphi(m) \mid \varphi(n)\right)$
$n \mid \varphi\!\left({m}^{n} - 1\right)$

### Euler-Fermat theorem

${a}^{\varphi(n)} \equiv 1 \pmod {n}$
$\left(x \equiv y \pmod {\varphi(n)}\right) \;\implies\; \left({a}^{x} \equiv {a}^{y} \pmod {n}\right)$

## Sum representations

$\varphi(n) = \sum_{k=1}^{n} \gcd\!\left(n, k\right) {e}^{2 \pi i k / n}$
$\varphi(n) = \sum_{k=1}^{n} \gcd\!\left(n, k\right) \cos\!\left(\frac{2 \pi k}{n}\right)$
$\varphi(n) = \sum_{d \mid n} \mu(d) \frac{n}{d}$
$\varphi(n) = \sum_{k=1}^{n} \begin{cases} 1, & \gcd\!\left(n, k\right) = 1\\0, & \text{otherwise}\\ \end{cases}$
$\varphi(n) = \frac{2}{n} \sum_{k=1}^{n} \begin{cases} k, & \gcd\!\left(n, k\right) = 1\\0, & \text{otherwise}\\ \end{cases}$
$\varphi(n) \sigma_{0}\!\left(n\right) = \sum_{k=1}^{n} \begin{cases} \gcd\!\left(n, k - 1\right), & \gcd\!\left(n, k\right) = 1\\0, & \text{otherwise}\\ \end{cases}$
$\varphi(n) = n - \sum_{d \mid n,\, d < n} \varphi(d)$

## Summation

$\sum_{d \mid n} \varphi(d) = n$
$\sum_{d \mid n} \varphi(d) d = \left(\frac{2}{n} \sum_{k=1}^{n} \operatorname{lcm}\!\left(n, k\right)\right) - 1$
$\sum_{d \mid n} \varphi(d) \frac{n}{d} = \sum_{k=1}^{n} \gcd\!\left(n, k\right)$
$\sum_{d \mid n} \varphi(d) \sigma_{k}\!\left(\frac{n}{d}\right) = n \sigma_{k - 1}\!\left(n\right)$
$\sum_{k=1}^{n} \varphi(k) \left\lfloor \frac{n}{k} \right\rfloor = \frac{n \left(n + 1\right)}{2}$

## Generating functions

$\sum_{n=1}^{\infty} \frac{\varphi(n)}{{n}^{s}} = \frac{\zeta\!\left(s - 1\right)}{\zeta\!\left(s\right)}$
$\sum_{n=1}^{\infty} \frac{\varphi(n) {q}^{n}}{1 - {q}^{n}} = \frac{q}{{\left(1 - q\right)}^{2}}$
$\sum_{n=1}^{\infty} \frac{\varphi(n)}{n} \log\!\left(1 - {x}^{n}\right) = \frac{x}{x - 1}$

## Asymptotics

$\limsup_{n \to \infty} \frac{\varphi(n)}{n} = 1$
$\liminf_{n \to \infty} \frac{\varphi(n) \log\!\left(\log(n)\right)}{n} = {e}^{-\gamma}$
$\lim_{n \to \infty} \frac{\varphi(n)}{{n}^{1 - \delta}} = \infty$
$\liminf_{n \to \infty} \frac{\varphi\!\left(n + 1\right)}{\varphi(n)} = 0$
$\limsup_{n \to \infty} \frac{\varphi\!\left(n + 1\right)}{\varphi(n)} = \infty$
$\lim_{N \to \infty} \frac{1}{{N}^{2}} \sum_{n=1}^{N} \varphi(n) = \frac{3}{{\pi}^{2}}$
$\lim_{N \to \infty} \frac{1}{\log(N)} \sum_{n=1}^{N} \frac{1}{\varphi(n)} = \frac{\zeta\!\left(2\right) \zeta\!\left(3\right)}{\zeta\!\left(6\right)}$

## Bounds and inequalities

$\varphi(n) \le n$
$\varphi(n) \le n - 1$
$\varphi(n) \ge \sqrt{n}$
$\left(n \notin \mathbb{P}\right) \;\implies\; \left(\varphi(n) \le n - \sqrt{n}\right)$
$\varphi\!\left(m n\right) \le m \varphi(n)$
$\varphi(m) \varphi(n) \le \varphi\!\left(m n\right)$
$\varphi(n) > \frac{n}{{e}^{\gamma} \log\!\left(\log(n)\right) + \frac{2.50637}{\log\!\left(\log(n)\right)}}$
$\# \left\{ n : n \in \mathbb{Z}_{\ge 1} \,\mathbin{\operatorname{and}}\, \varphi(n) < \frac{n}{{e}^{\gamma} \log\!\left(\log(n)\right)} \right\}$
$\varphi(n) \sigma_{1}\!\left(n\right) < {n}^{2}$
$\varphi(n) \sigma_{1}\!\left(n\right) > \frac{6}{{\pi}^{2}} {n}^{2}$

Copyright (C) Fredrik Johansson and contributors. Fungrim is provided under the MIT license. The source code is on GitHub.

2021-03-15 19:12:00.328586 UTC