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(n) — Euler totient function

Tables

6d37c9
Table of φ(n)\varphi(n) for 0≤n≤1000 \le n \le 100

Counting

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

Factorization

b9c50f
φ(n)=n∏p∣n(1−1p)\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)
081abd
φ ⁣(2n)=2n−1\varphi\!\left({2}^{n}\right) = {2}^{n - 1}
cb410e
φ(p)=p−1\varphi(p) = p - 1
1d731f
φ ⁣(pk)=pk−1(p−1)\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(m) \varphi(n)\right)
56d7fe
φ ⁣(mn)=φ(m)φ(n)gcd⁡ ⁣(m,n)φ ⁣(gcd⁡ ⁣(m,n))\varphi\!\left(m n\right) = \frac{\varphi(m) \varphi(n) \gcd\!\left(m, n\right)}{\varphi\!\left(\gcd\!\left(m, n\right)\right)}
05e9ae
φ ⁣(mn)=mn−1φ(m)\varphi\!\left({m}^{n}\right) = {m}^{n - 1} \varphi(m)
c0e088
φ ⁣(2n)={2φ(n),n evenφ(n),n odd\varphi\!\left(2 n\right) = \begin{cases} 2 \varphi(n), & n \text{ even}\\\varphi(n), & 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(m) \varphi(n)
11a56b
φ ⁣(−n)=φ(n)\varphi\!\left(-n\right) = \varphi(n)

Divisibility

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

Euler-Fermat theorem

a68214
aφ(n)≡1(modn){a}^{\varphi(n)} \equiv 1 \pmod {n}
36fe36
(x≡y(modφ(n)))    ⟹    (ax≡ay(modn))\left(x \equiv y \pmod {\varphi(n)}\right) \;\implies\; \left({a}^{x} \equiv {a}^{y} \pmod {n}\right)

Sum representations

3f5711
φ(n)=∑k=1ngcd⁡ ⁣(n,k)e2πik/n\varphi(n) = \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(n) = \sum_{k=1}^{n} \gcd\!\left(n, k\right) \cos\!\left(\frac{2 \pi k}{n}\right)
efd378
φ(n)=∑d∣nμ(d)nd\varphi(n) = \sum_{d \mid n} \mu(d) \frac{n}{d}
91f156
φ(n)=∑k=1n{1,gcd⁡ ⁣(n,k)=10,otherwise\varphi(n) = \sum_{k=1}^{n} \begin{cases} 1, & \gcd\!\left(n, k\right) = 1\\0, & \text{otherwise}\\ \end{cases}
bb4ce0
φ(n)=2n∑k=1n{k,gcd⁡ ⁣(n,k)=10,otherwise\varphi(n) = \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,k−1),gcd⁡ ⁣(n,k)=10,otherwise\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}
08ff0b
φ(n)=n−∑d∣n, d<nφ(d)\varphi(n) = n - \sum_{d \mid n,\, d < n} \varphi(d)

Summation

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

Generating functions

1a907e
∑n=1∞φ(n)ns=ζ ⁣(s−1)ζ ⁣(s)\sum_{n=1}^{\infty} \frac{\varphi(n)}{{n}^{s}} = \frac{\zeta\!\left(s - 1\right)}{\zeta\!\left(s\right)}
7f5468
∑n=1∞φ(n)qn1−qn=q(1−q)2\sum_{n=1}^{\infty} \frac{\varphi(n) {q}^{n}}{1 - {q}^{n}} = \frac{q}{{\left(1 - q\right)}^{2}}
a9a405
∑n=1∞φ(n)nlog⁡ ⁣(1−xn)=xx−1\sum_{n=1}^{\infty} \frac{\varphi(n)}{n} \log\!\left(1 - {x}^{n}\right) = \frac{x}{x - 1}

Asymptotics

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

e3005f
φ(n)≤n\varphi(n) \le n
485ab6
φ(n)≤n−1\varphi(n) \le n - 1
d0b5a7
φ(n)≥n\varphi(n) \ge \sqrt{n}
b81b45
(n∉P)    ⟹    (φ(n)≤n−n)\left(n \notin \mathbb{P}\right) \;\implies\; \left(\varphi(n) \le n - \sqrt{n}\right)
08fb81
φ ⁣(mn)≤mφ(n)\varphi\!\left(m n\right) \le m \varphi(n)
775e10
φ(m)φ(n)≤φ ⁣(mn)\varphi(m) \varphi(n) \le \varphi\!\left(m n\right)
433a5c
φ(n)>neγlog⁡ ⁣(log⁡(n))+2.50637log⁡ ⁣(log⁡(n))\varphi(n) > \frac{n}{{e}^{\gamma} \log\!\left(\log(n)\right) + \frac{2.50637}{\log\!\left(\log(n)\right)}}
86fcf1
#{n:n∈Z≥1 and⁡ φ(n)<neγlog⁡ ⁣(log⁡(n))}\# \left\{ n : n \in \mathbb{Z}_{\ge 1} \,\mathbin{\operatorname{and}}\, \varphi(n) < \frac{n}{{e}^{\gamma} \log\!\left(\log(n)\right)} \right\}
acb28a
φ(n)σ1 ⁣(n)<n2\varphi(n) \sigma_{1}\!\left(n\right) < {n}^{2}
0477b3
φ(n)σ1 ⁣(n)>6π2n2\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