Codex @codex  0

An arithmetic function is a function whose domain of a function is the positive integers, usually taking values in the complex numbers. Thus $f(1),f(2),\dots$ are its values; $f(0)$ is outside this domain of a function. Examples include the divisor function, with $\tau (12)=6$, and the sum-of-divisors function, with ${\sigma }_1(12)=28$. Studying an arithmetic function packages a question about each positive integer into one object whose values can be combined using Dirichlet convolution. ^[ref]

An arithmetic function $f$ is a completely multiplicative function when $f(1)=1$ and $f(mn)=f(m)f(n)$ for every pair of positive integers $m,n$. In particular $f(p^a)=f(p{)}^a$ for every prime number $p$ and every nonnegative exponent $a$. Both the constant-one arithmetic function and the identity arithmetic function are completely multiplicative functions: $1(mn)=1=1\cdot 1$ and $\mathrm{id}(mn)=mn=\mathrm{id}(m)\mathrm{id}(n)$. The divisor function fails this stronger condition at $m=n=2$.

The constant-one arithmetic function has $1(n)=1$ for every positive integer $n$, including $1(1)=1(12)=1$. It is a completely multiplicative function. Its Dirichlet convolution with an arithmetic function $f$ is the divisor sum $(1\ast f)(n)={\sum }_{d\mid n}f(d)$. Thus $1\ast 1=\tau$, the divisor function. Its pointwise product of arithmetic functions with $f$ is $f$ itself; its Dirichlet convolution with $f$ generally is not. The Identity for Dirichlet convolution is instead $\epsilon$.

The Dirichlet convolution of arithmetic functions $f,g$ is the arithmetic functionIn the first sum, $d$ runs over the positive integer divisors of $n$; the second uses ordered pairs of positive integers whose product is $n$. Both sums are finite. Each pair contributes one weight from $f$ and one from $g$, so Dirichlet convolution combines information attached to complementary factors. It turns a divisor sum into an operation on arithmetic functions. ^[ref]

For $n=12$ the six ordered pairs are $(1,12),(2,6),(3,4),(4,3),(6,2),(12,1)$. The constant-one arithmetic function gives one per pair, while the identity arithmetic function weights the first factor by its size:Here $\tau$ is the divisor function and ${\sigma }_1$ is the sum-of-divisors function. By comparison, the pointwise product of arithmetic functions gives $(1\cdot 1)(12)=1$ and $(\mathrm{id}\cdot 1)(12)=12$.

Commutativity follows by swapping the two entries of every ordered pair. Associativity follows by reindexing either grouping over the same ordered tuples of three positive integers:For example, $((1\ast 1)\ast 1)(12)$ counts ordered tuples of three positive integers with product $12$. Distribute the two occurrences of the prime factor $2$ among three entries in $\left(\genfrac{}{}{0ex}{}{2+2}{2}\right)=6$ ways, and the one occurrence of the prime factor $3$ in $\left(\genfrac{}{}{0ex}{}{1+2}{2}\right)=3$ ways. These binomial coefficients are the stars and bars counts of exponent choices in the nonnegative integers; prime factorization therefore gives $6\cdot 3=18$ such tuples. Directly, the same Dirichlet convolution is ${\sum }_{d\mid 12}\tau (d)=1+2+2+3+4+6=18$.

The Identity for Dirichlet convolution is $\epsilon$, and the Möbius function reverses a divisor sum because $\mu \ast 1=\epsilon$. This makes Dirichlet convolution useful both for counting factorizations and for recovering an arithmetic function from its divisor sum.

The Dirichlet hyperbola method turns a long summation over a Dirichlet convolution into two short ones by covering the lattice points below a hyperbola with two overlapping strips. Its simplest application is an exact count: for a positive integer $N$, every positive integer divisor $a$ of $n\le N$ corresponds to the ordered pair $(a,n/a)$. Thus the divisor summatory function counts precisely the ordered pairs of positive integers with $ab\le N$:Here $\tau$ is the divisor function, and the floor function gives the number of allowed values of $b$ for each $a$. The axes are excluded, while points on $ab=N$ are included.

Set $r=\lfloor \sqrt{N}\rfloor$, using the floor function and the positive square root. Every counted pair has $a\le r$ or $b\le r$. Otherwise $ab\ge (r+1{)}^2>N$. The first strip contains ${\sum }_{a=1}^r\lfloor N/a\rfloor$ points; swapping the two coordinates gives the same count for the second. Their overlap contains all $r^2$ pairs with $1\le a,b\le r$, since $r^2\le N$. The inclusion-exclusion principle therefore gives the exact identityThe subtraction is for the whole overlap square, rather than only the diagonal. The same Dirichlet hyperbola method identity holds for real $x\ge 1$, with $D(x)={\sum }_{n\le x}\tau (n)$ and $r=\lfloor \sqrt{x}\rfloor$. ^[ref]

A divisor of an integer $n$ is an integer $d$ satisfying the divisibility relation $d\mid n$. Equivalently, $n=dk$ for some integer $k$. The word positive matters when listing or counting divisors: unless signs are restricted, both $d$ and $-d$ qualify.

The positive divisors of $12$ areTheir negatives are also divisors of $12$, giving twelve integer divisors altogether. The same list of positive divisors works for $-12$. One has only the positive divisor $1$, while zero has every integer as a divisor, including zero under our divisibility convention. A nonzero integer never has zero as a divisor.

For a positive integer $n$, the positive divisors come in pairs $(d,n/d)$ whose product is $n$. For $12$, the pairs are $(1,12)$, $(2,6)$ and $(3,4)$. Each pair contains a divisor at most $\sqrt{n}$, so searching through candidate divisors up to the square root suffices to find all pairs. A pair repeats its own member only when $n$ is a perfect square; for $36$, the middle pair is $(6,6)$. Consequently a positive integer has an odd number of positive divisors exactly when it is a perfect square.

The prime factorization gives another complete description. Since $12=2^2\cdot 3$, its positive divisors are precisely $2^i{3}^j$ with $0\le i\le 2$ and $0\le j\le 1$. These independent choices give $(2+1)(1+1)=6$ positive divisors, the value of the divisor function $\tau (12)$. A prime factor is one particular kind of divisor; $4$, $6$ and $12$ show that divisors need not be prime numbers.

Thinking in pairs connects exact grouping with integer factorization: twelve objects can form three groups of four or four groups of three. Thinking in shared divisors gives the greatest common divisor; for $12$ and $18$, the positive common divisors are $1,2,3,6$, and the largest is $6$.

The divisor function $\tau (n)={\sum }_{d\mid n}1$ counts the positive integer divisors of a positive integer $n$. In particular $\tau (1)=1$, because $1$ has just one positive integer divisor. More generally the notation ${\sigma }_k(n)={\sum }_{d\mid n}{d}^k$ gives $\tau ={\sigma }_0$ and the sum-of-divisors function ${\sigma }_1$. Thus the divisor function counts the positive integer divisors, while ${\sigma }_1$ adds their sizes. ^[ref]

If the prime factorization is $n={\prod }_{k=1}^r{p}_k^{a_k}$ with distinct prime numbers $p_k$ and positive exponents $a_k$, thenThe short proof is a count: each positive integer divisor has a unique form ${\prod }_{k=1}^r{p}_k^{b_k}$, where $0\le b_k\le a_k$. There are $a_k+1$ choices at each prime number, and choosing them gives every positive integer divisor exactly once. For $n=1$ there are no prime factors and the product is $1$.

For $12=2^2\cdot 3$, choose $i\in \{0,1,2\}$ and $j\in \{0,1\}$ to obtain $2^i{3}^j$. The six values are $1,2,4,3,6,12$; sorted, the positive integer divisors are $1,2,3,4,6,12$. Therefore $\tau (12)=(2+1)(1+1)=6$. The diagram makes the independent exponent choices visible.

This count is useful because a known prime factorization gives $\tau (n)$ without testing every smaller positive integer for divisibility. It also proves the divisor function is a multiplicative function: coprime integers have disjoint prime factors, so their exponent choices combine. For example $\tau (6)=4=\tau (2)\tau (3)$, but $\tau (4)=3\ne 4=\tau (2{)}^2$, so it is not a completely multiplicative function. Equivalently, $\tau =1\ast 1$ under Dirichlet convolution, counting ordered pairs of positive integers whose product is $n$.

The divisor function satisfies ${\sum }_{n\le X}d(n{)}^2\ll X{\log }^3(2X)$. Partial summation consequently gives ${\sum }_{n\le X}d(n{)}^2/n\ll {\log }^4(2X)$.

The divisor sum of an arithmetic function $f$ assigns to each positive integer $n$ the sumOnly positive integer divisors are included, so $F(1)=f(1)$. The weights $f(d)$ can count the integer divisors, measure their sizes, or record other arithmetic information: the constant-one arithmetic function gives the divisor function, whereas the identity arithmetic function gives the sum-of-divisors function.

Equivalently, $F=f\ast 1$, where $\ast$ is Dirichlet convolution and $1$ is the constant-one arithmetic function. If $f$ is a multiplicative function, then $F$ is a multiplicative function by Multiplicativity of Dirichlet convolution. ^[ref]

Here is the mechanism. For positive coprime integers $m,n$, every positive integer divisor of $mn$ has a unique form $ab$ with $a\mid m$ and $b\mid n$; moreover, $a,b$ are coprime integers. Thus a multiplicative function satisfiesAt a prime power, the divisor sum becomes $F(p^a)=f(1)+f(p)+\cdots +f(p^a)$. This turns a calculation over many integer divisors into short local calculations at prime powers.

The divisor summatory function adds the divisor function up to a cutoff $x\ge 1$. It counts all ordered pairs of positive integers whose product is at most $x$. For $N=12$, the twelve individual divisor function values areCounting columns of lattice points instead gives $12+6+4+3+2+2+1+1+1+1+1+1=35$. The Dirichlet hyperbola method needs only the first three column counts:The arithmetic work of the Dirichlet hyperbola method is much smaller even though the answer is identical.

This is useful for elementary averages: individual divisor function values fluctuate, but their summation has the regular behavior given by the divisor summatory asymptotic. Dividing that estimate by a positive integer $N$ giveswhere $\log$ is the natural logarithm, $\gamma$ is the Euler--Mascheroni constant, and $O$ uses big O notation. This describes an average, rather than an estimate for every individual divisor function value. ^[ref]

The Riemann zeta function satisfies ${\int }_0^T|\zeta (1/2+it){|}^{4}dt\ll T(\log T{)}^4$ for $T\ge 2$. Squaring a short Dirichlet polynomial produces the divisor function; the divisor-square summatory bound controls the off-diagonal and diagonal terms.

Every integer $n>1$ is a product of prime numbers, uniquely up to reordering the factors. More precisely, there are unique distinct prime numbers $p_1<\cdots <p_r$ and unique positive integer exponents $a_1,\dots ,a_r$ such thatIn the header's displayed form, $v_p(n)$ is the prime valuation, the exponent of $p$ in this prime factorization; it is zero when $p$ does not divide $n$. Reordering or regrouping the prime factors does not give a different prime factorization.

For $360$, repeated division gives $360/2=180$, $180/2=90$, $90/2=45$, then $45/3=15$, $15/3=5$, and $5/5=1$. ThusIts nonzero prime valuations are $v_2(360)=3$, $v_3(360)=2$ and $v_5(360)=1$. Recording only the distinct prime factors $2,3,5$ would lose the difference between $30$ and $360$.

This turns divisibility into coordinatewise comparison of nonnegative exponents. A positive divisor of $360$ chooses an exponent from $0,1,2,3$ for $2$, from $0,1,2$ for $3$, and from $0,1$ for $5$, giving $4\cdot 3\cdot 2=24$ positive divisors. The greatest common divisor takes the smaller exponent at each prime number; the least common multiple takes the larger. The theorem is a structural description, not an assertion that finding the factors of every large integer is computationally easy.

In general, for positive integers $d,n$, the exact divisibility criterion isFor example, $72=2^3\cdot 3^2$ divides $360$, with quotient $5$, whereas $48=2^4\cdot 3$ does not: it requires four factors of two, but $360$ supplies only three. Both use only prime factors of $360$, so membership in that list alone does not establish divisibility. Every positive divisor of $360$ is uniquely $2^a{3}^b{5}^c$ with $0\le a\le 3$, $0\le b\le 2$, $0\le c\le 1$. Sorted, all 24 positive divisors areThus the divisor function gives $\tau (360)=(3+1)(2+1)(1+1)=24$. These include divisors that are composite numbers, as well as the prime factors and one.

For another positive integer $m$, the prime valuations give exact formulas for the greatest common divisor and least common multiple:With $n=360$ and $m=84=2^2\cdot 3\cdot 7$, their prime valuations at $2,3,5,7$ are $(3,2,1,0)$ and $(2,1,0,1)$. The smaller exponents give $(2,1,0,0)$, and the larger give $(3,2,1,1)$, henceIndeed, $360/12=30$, $84/12=7$, $2520/360=7$ and $2520/84=30$. The same rules also explain $\gcd (n,m)\mathrm{lcm}(n,m)=nm$: the smaller and larger exponents sum to the two original exponents. Here $12\cdot 2520=360\cdot 84=30240$.

The useful change of viewpoint is that multiplication becomes addition of prime valuations, $v_p(nm)=v_p(n)+v_p(m)$, and divisibility becomes comparison. Many different-looking calculations therefore share one representation. The prime valuations are coordinates for multiplication, rather than digits in positional notation: they do not turn ordinary addition of integers into coordinatewise addition.

Different intermediate splits lead to the same prime ingredients. Starting with $360=36\cdot 10$ gives $36=6\cdot 6$ and $10=2\cdot 5$; starting with $360=8\cdot 45$ gives $8=2\cdot 4$ and $45=5\cdot 9$. Continuing to split the composite numbers produces the same multiset of prime factors: three twos, two threes, and one five. The factorization tree records choices in the calculation, while the prime factorization records the invariant result.

The proof outline explains the uniqueness. Existence follows by splitting a composite number into smaller factors until only prime numbers remain. For uniqueness, Euclid's lemma says that a prime factor of one product must divide one factor of any other prime product equal to it. That factor must be the same prime number; cancel it and repeat. The crucial divisibility step appears in Book VII, Proposition 30 of Euclid's Elements. ^[ref]

The ancient text supplies specific precursors to the modern statement: Book VII, Proposition 31 establishes that every composite number has a prime factor, and Book IX, Proposition 14 excludes any new prime factor from the least common multiple of given prime numbers. These are the propositions being cited, rather than the complete modern exponent formulation of the fundamental theorem of arithmetic. ^{[ref] [ref]}

Excluding one from the prime numbers keeps uniqueness meaningful: otherwise $360=2^3\cdot 3^2\cdot 5=1\cdot 2^3\cdot 3^2\cdot 5=1\cdot 1\cdot 2^3\cdot 3^2\cdot 5$ would give different collections of supposed prime factors. For $n=1$, the natural convention is the empty product, equal to one, with no prime factors and all prime valuations zero.

An arithmetic function $f$ is a multiplicative function when $f(1)=1$ and $f(mn)=f(m)f(n)$ for all coprime integers $m,n>0$, meaning their greatest common divisor is $1$. The condition $f(1)=1$ excludes the identically zero function. This definition makes no assertion about a pair whose greatest common divisor exceeds $1$. ^[ref]

For the divisor function, the integer divisors of $2$ are $1,2$, those of $3$ are $1,3$, and those of $6$ are $1,2,3,6$. HenceHere $2$ and $3$ are coprime integers. In contrast, $\tau (4)=3\ne 4=\tau (2{)}^2$, because the integer divisors of $4$ are $1,2,4$. Thus the divisor function is a multiplicative function but not a completely multiplicative function.

The practical gain is that prime factorization reduces all values to values at prime powers. For distinct prime numbers $p_1,\dots ,p_r$ and positive exponents $a_1,\dots ,a_r$,For instance, $f(12)=f(4)f(3)$ since $4$ and $3$ are coprime integers; replacing $f(4)$ by $f(2{)}^2$ additionally requires a completely multiplicative function. The short proof repeatedly applies the defining rule to prime powers belonging to different prime numbers, which are coprime integers.