27 Functions of Number TheoryMultiplicative Number Theory27.1 Special Notation27.3 Multiplicative Properties

Functions in this section derive their properties from the *fundamental
theorem of arithmetic*, which states that every integer $n>1$ can be
represented uniquely as a product of prime powers,

27.2.1 | $$n=\prod _{r=1}^{\nu \left(n\right)}{p}_{r}^{{a}_{r}},$$ | ||

where ${p}_{1},{p}_{2},\mathrm{\dots},{p}_{\nu \left(n\right)}$ are the distinct prime factors of $n$, each exponent ${a}_{r}$ is positive, and $\nu \left(n\right)$ is the number of distinct primes dividing $n$. ($\nu \left(1\right)$ is defined to be 0.) Euclid’s Elements (Euclid (1908, Book IX, Proposition 20)) gives an elegant proof that there are infinitely many primes. Tables of primes (§27.21) reveal great irregularity in their distribution. They tend to thin out among the large integers, but this thinning out is not completely regular. There is great interest in the function $\pi \left(x\right)$ that counts the number of primes not exceeding $x$. It can be expressed as a sum over all primes $p\le x$:

27.2.2 | $$\pi \left(x\right)=\sum _{p\le x}1.$$ | ||

Gauss and Legendre conjectured that $\pi \left(x\right)$ is asymptotic to $x/\mathrm{log}x$ as $x\to \mathrm{\infty}$:

27.2.3 | $$\pi \left(x\right)\sim \frac{x}{\mathrm{log}x}.$$ | ||

(See Gauss (1863, Band II, pp. 437–477) and Legendre (1808, p. 394).)

This result, first proved in Hadamard (1896) and
de la Vallée Poussin (1896a, b), is known as
the *prime number theorem*. An equivalent form states that the $n$th prime
${p}_{n}$ (when the primes are listed in increasing order) is asymptotic to
$n\mathrm{log}n$ as $n\to \mathrm{\infty}$:

27.2.4 | $${p}_{n}\sim n\mathrm{log}n.$$ | ||

(See also §27.12.) Other examples of number-theoretic functions treated in this chapter are as follows.

27.2.5 | $$\lfloor \frac{1}{n}\rfloor =\{\begin{array}{cc}1,\hfill & n=1,\hfill \\ 0,\hfill & n>1.\hfill \end{array}$$ | ||

27.2.6 | $${\varphi}_{k}\left(n\right)=\sum _{\left(m,n\right)=1}{m}^{k},$$ | ||

the sum of the $k$th powers of the positive integers $m\le n$ that are relatively prime to $n$.

27.2.7 | $$\varphi \left(n\right)={\varphi}_{0}\left(n\right).$$ | ||

This is the number of positive integers $\le n$ that are relatively prime to
$n$; $\varphi \left(n\right)$ is *Euler’s totient*.

If $\left(a,n\right)=1$, then the *Euler–Fermat theorem* states that

27.2.8 | $${a}^{\varphi \left(n\right)}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}\left(modn\right),$$ | ||

and if $\varphi \left(n\right)$ is the smallest positive integer $f$ such that
${a}^{f}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}\left(modn\right)$, then $a$ is a *primitive root* mod $n$. The
$\varphi \left(n\right)$ numbers $a,{a}^{2},\mathrm{\dots},{a}^{\varphi \left(n\right)}$ are
relatively prime to $n$ and distinct (mod $n$). Such a set is a *reduced
residue system* modulo $n$.

27.2.9 | $$d\left(n\right)=\sum _{d|n}1$$ | ||

is the number of divisors of $n$ and is the *divisor function*. It is the
special case $k=2$ of the function ${d}_{k}\left(n\right)$ that counts the
number of ways of expressing $n$ as the product of $k$ factors, with the order
of factors taken into account.

27.2.10 | $${\sigma}_{\alpha}\left(n\right)=\sum _{d|n}{d}^{\alpha},$$ | ||

is the sum of the $\alpha $th powers of the divisors of $n$, where the exponent $\alpha $ can be real or complex. Note that ${\sigma}_{0}\left(n\right)=d\left(n\right)$.

27.2.11 | $${J}_{k}\left(n\right)=\sum _{\left(\left({d}_{1},\mathrm{\dots},{d}_{k}\right),n\right)=1}1,$$ | ||

is the number of $k$-tuples of integers $\le n$ whose greatest common divisor
is relatively prime to $n$. This is *Jordan’s function*. Note that
${J}_{1}\left(n\right)=\varphi \left(n\right)$.

In the following examples, ${a}_{1},\mathrm{\dots},{a}_{\nu \left(n\right)}$ are the exponents in the factorization of $n$ in (27.2.1).

27.2.12 | $$\mu \left(n\right)=\{\begin{array}{cc}1,\hfill & n=1,\hfill \\ {\left(-1\right)}^{\nu \left(n\right)},\hfill & {a}_{1}={a}_{2}=\mathrm{\dots}={a}_{\nu \left(n\right)}=1,\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$ | ||

This is the *Möbius function*.

27.2.13 | $$\lambda \left(n\right)=\{\begin{array}{cc}1,\hfill & n=1,\hfill \\ {\left(-1\right)}^{{a}_{1}+\mathrm{\dots}+{a}_{\nu \left(n\right)}},\hfill & n>1.\hfill \end{array}$$ | ||

This is *Liouville’s function*.

27.2.14 | $$\mathrm{\Lambda}\left(n\right)=\mathrm{log}p,$$ | ||

$n={p}^{a}$, | |||

where ${p}^{a}$ is a prime power with $a\ge 1$; otherwise
$\mathrm{\Lambda}\left(n\right)=0$. This is *Mangoldt’s function*.

Table 27.2.1 lists the first 100 prime numbers ${p}_{n}$. Table 27.2.2 tabulates the Euler totient function $\varphi \left(n\right)$, the divisor function $d\left(n\right)$ ($={\sigma}_{0}\left(n\right)$), and the sum of the divisors $\sigma \left(n\right)$ ($={\sigma}_{1}\left(n\right)$), for $n=1\left(1\right)52$.

$n$ | ${p}_{n}$ | ${p}_{n+10}$ | ${p}_{n+20}$ | ${p}_{n+30}$ | ${p}_{n+40}$ | ${p}_{n+50}$ | ${p}_{n+60}$ | ${p}_{n+70}$ | ${p}_{n+80}$ | ${p}_{n+90}$ |
---|---|---|---|---|---|---|---|---|---|---|

1 | 2 | 31 | 73 | 127 | 179 | 233 | 283 | 353 | 419 | 467 |

2 | 3 | 37 | 79 | 131 | 181 | 239 | 293 | 359 | 421 | 479 |

3 | 5 | 41 | 83 | 137 | 191 | 241 | 307 | 367 | 431 | 487 |

4 | 7 | 43 | 89 | 139 | 193 | 251 | 311 | 373 | 433 | 491 |

5 | 11 | 47 | 97 | 149 | 197 | 257 | 313 | 379 | 439 | 499 |

6 | 13 | 53 | 101 | 151 | 199 | 263 | 317 | 383 | 443 | 503 |

7 | 17 | 59 | 103 | 157 | 211 | 269 | 331 | 389 | 449 | 509 |

8 | 19 | 61 | 107 | 163 | 223 | 271 | 337 | 397 | 457 | 521 |

9 | 23 | 67 | 109 | 167 | 227 | 277 | 347 | 401 | 461 | 523 |

10 | 29 | 71 | 113 | 173 | 229 | 281 | 349 | 409 | 463 | 541 |

$n$ | $\varphi \left(n\right)$ | $d\left(n\right)$ | $\sigma \left(n\right)$ | $n$ | $\varphi \left(n\right)$ | $d\left(n\right)$ | $\sigma \left(n\right)$ | $n$ | $\varphi \left(n\right)$ | $d\left(n\right)$ | $\sigma \left(n\right)$ | $n$ | $\varphi \left(n\right)$ | $d\left(n\right)$ | $\sigma \left(n\right)$ |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 1 | 1 | 1 | 14 | 6 | 4 | 24 | 27 | 18 | 4 | 40 | 40 | 16 | 8 | 90 |

2 | 1 | 2 | 3 | 15 | 8 | 4 | 24 | 28 | 12 | 6 | 56 | 41 | 40 | 2 | 42 |

3 | 2 | 2 | 4 | 16 | 8 | 5 | 31 | 29 | 28 | 2 | 30 | 42 | 12 | 8 | 96 |

4 | 2 | 3 | 7 | 17 | 16 | 2 | 18 | 30 | 8 | 8 | 72 | 43 | 42 | 2 | 44 |

5 | 4 | 2 | 6 | 18 | 6 | 6 | 39 | 31 | 30 | 2 | 32 | 44 | 20 | 6 | 84 |

6 | 2 | 4 | 12 | 19 | 18 | 2 | 20 | 32 | 16 | 6 | 63 | 45 | 24 | 6 | 78 |

7 | 6 | 2 | 8 | 20 | 8 | 6 | 42 | 33 | 20 | 4 | 48 | 46 | 22 | 4 | 72 |

8 | 4 | 4 | 15 | 21 | 12 | 4 | 32 | 34 | 16 | 4 | 54 | 47 | 46 | 2 | 48 |

9 | 6 | 3 | 13 | 22 | 10 | 4 | 36 | 35 | 24 | 4 | 48 | 48 | 16 | 10 | 124 |

10 | 4 | 4 | 18 | 23 | 22 | 2 | 24 | 36 | 12 | 9 | 91 | 49 | 42 | 3 | 57 |

11 | 10 | 2 | 12 | 24 | 8 | 8 | 60 | 37 | 36 | 2 | 38 | 50 | 20 | 6 | 93 |

12 | 4 | 6 | 28 | 25 | 20 | 3 | 31 | 38 | 18 | 4 | 60 | 51 | 32 | 4 | 72 |

13 | 12 | 2 | 14 | 26 | 12 | 4 | 42 | 39 | 24 | 4 | 56 | 52 | 24 | 6 | 98 |