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 0n1000 \le n \le 100

Counting

c19cd6
φ(n)=#{k:k{1,2,,n}andgcd ⁣(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)=npn(11p)\varphi(n) = 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(p) = 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(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)=mn1φ(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)=0\varphi\!\left(-n\right) = 0

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
(mn)    (φ(m)φ(n))\left(m \mid n\right) \implies \left(\varphi(m) \mid \varphi(n)\right)
8f51dd
nφ ⁣(mn1)n \mid \varphi\!\left({m}^{n} - 1\right)

Euler-Fermat theorem

a68214
aφ(n)1(modn){a}^{\varphi(n)} \equiv 1 \pmod {n}
36fe36
(xy(modφ(n)))    (axay(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)=dnμ(d)nd\varphi(n) = \sum_{d \mid n} \mu(d) \frac{n}{d}
bb4ce0
φ(n)=2nk=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,k1),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)=ndn,d<nφ(d)\varphi(n) = n - \sum_{d \mid n,\, d < n} \varphi(d)

Summation

cdd7e7
dnφ(d)=n\sum_{d \mid n} \varphi(d) = n
90bb4a
dnφ(d)d=(2nk=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
dnφ(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
dnφ(d)σk ⁣(nd)=nσk1 ⁣(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=ζ ⁣(s1)ζ(s)\sum_{n=1}^{\infty} \frac{\varphi(n)}{{n}^{s}} = \frac{\zeta\!\left(s - 1\right)}{\zeta(s)}
7f5468
n=1φ(n)qn1qn=q(1q)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 ⁣(1xn)=xx1\sum_{n=1}^{\infty} \frac{\varphi(n)}{n} \log\!\left(1 - {x}^{n}\right) = \frac{x}{x - 1}

Asymptotics

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

Bounds and inequalities

e3005f
φ(n)n\varphi(n) \le n
485ab6
φ(n)n1\varphi(n) \le n - 1
d0b5a7
φ(n)n\varphi(n) \ge \sqrt{n}
b81b45
(nP)    (φ(n)nn)\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:nZ1andφ(n)<neγlog ⁣(log(n))}=#Z\# \left\{ n : n \in \mathbb{Z}_{\ge 1} \,\mathbin{\operatorname{and}}\, \varphi(n) < \frac{n}{{e}^{\gamma} \log\!\left(\log(n)\right)} \right\} = \# \mathbb{Z}
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.

2019-10-05 13:11:19.856591 UTC