# Totient function

## Definitions

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

## Tables

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

## Counting

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

## Factorization

$\varphi\!\left(n\right) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$
$\varphi\!\left({2}^{n}\right) = {2}^{n - 1}$
$\varphi\!\left(p\right) = 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\!\left(m\right) \varphi\!\left(n\right)\right)$
$\varphi\!\left(m n\right) = \frac{\varphi\!\left(m\right) \varphi\!\left(n\right) \gcd\!\left(m, n\right)}{\varphi\!\left(\gcd\!\left(m, n\right)\right)}$
$\varphi\!\left({m}^{n}\right) = {m}^{n - 1} \varphi\!\left(m\right)$
$\varphi\!\left(2 n\right) = \begin{cases} 2 \varphi\!\left(n\right), & n \text{ even}\\\varphi\!\left(n\right), & 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\!\left(m\right) \varphi\!\left(n\right)$
$\varphi\!\left(-n\right) = 0$

## Divisibility

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

### Euler-Fermat theorem

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

## Sum representations

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

## Summation

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

## Generating functions

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

## Asymptotics

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

## Bounds and inequalities

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

2019-08-21 11:44:15.926409 UTC