Fungrim home page

Totient function

Table of contents: Definitions - Tables - Counting - Factorization - Divisibility - Sum representations - Summation - Generating functions - Asymptotics - Bounds and inequalities

Definitions

2c46dc
Symbol: Totient φ ⁣(n)\varphi\!\left(n\right) Euler totient function

Tables

6d37c9
Table of φ ⁣(n)\varphi\!\left(n\right) for 0n1000 \le n \le 100

Counting

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

Factorization

b9c50f
φ ⁣(n)=npn(11p)\varphi\!\left(n\right) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)
081abd
φ ⁣(2n)=2n1\varphi\!\left({2}^{n}\right) = {2}^{n - 1}
cb410e
φ ⁣(p)=p1\varphi\!\left(p\right) = p - 1
1d731f
φ ⁣(pk)=pk1(p1)\varphi\!\left({p}^{k}\right) = {p}^{k - 1} \left(p - 1\right)
db4763
(gcd ⁣(m,n)=1)    (φ ⁣(mn)=φ ⁣(m)φ ⁣(n))\left(\gcd\!\left(m, n\right) = 1\right) \implies \left(\varphi\!\left(m n\right) = \varphi\!\left(m\right) \varphi\!\left(n\right)\right)
56d7fe
φ ⁣(mn)=φ ⁣(m)φ ⁣(n)gcd ⁣(m,n)φ ⁣(gcd ⁣(m,n))\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)}
05e9ae
φ ⁣(mn)=mn1φ ⁣(m)\varphi\!\left({m}^{n}\right) = {m}^{n - 1} \varphi\!\left(m\right)
c0e088
φ ⁣(2n)={2φ ⁣(n),n evenφ ⁣(n),n odd\varphi\!\left(2 n\right) = \begin{cases} 2 \varphi\!\left(n\right), & n \text{ even}\\\varphi\!\left(n\right), & n \text{ odd}\\ \end{cases}
b9c36d
φ ⁣(k=1mpkek)=k=1mφ ⁣(pkek)\varphi\!\left(\prod_{k=1}^{m} {p_{k}}^{{e}_{k}}\right) = \prod_{k=1}^{m} \varphi\!\left({p_{k}}^{{e}_{k}}\right)
d1ea57
φ ⁣(lcm ⁣(m,n))φ ⁣(gcd ⁣(m,n))=φ ⁣(m)φ ⁣(n)\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)
11a56b
φ ⁣(n)=0\varphi\!\left(-n\right) = 0

Divisibility

f0639c
{φ ⁣(n) odd,n{1,2}φ ⁣(n) even,otherwise\begin{cases} \varphi\!\left(n\right) \text{ odd}, & n \in \left\{1, 2\right\}\\\varphi\!\left(n\right) \text{ even}, & \text{otherwise}\\ \end{cases}
eae0de
(mn)    (φ ⁣(m)φ ⁣(n))\left(m \mid n\right) \implies \left(\varphi\!\left(m\right) \mid \varphi\!\left(n\right)\right)
8f51dd
nφ ⁣(mn1)n \mid \varphi\!\left({m}^{n} - 1\right)

Euler-Fermat theorem

a68214
aφ(n)1(modn){a}^{\varphi\left(n\right)} \equiv 1 \pmod {n}
36fe36
(xy(modφ ⁣(n)))    (axay(modn))\left(x \equiv y \pmod {\varphi\!\left(n\right)}\right) \implies \left({a}^{x} \equiv {a}^{y} \pmod {n}\right)

Sum representations

3f5711
φ ⁣(n)=k=1ngcd ⁣(n,k)e2πik/n\varphi\!\left(n\right) = \sum_{k=1}^{n} \gcd\!\left(n, k\right) {e}^{2 \pi i k / n}
93a877
φ ⁣(n)=k=1ngcd ⁣(n,k)cos ⁣(2πkn)\varphi\!\left(n\right) = \sum_{k=1}^{n} \gcd\!\left(n, k\right) \cos\!\left(\frac{2 \pi k}{n}\right)
efd378
φ ⁣(n)=dnμ ⁣(d)nd\varphi\!\left(n\right) = \sum_{d \mid n} \mu\!\left(d\right) \frac{n}{d}
bb4ce0
φ ⁣(n)=2nk=1n{k,gcd ⁣(n,k)=10,otherwise\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}
a08583
φ ⁣(n)σ0 ⁣(n)=k=1n{gcd ⁣(n,k1),gcd ⁣(n,k)=10,otherwise\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}
08ff0b
φ ⁣(n)=ndn,d<nφ ⁣(d)\varphi\!\left(n\right) = n - \sum_{d \mid n,\, d < n} \varphi\!\left(d\right)

Summation

cdd7e7
dnφ ⁣(d)=n\sum_{d \mid n} \varphi\!\left(d\right) = n
90bb4a
dnφ ⁣(d)d=(2nk=1nlcm ⁣(n,k))1\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
0fdb94
dnφ ⁣(d)nd=k=1ngcd ⁣(n,k)\sum_{d \mid n} \varphi\!\left(d\right) \frac{n}{d} = \sum_{k=1}^{n} \gcd\!\left(n, k\right)
a05466
dnφ ⁣(d)σk ⁣(nd)=nσk1 ⁣(n)\sum_{d \mid n} \varphi\!\left(d\right) \sigma_{k}\!\left(\frac{n}{d}\right) = n \sigma_{k - 1}\!\left(n\right)
ea27a7
k=1nφ ⁣(k)nk=n(n+1)2\sum_{k=1}^{n} \varphi\!\left(k\right) \left\lfloor \frac{n}{k} \right\rfloor = \frac{n \left(n + 1\right)}{2}

Generating functions

1a907e
n=1φ ⁣(n)ns=ζ ⁣(s1)ζ ⁣(s)\sum_{n=1}^{\infty} \frac{\varphi\!\left(n\right)}{{n}^{s}} = \frac{\zeta\!\left(s - 1\right)}{\zeta\!\left(s\right)}
7f5468
n=1φ ⁣(n)qn1qn=q(1q)2\sum_{n=1}^{\infty} \frac{\varphi\!\left(n\right) {q}^{n}}{1 - {q}^{n}} = \frac{q}{{\left(1 - q\right)}^{2}}
a9a405
n=1φ ⁣(n)nlog ⁣(1xn)=xx1\sum_{n=1}^{\infty} \frac{\varphi\!\left(n\right)}{n} \log\!\left(1 - {x}^{n}\right) = \frac{x}{x - 1}

Asymptotics

cd7877
lim supnφ ⁣(n)n=1\limsup_{n \to \infty} \frac{\varphi\!\left(n\right)}{n} = 1
acfc1f
lim infnφ ⁣(n)log ⁣(log ⁣(n))n=eγ\liminf_{n \to \infty} \frac{\varphi\!\left(n\right) \log\!\left(\log\!\left(n\right)\right)}{n} = {e}^{-\gamma}
4b5b44
limnφ ⁣(n)n1δ=\lim_{n \to \infty} \frac{\varphi\!\left(n\right)}{{n}^{1 - \delta}} = \infty
33139b
lim infnφ ⁣(n+1)φ ⁣(n)=0\liminf_{n \to \infty} \frac{\varphi\!\left(n + 1\right)}{\varphi\!\left(n\right)} = 0
feb1a0
lim supnφ ⁣(n+1)φ ⁣(n)=\limsup_{n \to \infty} \frac{\varphi\!\left(n + 1\right)}{\varphi\!\left(n\right)} = \infty
8d7b3d
limN1N2n=1Nφ ⁣(n)=3π2\lim_{N \to \infty} \frac{1}{{N}^{2}} \sum_{n=1}^{N} \varphi\!\left(n\right) = \frac{3}{{\pi}^{2}}
9923b7
limN1log ⁣(N)n=1N1φ ⁣(n)=ζ ⁣(2)ζ ⁣(3)ζ ⁣(6)\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

e3005f
φ ⁣(n)n\varphi\!\left(n\right) \le n
485ab6
φ ⁣(n)n1\varphi\!\left(n\right) \le n - 1
d0b5a7
φ ⁣(n)n\varphi\!\left(n\right) \ge \sqrt{n}
b81b45
(nP)    (φ ⁣(n)nn)\left(n \notin \mathbb{P}\right) \implies \left(\varphi\!\left(n\right) \le n - \sqrt{n}\right)
08fb81
φ ⁣(mn)mφ ⁣(n)\varphi\!\left(m n\right) \le m \varphi\!\left(n\right)
775e10
φ ⁣(m)φ ⁣(n)φ ⁣(mn)\varphi\!\left(m\right) \varphi\!\left(n\right) \le \varphi\!\left(m n\right)
433a5c
φ ⁣(n)>neγlog ⁣(log ⁣(n))+2.50637log ⁣(log ⁣(n))\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)}}
86fcf1
#{n:nZ1andφ ⁣(n)<neγlog ⁣(log ⁣(n))}=#Z\# \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}
acb28a
φ ⁣(n)σ1 ⁣(n)<n2\varphi\!\left(n\right) \sigma_{1}\!\left(n\right) < {n}^{2}
0477b3
φ ⁣(n)σ1 ⁣(n)>6π2n2\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