Arithmetic function

σ_k(n), τ(n), d(n) – divisor sums

σ_k(n) is the sum of the kth powers of the positive divisors of n, including 1 and n, where k is a complex number.

σ₁(n), the sum of the (positive) divisors of n, is usually denoted by σ(n).

Since a positive number to the zero power is one, σ₀(n) is therefore the number of (positive) divisors of n; it is usually denoted by d(n) or τ(n) (for the German Teiler = divisors).

$${\displaystyle \sigma _{k}(n)=\prod _{i=1}^{\omega (n)}{\frac {p_{i}^{(a_{i}+1)k}-1}{p_{i}^{k}-1}}=\prod _{i=1}^{\omega (n)}\left(1+p_{i}^{k}+p_{i}^{2k}+\cdots +p_{i}^{a_{i}k}\right).}$$

Setting k = 0 in the second product gives $${\displaystyle \tau (n)=d(n)=(1+a_{1})(1+a_{2})\cdots (1+a_{\omega (n)}).}$$

φ(n) – Euler totient function

φ(n) , the Euler totient function, is the number of positive integers not greater than n that are coprime to n.

$${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)=n\left({\frac {p_{1}-1}{p_{1}}}\right)\left({\frac {p_{2}-1}{p_{2}}}\right)\cdots \left({\frac {p_{\omega (n)}-1}{p_{\omega (n)}}}\right).}$$

J_k(n) – Jordan totient function

J_k(n) , the Jordan totient function, is the number of k-tuples of positive integers all less than or equal to n that form a coprime (k + 1)-tuple together with n. It is a generalization of Euler's totient, φ(n) = J₁(n). $${\displaystyle J_{k}(n)=n^{k}\prod _{p\mid n}\left(1-{\frac {1}{p^{k}}}\right)=n^{k}\left({\frac {p_{1}^{k}-1}{p_{1}^{k}}}\right)\left({\frac {p_{2}^{k}-1}{p_{2}^{k}}}\right)\cdots \left({\frac {p_{\omega (n)}^{k}-1}{p_{\omega (n)}^{k}}}\right).}$$

μ(n) – Möbius function

μ(n) , the Möbius function, is important because of the Möbius inversion formula. See Dirichlet convolution, below.

$${\displaystyle \mu (n)={\begin{cases}(-1)^{\omega (n)}=(-1)^{\Omega (n)}&{\text{if }}\;\omega (n)=\Omega (n)\\0&{\text{if }}\;\omega (n)\neq \Omega (n).\end{cases}}}$$

This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.)

τ(n) – Ramanujan tau function

τ(n) , the Ramanujan tau function, is defined by its generating function identity:

$${\displaystyle \sum _{n\geq 1}\tau (n)q^{n}=q\prod _{n\geq 1}(1-q^{n})^{24}.}$$

Although it is hard to say exactly what "arithmetical property of n" it "expresses", ^[7] (τ(n) is (2π)⁻¹² times the nth Fourier coefficient in the q-expansion of the modular discriminant function) ^[8] it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σ_k(n) and r_k(n) functions (because these are also coefficients in the expansion of modular forms).

c_q(n) – Ramanujan's sum

c_q(n) , Ramanujan's sum, is the sum of the nth powers of the primitive qth roots of unity: $${\displaystyle c_{q}(n)=\sum _{\stackrel {1\leq a\leq q}{\gcd(a,q)=1}}e^{2\pi i{\tfrac {a}{q}}n}.}$$

Even though it is defined as a sum of complex numbers (irrational for most values of q), it is an integer. For a fixed value of n it is multiplicative in q:

If q and r are coprime, then ${\displaystyle c_{q}(n)c_{r}(n)=c_{qr}(n).}$

ψ(n) - Dedekind psi function

The Dedekind psi function, used in the theory of modular functions, is defined by the formula $${\displaystyle \psi (n)=n\prod _{p|n}\left(1+{\frac {1}{p}}\right).}$$

λ(n) – Liouville function

λ(n) , the Liouville function, is defined by $${\displaystyle \lambda (n)=(-1)^{\Omega (n)}.}$$

χ(n) – characters

All Dirichlet characters χ(n) are completely multiplicative. Two characters have special notations:

The principal character (mod n) is denoted by χ₀(a) (or χ₁(a)). It is defined as $${\displaystyle \chi _{0}(a)={\begin{cases}1&{\text{if }}\gcd(a,n)=1,\\0&{\text{if }}\gcd(a,n)\neq 1.\end{cases}}}$$

The quadratic character (mod n) is denoted by the Jacobi symbol for odd n (it is not defined for even n): $${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{a_{1}}\left({\frac {a}{p_{2}}}\right)^{a_{2}}\cdots \left({\frac {a}{p_{\omega (n)}}}\right)^{a_{\omega (n)}}.}$$

In this formula ${\displaystyle ({\tfrac {a}{p}})}$ is the Legendre symbol, defined for all integers a and all odd primes p by $${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{if }}a\equiv 0{\pmod {p}},\\+1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x,\;a\equiv x^{2}{\pmod {p}}\\-1&{\text{if there is no such }}x.\end{cases}}}$$

Following the normal convention for the empty product, ${\displaystyle \left({\frac {a}{1}}\right)=1.}$

ω(n) – distinct prime divisors

ω(n), defined above as the number of distinct primes dividing n, is additive (see Prime omega function).

Ω(n) – prime divisors

Ω(n) , defined above as the number of prime factors of n counted with multiplicities, is completely additive (see Prime omega function).

ν_p(n) – p-adic valuation of an integer n

For a fixed prime p, ν_p(n), defined above as the exponent of the largest power of p dividing n, is completely additive.

Logarithmic derivative

${\displaystyle \operatorname {ld} (n)={\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}}$, where ${\displaystyle D(n)}$ is the arithmetic derivative.

π(x), Π(x), ϑ(x), ψ(x) – prime-counting functions

These important functions (which are not arithmetic functions) are defined for non-negative real arguments, and are used in the various statements and proofs of the prime number theorem. They are summation functions (see the main section just below) of arithmetic functions which are neither multiplicative nor additive.

π(x), the prime-counting function, is the number of primes not exceeding x. It is the summation function of the characteristic function of the prime numbers. $${\displaystyle \pi (x)=\sum _{p\leq x}1}$$

A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, etc. It is the summation function of the arithmetic function which takes the value 1/k on integers which are the k-th power of some prime number, and the value 0 on other integers.

$${\displaystyle \Pi (x)=\sum _{p^{k}\leq x}{\frac {1}{k}}.}$$

ϑ(x) and ψ(x), the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding x. $${\displaystyle \vartheta (x)=\sum _{p\leq x}\log p,}$$$${\displaystyle \psi (x)=\sum _{p^{k}\leq x}\log p.}$$

The second Chebyshev function ψ(x) is the summation function of the von Mangoldt function just below.

Λ(n) – von Mangoldt function

Λ(n) , the von Mangoldt function, is 0 unless the argument n is a prime power p^k, in which case it is the natural log of the prime p: $${\displaystyle \Lambda (n)={\begin{cases}\log p&{\text{if }}n=2,3,4,5,7,8,9,11,13,16,\ldots =p^{k}{\text{ is a prime power}}\\0&{\text{if }}n=1,6,10,12,14,15,18,20,21,\dots \;\;\;\;{\text{ is not a prime power}}.\end{cases}}}$$

p(n) – partition function

p(n) , the partition function, is the number of ways of representing n as a sum of positive integers, where two representations with the same summands in a different order are not counted as being different: $${\displaystyle p(n)=\left|\left\{(a_{1},a_{2},\dots a_{k}):0<a_{1}\leq a_{2}\leq \cdots \leq a_{k}\;\land \;n=a_{1}+a_{2}+\cdots +a_{k}\right\}\right|.}$$

λ(n) – Carmichael function

λ(n) , the Carmichael function, is the smallest positive number such that ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$  for all a coprime to n. Equivalently, it is the least common multiple of the orders of the elements of the multiplicative group of integers modulo n.

For powers of odd primes and for 2 and 4, λ(n) is equal to the Euler totient function of n; for powers of 2 greater than 4 it is equal to one half of the Euler totient function of n: $${\displaystyle \lambda (n)={\begin{cases}\;\;\phi (n)&{\text{if }}n=2,3,4,5,7,9,11,13,17,19,23,25,27,\dots \\{\tfrac {1}{2}}\phi (n)&{\text{if }}n=8,16,32,64,\dots \end{cases}}}$$ and for general n it is the least common multiple of λ of each of the prime power factors of n: $${\displaystyle \lambda (p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}})=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})].}$$

h(n) – Class number

h(n) , the class number function, is the order of the ideal class group of an algebraic extension of the rationals with discriminant n. The notation is ambiguous, as there are in general many extensions with the same discriminant. See quadratic field and cyclotomic field for classical examples.

r_k(n) – Sum of k squares

r_k(n) is the number of ways n can be represented as the sum of k squares, where representations that differ only in the order of the summands or in the signs of the square roots are counted as different.

$${\displaystyle r_{k}(n)=\left|\left\{(a_{1},a_{2},\dots ,a_{k}):n=a_{1}^{2}+a_{2}^{2}+\cdots +a_{k}^{2}\right\}\right|}$$

D(n) – Arithmetic derivative

Using the Heaviside notation for the derivative, the arithmetic derivative D(n) is a function such that

• ${\displaystyle D(n)=1}$ if n prime, and
• ${\displaystyle D(mn)=mD(n)+D(m)n}$ (the product rule)

Dirichlet convolutions

${\displaystyle \sum _{\delta \mid n}\mu (\delta )=\sum _{\delta \mid n}\lambda \left({\frac {n}{\delta }}\right)|\mu (\delta )|={\begin{cases}1&{\text{if }}n=1\\0&{\text{if }}n\neq 1\end{cases}}}$   where λ is the Liouville function. ^[12]

${\displaystyle \sum _{\delta \mid n}\varphi (\delta )=n.}$    ^[13]

${\displaystyle \varphi (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta =n\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta }}.}$    Möbius inversion

${\displaystyle \sum _{d\mid n}J_{k}(d)=n^{k}.}$    ^[14]

${\displaystyle J_{k}(n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta ^{k}=n^{k}\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta ^{k}}}.}$    Möbius inversion

${\displaystyle \sum _{\delta \mid n}\delta ^{s}J_{r}(\delta )J_{s}\left({\frac {n}{\delta }}\right)=J_{r+s}(n)}$    ^[15]

${\displaystyle \sum _{\delta \mid n}\varphi (\delta )d\left({\frac {n}{\delta }}\right)=\sigma (n).}$    ^{[16] [17]}

${\displaystyle \sum _{\delta \mid n}|\mu (\delta )|=2^{\omega (n)}.}$    ^[18]

${\displaystyle |\mu (n)|=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)2^{\omega (\delta )}.}$    Möbius inversion

${\displaystyle \sum _{\delta \mid n}2^{\omega (\delta )}=d(n^{2}).}$   

${\displaystyle 2^{\omega (n)}=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d(\delta ^{2}).}$    Möbius inversion

${\displaystyle \sum _{\delta \mid n}d(\delta ^{2})=d^{2}(n).}$   

${\displaystyle d(n^{2})=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d^{2}(\delta ).}$    Möbius inversion

${\displaystyle \sum _{\delta \mid n}d\left({\frac {n}{\delta }}\right)2^{\omega (\delta )}=d^{2}(n).}$   

${\displaystyle \sum _{\delta \mid n}\lambda (\delta )={\begin{cases}&1{\text{ if }}n{\text{ is a square }}\\&0{\text{ if }}n{\text{ is not square.}}\end{cases}}}$   where λ is the Liouville function.

${\displaystyle \sum _{\delta \mid n}\Lambda (\delta )=\log n.}$    ^[19]

${\displaystyle \Lambda (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\log(\delta ).}$    Möbius inversion

Sums of squares

For all ${\displaystyle k\geq 4,\;\;\;r_{k}(n)>0.}$   (Lagrange's four-square theorem).

${\displaystyle r_{2}(n)=4\sum _{d\mid n}\left({\frac {-4}{d}}\right),}$ ^[20]

where the Kronecker symbol has the values

${\displaystyle \left({\frac {-4}{n}}\right)={\begin{cases}+1&{\text{if }}n\equiv 1{\pmod {4}}\\-1&{\text{if }}n\equiv 3{\pmod {4}}\\\;\;\;0&{\text{if }}n{\text{ is even}}.\\\end{cases}}}$

There is a formula for r₃ in the section on class numbers below. $${\displaystyle r_{4}(n)=8\sum _{\stackrel {d\mid n}{4\,\nmid \,d}}d=8(2+(-1)^{n})\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d={\begin{cases}8\sigma (n)&{\text{if }}n{\text{ is odd }}\\24\sigma \left({\frac {n}{2^{\nu }}}\right)&{\text{if }}n{\text{ is even }}\end{cases}},}$$ where ν = ν₂(n).    ^{[21] [22] [23]}

$${\displaystyle r_{6}(n)=16\sum _{d\mid n}\chi \left({\frac {n}{d}}\right)d^{2}-4\sum _{d\mid n}\chi (d)d^{2},}$$ where ${\displaystyle \chi (n)=\left({\frac {-4}{n}}\right).}$ ^[24]

Define the function σ_k^*(n) as ^[25] $${\displaystyle \sigma _{k}^{*}(n)=(-1)^{n}\sum _{d\mid n}(-1)^{d}d^{k}={\begin{cases}\sum _{d\mid n}d^{k}=\sigma _{k}(n)&{\text{if }}n{\text{ is odd }}\\\sum _{\stackrel {d\mid n}{2\,\mid \,d}}d^{k}-\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d^{k}&{\text{if }}n{\text{ is even}}.\end{cases}}}$$

That is, if n is odd, σ_k^*(n) is the sum of the kth powers of the divisors of n, that is, σ_k(n), and if n is even it is the sum of the kth powers of the even divisors of n minus the sum of the kth powers of the odd divisors of n.

${\displaystyle r_{8}(n)=16\sigma _{3}^{*}(n).}$   ^{[24] [26]}

Adopt the convention that Ramanujan's τ(x) = 0 if x is not an integer.

${\displaystyle r_{24}(n)={\frac {16}{691}}\sigma _{11}^{*}(n)+{\frac {128}{691}}\left\{(-1)^{n-1}259\tau (n)-512\tau \left({\frac {n}{2}}\right)\right\}}$   ^[27]

Divisor sum convolutions

Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of the product of two power series:

${\displaystyle \left(\sum _{n=0}^{\infty }a_{n}x^{n}\right)\left(\sum _{n=0}^{\infty }b_{n}x^{n}\right)=\sum _{i=0}^{\infty }\sum _{j=0}^{\infty }a_{i}b_{j}x^{i+j}=\sum _{n=0}^{\infty }\left(\sum _{i=0}^{n}a_{i}b_{n-i}\right)x^{n}=\sum _{n=0}^{\infty }c_{n}x^{n}.}$

The sequence ${\displaystyle c_{n}=\sum _{i=0}^{n}a_{i}b_{n-i}}$ is called the convolution or the Cauchy product of the sequences a_n and b_n.
These formulas may be proved analytically (see Eisenstein series) or by elementary methods. ^[28]

${\displaystyle \sigma _{3}(n)={\frac {1}{5}}\left\{6n\sigma _{1}(n)-\sigma _{1}(n)+12\sum _{0<k<n}\sigma _{1}(k)\sigma _{1}(n-k)\right\}.}$   ^[29]

${\displaystyle \sigma _{5}(n)={\frac {1}{21}}\left\{10(3n-1)\sigma _{3}(n)+\sigma _{1}(n)+240\sum _{0<k<n}\sigma _{1}(k)\sigma _{3}(n-k)\right\}.}$   ^[30]

${\displaystyle {\begin{aligned}\sigma _{7}(n)&={\frac {1}{20}}\left\{21(2n-1)\sigma _{5}(n)-\sigma _{1}(n)+504\sum _{0<k<n}\sigma _{1}(k)\sigma _{5}(n-k)\right\}\\&=\sigma _{3}(n)+120\sum _{0<k<n}\sigma _{3}(k)\sigma _{3}(n-k).\end{aligned}}}$   ^{[30] [31]}

${\displaystyle {\begin{aligned}\sigma _{9}(n)&={\frac {1}{11}}\left\{10(3n-2)\sigma _{7}(n)+\sigma _{1}(n)+480\sum _{0<k<n}\sigma _{1}(k)\sigma _{7}(n-k)\right\}\\&={\frac {1}{11}}\left\{21\sigma _{5}(n)-10\sigma _{3}(n)+5040\sum _{0<k<n}\sigma _{3}(k)\sigma _{5}(n-k)\right\}.\end{aligned}}}$   ^{[29] [32]}

${\displaystyle \tau (n)={\frac {65}{756}}\sigma _{11}(n)+{\frac {691}{756}}\sigma _{5}(n)-{\frac {691}{3}}\sum _{0<k<n}\sigma _{5}(k)\sigma _{5}(n-k),}$   where τ(n) is Ramanujan's function.    ^{[33] [34]}

Since σ_k(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences ^[35] for the functions. See Ramanujan tau function for some examples.

Extend the domain of the partition function by setting p(0) = 1.

${\displaystyle p(n)={\frac {1}{n}}\sum _{1\leq k\leq n}\sigma (k)p(n-k).}$   ^[36]   This recurrence can be used to compute p(n).

Class number related

Peter Gustav Lejeune Dirichlet discovered formulas that relate the class number h of quadratic number fields to the Jacobi symbol. ^[37]

An integer D is called a fundamental discriminant if it is the discriminant of a quadratic number field. This is equivalent to D ≠ 1 and either a) D is squarefree and D ≡ 1 (mod 4) or b) D ≡ 0 (mod 4), D/4 is squarefree, and D/4 ≡ 2 or 3 (mod 4). ^[38]

Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the Kronecker symbol: $${\displaystyle \left({\frac {a}{2}}\right)={\begin{cases}\;\;\,0&{\text{ if }}a{\text{ is even}}\\(-1)^{\frac {a^{2}-1}{8}}&{\text{ if }}a{\text{ is odd. }}\end{cases}}}$$

Then if D < −4 is a fundamental discriminant ^{[39] [40]} $${\displaystyle {\begin{aligned}h(D)&={\frac {1}{D}}\sum _{r=1}^{|D|}r\left({\frac {D}{r}}\right)\\&={\frac {1}{2-\left({\tfrac {D}{2}}\right)}}\sum _{r=1}^{|D|/2}\left({\frac {D}{r}}\right).\end{aligned}}}$$

There is also a formula relating r₃ and h. Again, let D be a fundamental discriminant, D < −4. Then ^[41] $${\displaystyle r_{3}(|D|)=12\left(1-\left({\frac {D}{2}}\right)\right)h(D).}$$

Prime-count related

Let ${\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}}$  be the nth harmonic number. Then

${\displaystyle \sigma (n)\leq H_{n}+e^{H_{n}}\log H_{n}}$  is true for every natural number n if and only if the Riemann hypothesis is true.    ^[42]

The Riemann hypothesis is also equivalent to the statement that, for all n > 5040, $${\displaystyle \sigma (n)<e^{\gamma }n\log \log n}$$ (where γ is the Euler–Mascheroni constant). This is Robin's theorem.

${\displaystyle \sum _{p}\nu _{p}(n)=\Omega (n).}$

${\displaystyle \psi (x)=\sum _{n\leq x}\Lambda (n).}$   ^[43]

${\displaystyle \Pi (x)=\sum _{n\leq x}{\frac {\Lambda (n)}{\log n}}.}$   ^[44]

${\displaystyle e^{\theta (x)}=\prod _{p\leq x}p.}$   ^[45]

${\displaystyle e^{\psi (x)}=\operatorname {lcm} [1,2,\dots ,\lfloor x\rfloor ].}$   ^[46]

Menon's identity

In 1965 P Kesava Menon proved ^[47] $${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n).}$$

This has been generalized by a number of mathematicians. For example,

• B. Sury ^[48] $${\displaystyle \sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{\gcd(k_{1},n)=1}}\gcd(k_{1}-1,k_{2},\dots ,k_{s},n)=\varphi (n)\sigma _{s-1}(n).}$$
• N. Rao ^[49] $${\displaystyle \sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{\gcd(k_{1},k_{2},\dots ,k_{s},n)=1}}\gcd(k_{1}-a_{1},k_{2}-a_{2},\dots ,k_{s}-a_{s},n)^{s}=J_{s}(n)d(n),}$$ where a₁, a₂, ..., a_s are integers, gcd(a₁, a₂, ..., a_s, n) = 1.
• László Fejes Tóth ^[50] $${\displaystyle \sum _{\stackrel {1\leq k\leq m}{\gcd(k,m)=1}}\gcd(k^{2}-1,m_{1})\gcd(k^{2}-1,m_{2})=\varphi (n)\sum _{\stackrel {d_{1}\mid m_{1}}{d_{2}\mid m_{2}}}\varphi (\gcd(d_{1},d_{2}))2^{\omega (\operatorname {lcm} (d_{1},d_{2}))},}$$ where m₁ and m₂ are odd, m = lcm(m₁, m₂).

In fact, if f is any arithmetical function ^{[51] [52]} $${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}f(\gcd(k-1,n))=\varphi (n)\sum _{d\mid n}{\frac {(\mu *f)(d)}{\varphi (d)}},}$$ where ${\displaystyle *}$ stands for Dirichlet convolution.

Miscellaneous

Let m and n be distinct, odd, and positive. Then the Jacobi symbol satisfies the law of quadratic reciprocity: $${\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{(m-1)(n-1)/4}.}$$

Let D(n) be the arithmetic derivative. Then the logarithmic derivative $${\displaystyle {\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}.}$$ See Arithmetic derivative for details.

Let λ(n) be Liouville's function. Then

${\displaystyle |\lambda (n)|\mu (n)=\lambda (n)|\mu (n)|=\mu (n),}$   and

${\displaystyle \lambda (n)\mu (n)=|\mu (n)|=\mu ^{2}(n).}$  

Let λ(n) be Carmichael's function. Then

${\displaystyle \lambda (n)\mid \phi (n).}$   Further,

${\displaystyle \lambda (n)=\phi (n){\text{ if and only if }}n={\begin{cases}1,2,4;\\3,5,7,9,11,\ldots {\text{ (that is, }}p^{k}{\text{, where }}p{\text{ is an odd prime)}};\\6,10,14,18,\ldots {\text{ (that is, }}2p^{k}{\text{, where }}p{\text{ is an odd prime)}}.\end{cases}}}$

See Multiplicative group of integers modulo n and Primitive root modulo n.  

${\displaystyle 2^{\omega (n)}\leq d(n)\leq 2^{\Omega (n)}.}$   ^{[53] [54]}

${\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\phi (n)\sigma (n)}{n^{2}}}<1.}$   ^[55]

${\displaystyle {\begin{aligned}c_{q}(n)&={\frac {\mu \left({\frac {q}{\gcd(q,n)}}\right)}{\phi \left({\frac {q}{\gcd(q,n)}}\right)}}\phi (q)\\&=\sum _{\delta \mid \gcd(q,n)}\mu \left({\frac {q}{\delta }}\right)\delta .\end{aligned}}}$   ^[56]    Note that  ${\displaystyle \phi (q)=\sum _{\delta \mid q}\mu \left({\frac {q}{\delta }}\right)\delta .}$   ^[57]

${\displaystyle c_{q}(1)=\mu (q).}$

${\displaystyle c_{q}(q)=\phi (q).}$

${\displaystyle \sum _{\delta \mid n}d^{3}(\delta )=\left(\sum _{\delta \mid n}d(\delta )\right)^{2}.}$   ^[58]   Compare this with 1³ + 2³ + 3³ + ... + n³ = (1 + 2 + 3 + ... + n)²

${\displaystyle d(uv)=\sum _{\delta \mid \gcd(u,v)}\mu (\delta )d\left({\frac {u}{\delta }}\right)d\left({\frac {v}{\delta }}\right).}$   ^[59]

${\displaystyle \sigma _{k}(u)\sigma _{k}(v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{k}\sigma _{k}\left({\frac {uv}{\delta ^{2}}}\right).}$   ^[60]

${\displaystyle \tau (u)\tau (v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{11}\tau \left({\frac {uv}{\delta ^{2}}}\right),}$   where τ(n) is Ramanujan's function.    ^[61]