Arithmetic Functions: Definitions and Examples

How many divisors does 5,040 have? How many integers below a million are coprime to it? How is an integer built from primes? Each question has an answer. That answer depends only on the integer itself. Yet the rules producing these answers look nothing alike at first glance. Number theory organizes all of them under a single unifying concept: the arithmetic function, a rule assigning a complex number to each positive integer. This idea matters because it turns number theory into an algebraic and analytic playground. Divisor counts, sums of divisors, prime factorization data, and coprimality counts can all be recognized as functions on the same domain. Once this is done, one can add them, multiply them, and compose them under new operations. One can also ask about their growth, average size, and special values. The apparent chaos of "how numbers factor" becomes a structured study of functions with rich internal patterns. Some are multiplicative, some additive, some neither. Yet all are built from the same divisibility data every reader already knows. The big picture is this: an arithmetic function is deliberately a very weak kind of object. It is just a sequence of complex numbers indexed by 1,2,3,…1, 2, 3, \dots. But the ones number theory actually cares about are never arbitrary. They arise from counting divisors, from prime factorizations, from Euler's totient, from Möbius's alternating sign trick. Recognizing the common domain and codomain of these examples is a necessary first step. Only then can one define the algebraic structures — multiplicativity, Dirichlet convolution — that make the subject computationally powerful. This article gives the formal definition of an arithmetic function. It develops the canonical examples in full rigorous detail: the divisor function, the sum-of-divisors function, Euler's totient, the Möbius function, the Liouville function, and the von Mangoldt function. It proves their basic defining formulas from first principles. It also sets up — without yet proving — the multiplicative structure that later material builds upon.

Key takeaways
  • An arithmetic function is any function f:Z+→Cf : \mathbb{Z}^{+} \to \mathbb{C}; no further structure is assumed a priori.
  • The set of all arithmetic functions forms a C\mathbb{C}-vector space under pointwise addition and scalar multiplication.
  • Canonical examples: τ(n)\tau(n) (number of divisors), σ(n)\sigma(n) (sum of divisors), φ(n)\varphi(n) (Euler's totient), μ(n)\mu(n) (Möbius function), λ(n)\lambda(n) (Liouville function), Λ(n)\Lambda(n) (von Mangoldt function).
  • Each example is computed directly from the prime factorization n=p1a1⋯pkakn = p_1^{a_1} \cdots p_k^{a_k}, giving closed formulas that are proved rigorously here.
  • These functions later turn out to be multiplicative — a structural property studied as its own topic and combined via Dirichlet Convolution.
  • Key idea: collapsing many different divisibility-counting problems into one common object — a function on Z+\mathbb{Z}^+ — is what lets number theory apply uniform algebraic and analytic tools to all of them at once.

Where this lives today

The divisor and totient functions are the computational backbone of RSA cryptography: key generation depends on computing φ(n)\varphi(n) for an RSA modulus n=pqn=pq, and the security of the scheme rests on the hardness of factoring nn (equivalently, of computing φ(n)\varphi(n)) without knowing p,qp,q individually. The Möbius function μ(n)\mu(n) underlies Möbius inversion, a technique used across combinatorics, algebraic topology (inclusion–exclusion on posets), and analytic number theory to invert divisor sums. The von Mangoldt function Λ(n)\Lambda(n) is the central object in the analytic proof of the Prime Number Theorem, appearing in the logarithmic derivative of the Riemann zeta function. The Liouville function λ(n)\lambda(n) appears in equivalent reformulations of the Riemann Hypothesis via the Pólya conjecture and related summatory-function identities. In computer science, fast computation of τ(n)\tau(n), σ(n)\sigma(n), and φ(n)\varphi(n) from a factorization is a standard subroutine in computational number theory libraries, and average-order estimates for these functions (their typical size as nn ranges over large intervals) are a staple topic in analytic number theory and probabilistic number theory alike.

Ask the tutor: How do the closed formulas for τ\tau, σ\sigma, and φ\varphi all follow from a single unifying property called multiplicativity?

DefinitionArithmetic function

An arithmetic function (also called a number-theoretic function) is any function

f:Z+⟶C.f : \mathbb{Z}^{+} \longrightarrow \mathbb{C}.

That is, ff assigns to every positive integer nn a complex number f(n)f(n), subject to no further condition. The set of all arithmetic functions is denoted A\mathcal{A}. Two arithmetic functions f,gf, g are added and scaled pointwise:

(f+g)(n):=f(n)+g(n),(cf)(n):=c⋅f(n)(c∈C).(f+g)(n) := f(n) + g(n), \qquad (cf)(n) := c \cdot f(n) \quad (c \in \mathbb{C}).

Under these operations A\mathcal{A} is a C\mathbb{C}-vector space (indeed it is exactly the space of all functions Z+→C\mathbb{Z}^+ \to \mathbb{C}, so vector-space axioms are inherited directly from those of C\mathbb{C}). The definition imposes no continuity, no growth restriction, and no algebraic compatibility with multiplication of integers. Multiplicativity, when it is discussed, is an extra property that specific arithmetic functions may or may not possess — it is not part of the definition of "arithmetic function" itself.

Intuition

Think of an arithmetic function as an infinite table: row nn, entry f(n)f(n). The table has one row for every positive integer and can otherwise contain absolutely anything — a constant, a random-looking sequence, or (the interesting case) a value computed from how nn factors into primes. What makes number theory possible is that the specific tables arising from divisor-counting, factorization, and coprimality turn out to interact beautifully with multiplication of the inputs nn, even though the definition says nothing about multiplication at all. A helpful mental picture is to fix a small integer, say n=12=22⋅3n = 12 = 2^2 \cdot 3, and watch how several canonical arithmetic functions read off different pieces of the same factorization data: τ(12)\tau(12) counts its six divisors, σ(12)\sigma(12) adds them up, φ(12)\varphi(12) counts integers below 1212 coprime to it, μ(12)=0\mu(12) = 0 because 1212 has a squared prime factor, λ(12)=+1\lambda(12) = +1 because it has an even number of prime factors with multiplicity, and Λ(12)=0\Lambda(12) = 0 because 1212 is not a prime power. One integer, six numbers, one underlying structure: the prime factorization.

Figure
Six arithmetic functions evaluated at n = 12 = 2² · 3, all derived from the same factorization
n = 12 = 2² · 3 Divisors: 1, 2, 3, 4, 6, 12 τ(12) = 6 (number of divisors) σ(12) = 1+2+3+4+6+12 = 28 (sum of divisors) φ(12) = 4 (coprime residues: 1,5,7,11) μ(12) = 0 since 2² | 12 (squared prime factor) λ(12) = (−1)^Ω(12) = (−1)^3 = −1 Λ(12) = 0 since 12 is not a prime power

Notice the theme: every value is computed from the same factorization 12=22⋅3112 = 2^2\cdot 3^1, just read off in a different way — count the exponents-plus-one products, sum divisors, count coprime residues, detect square factors, count prime factors with sign, or detect prime-power status. This shared dependence on factorization is exactly what later analysis exploits when studying Multiplicative Functions and combining them via Dirichlet Convolution.

TheoremCanonical arithmetic functions and their prime-factorization formulas

Let nn be a positive integer with prime factorization

n=p1a1p2a2⋯pkak,p1<p2<⋯<pk primes, ai≥1,n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}, \qquad p_1 < p_2 < \cdots < p_k \text{ primes}, \ a_i \ge 1,

(with the convention that n=1n=1 corresponds to the empty product, k=0k=0). Define the following arithmetic functions: 1. Divisor function τ(n)\tau(n): the number of positive divisors of nn. 2. Sum-of-divisors function σ(n)\sigma(n): the sum of the positive divisors of nn. 3. Euler's totient φ(n)\varphi(n): the number of integers mm with 1≤m≤n1 \le m \le n and gcd⁡(m,n)=1\gcd(m,n) = 1. 4. Möbius function μ(n)\mu(n): defined by μ(1)=1\mu(1) = 1; μ(n)=0\mu(n) = 0 if nn has a square factor >1> 1; and μ(n)=(−1)k\mu(n) = (-1)^k if n=p1p2⋯pkn = p_1 p_2 \cdots p_k is a product of kk distinct primes. 5. Liouville function λ(n)\lambda(n): defined by λ(n)=(−1)Ω(n)\lambda(n) = (-1)^{\Omega(n)}, where Ω(n)=a1+a2+⋯+ak\Omega(n) = a_1 + a_2 + \cdots + a_k is the number of prime factors of nn counted with multiplicity (Ω(1)=0\Omega(1) = 0). 6. Von Mangoldt function Λ(n)\Lambda(n): defined by Λ(n)=log⁡p\Lambda(n) = \log p if n=pan = p^a for some prime pp and integer a≥1a \ge 1, and Λ(n)=0\Lambda(n) = 0 otherwise. Then, for n=p1a1⋯pkak>1n = p_1^{a_1}\cdots p_k^{a_k} > 1:

τ(n)=∏i=1k(ai+1),σ(n)=∏i=1kpiai+1−1pi−1,\tau(n) = \prod_{i=1}^{k} (a_i + 1), \qquad \sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1}-1}{p_i - 1},
φ(n)=n∏i=1k(1−1pi),\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right),

and τ(1)=σ(1)=φ(1)=1\tau(1) = \sigma(1) = \varphi(1) = 1.

Proof

We prove the three closed formulas in turn, each by directly analyzing divisors of nn via unique factorization. Throughout, n=p1a1⋯pkakn = p_1^{a_1}\cdots p_k^{a_k} is the prime factorization of n>1n>1 guaranteed to exist and be unique by the Fundamental Theorem of Arithmetic (an already-known prerequisite result, used here only as the basic fact that every integer >1>1 factors uniquely into primes up to order).

Step 1: Characterizing the divisors of nn. Claim: dd is a positive divisor of nn if and only if

d=p1b1p2b2⋯pkbkwith 0≤bi≤ai for each i.d = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k} \quad \text{with } 0 \le b_i \le a_i \text{ for each } i.

(⇐\Leftarrow) If dd has this form, then n/d=p1a1−b1⋯pkak−bkn/d = p_1^{a_1-b_1}\cdots p_k^{a_k - b_k} is a positive integer (each exponent ai−bi≥0a_i - b_i \ge 0), so d∣nd \mid n. (⇒\Rightarrow) Suppose d∣nd \mid n, so n=d⋅en = d \cdot e for some positive integer ee. Factor dd and ee into primes; by unique factorization, the multiset of prime factors of nn (namely p1p_1 with multiplicity a1a_1, ..., pkp_k with multiplicity aka_k) is the union of the multisets of prime factors of dd and ee. In particular, no prime other than p1,…,pkp_1,\dots,p_k can divide dd (else it would divide nn, contradicting the factorization of nn), and if pibip_i^{b_i} exactly divides dd then bi≤aib_i \le a_i, since the total multiplicity of pip_i across dd and ee must equal aia_i. This proves the claim.

Step 2: The divisor-counting formula for τ\tau. By Step 1, divisors of nn correspond bijectively to tuples (b1,…,bk)(b_1,\dots,b_k) with 0≤bi≤ai0 \le b_i \le a_i, via d↦(b1,…,bk)d \mapsto (b_1,\dots,b_k) recovering d=∏pibid = \prod p_i^{b_i}; this map is a bijection precisely because distinct tuples give distinct integers dd (again by uniqueness of factorization: two products ∏pibi≠∏pibi′\prod p_i^{b_i} \ne \prod p_i^{b_i'} whenever the exponent tuples differ). The number of such tuples is, by the multiplication principle (each bib_i independently ranges over ai+1a_i + 1 values 0,1,…,ai0,1,\dots,a_i):

τ(n)=∏i=1k(ai+1).\tau(n) = \prod_{i=1}^{k}(a_i+1).

For n=1n=1 the only divisor is 11 itself, so τ(1)=1\tau(1)=1, matching the empty product convention.

Step 3: The divisor-sum formula for σ\sigma. Using the same bijection, summing dd over all divisors is summing ∏ipibi\prod_i p_i^{b_i} over all tuples (b1,…,bk)(b_1,\dots,b_k) with 0≤bi≤ai0 \le b_i \le a_i. This sum factors as a product of independent sums, one per prime, because

∑0≤b1≤a1⋯∑0≤bk≤ak ∏i=1kpibi  =  ∏i=1k(∑bi=0aipibi),\sum_{0 \le b_1 \le a_1} \cdots \sum_{0 \le b_k \le a_k} \ \prod_{i=1}^k p_i^{b_i} \;=\; \prod_{i=1}^{k} \left( \sum_{b_i=0}^{a_i} p_i^{b_i} \right),

which is the standard distributive-law expansion of a product of sums into a sum of products (each term on the left, a specific choice of all bib_i's, appears exactly once on the right when the product is expanded). Each inner sum is a finite geometric series:

∑b=0aipib=piai+1−1pi−1\sum_{b=0}^{a_i} p_i^{b} = \frac{p_i^{a_i+1}-1}{p_i-1}

(valid since pi≥2>1p_i \ge 2 > 1, so the standard geometric series identity ∑b=0axb=xa+1−1x−1\sum_{b=0}^{a} x^b = \frac{x^{a+1}-1}{x-1} for x≠1x \ne 1 applies). Substituting gives

σ(n)=∏i=1kpiai+1−1pi−1.\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1}-1}{p_i-1}.

For n=1n=1, σ(1)=1\sigma(1)=1 trivially (only divisor is 11).

Step 4: The totient formula for φ\varphi, via inclusion–exclusion. We count integers m∈{1,…,n}m \in \{1,\dots,n\} with gcd⁡(m,n)=1\gcd(m,n)=1. By definition of gcd and the prime factorization of nn, gcd⁡(m,n)>1\gcd(m,n) > 1 if and only if mm shares at least one of the primes p1,…,pkp_1,\dots,p_k with nn, i.e. pi∣mp_i \mid m for some ii. So

φ(n)=n−#{m∈{1,…,n}:∃i, pi∣m}=#{1,…,n}∖⋃i=1kSi,\varphi(n) = n - \#\{ m \in \{1,\dots,n\} : \exists i,\ p_i \mid m \} = \# \{1,\dots,n\} \setminus \bigcup_{i=1}^k S_i,

where Si={m∈{1,…,n}:pi∣m}S_i = \{ m \in \{1,\dots,n\} : p_i \mid m \}. Since pi∣np_i \mid n, exactly n/pin/p_i multiples of pip_i lie in {1,…,n}\{1,\dots,n\}, so ∣Si∣=n/pi|S_i| = n/p_i. More generally, for any subset I⊆{1,…,k}I \subseteq \{1,\dots,k\}, the integers in {1,…,n}\{1,\dots,n\} divisible by every pip_i with i∈Ii \in I are exactly the multiples of ∏i∈Ipi\prod_{i\in I} p_i (since the pip_i are distinct primes, divisibility by all of them is equivalent to divisibility by their product), and since ∏i∈Ipi\prod_{i \in I} p_i divides nn, there are exactly n/∏i∈Ipin / \prod_{i\in I} p_i such multiples in {1,…,n}\{1,\dots,n\}. By the inclusion–exclusion principle applied to the sets S1,…,SkS_1,\dots,S_k:

∣⋃i=1kSi∣=∑∅≠I⊆{1,…,k}(−1)∣I∣+1n∏i∈Ipi.\left| \bigcup_{i=1}^k S_i \right| = \sum_{\emptyset \ne I \subseteq \{1,\dots,k\}} (-1)^{|I|+1} \frac{n}{\prod_{i \in I} p_i}.

Therefore

φ(n)=n−∑∅≠I(−1)∣I∣+1n∏i∈Ipi=∑I⊆{1,…,k}(−1)∣I∣n∏i∈Ipi\varphi(n) = n - \sum_{\emptyset \ne I} (-1)^{|I|+1} \frac{n}{\prod_{i\in I}p_i} = \sum_{I \subseteq \{1,\dots,k\}} (-1)^{|I|} \frac{n}{\prod_{i\in I}p_i}

(absorbing the I=∅I = \emptyset term, which contributes nn, and flipping signs to unify the summation over all subsets II). Now factor this sum over subsets as a product:

∑I⊆{1,…,k}(−1)∣I∣n∏i∈Ipi=n∏i=1k(1−1pi),\sum_{I \subseteq \{1,\dots,k\}} (-1)^{|I|} \frac{n}{\prod_{i \in I} p_i} = n \prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right),

again by the distributive expansion of a product of kk two-term factors (1−1pi)\left(1 - \tfrac{1}{p_i}\right) into a sum over all 2k2^k subsets II (choosing the "−1pi-\frac{1}{p_i}" term for i∈Ii \in I and the "11" term otherwise reproduces exactly the sign (−1)∣I∣(-1)^{|I|} and factor ∏i∈Ipi−1\prod_{i\in I} p_i^{-1}). Hence

φ(n)=n∏i=1k(1−1pi).\varphi(n) = n \prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right).

For n=1n=1 there are no primes pip_i to exclude, the empty product is 11, and indeed φ(1)=1\varphi(1) = 1 (only m=1m=1 in range, and gcd⁡(1,1)=1\gcd(1,1)=1). This completes the proof of all three closed formulas. The definitions of μ\mu, λ\lambda, Λ\Lambda stated in the theorem are formulas already given directly in terms of the prime factorization, requiring no further derivation — they are definitions, not consequences to be derived, and are recorded here precisely so that later results (multiplicativity of μ\mu and λ\lambda, the fundamental identity Λ=μ∗log⁡\Lambda = \mu * \log under Dirichlet convolution) have an unambiguous starting point. ■\blacksquare

∎

Worked examples

Example 1: n=360n = 360. Factor 360=23⋅32⋅51360 = 2^3 \cdot 3^2 \cdot 5^1, so k=3k=3 with (p1,a1)=(2,3)(p_1,a_1)=(2,3), (p2,a2)=(3,2)(p_2,a_2)=(3,2), (p3,a3)=(5,1)(p_3,a_3)=(5,1). Divisor count. By the theorem,

τ(360)=(3+1)(2+1)(1+1)=4⋅3⋅2=24.\tau(360) = (3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2 = 24.

Check by direct listing: the divisors of 360360 are

1,2,3,4,5,6,8,9,10,12,15,18,20,24,30,36,40,45,60,72,90,120,180,360,1,2,3,4,5,6,8,9,10,12,15,18,20,24,30,36,40,45,60,72,90,120,180,360,

and counting gives exactly 2424 entries, confirming the formula. Sum of divisors.

σ(360)=24−12−1⋅33−13−1⋅52−15−1=151⋅262⋅244=15⋅13⋅6=1170.\sigma(360) = \frac{2^4-1}{2-1}\cdot\frac{3^3-1}{3-1}\cdot\frac{5^2-1}{5-1} = \frac{15}{1}\cdot\frac{26}{2}\cdot\frac{24}{4} = 15 \cdot 13 \cdot 6 = 1170.

As a sanity check, summing the 2424 divisors listed above:

1+2+3+4+5+6+8+9+10+12+15+18+20+24+30+36+40+45+60+72+90+120+180+360=1170,1+2+3+4+5+6+8+9+10+12+15+18+20+24+30+36+40+45+60+72+90+120+180+360 = 1170,

which matches. Totient.

φ(360)=360(1−12)(1−13)(1−15)=360⋅12⋅23⋅45=360⋅830=96.\varphi(360) = 360\left(1-\tfrac12\right)\left(1-\tfrac13\right)\left(1-\tfrac15\right) = 360 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 360 \cdot \frac{8}{30} = 96.

Möbius, Liouville, von Mangoldt. Since 360=23⋅32⋅5360 = 2^3\cdot 3^2\cdot 5 has a squared prime factor (232^3, in particular already 22∣3602^2 \mid 360), μ(360)=0\mu(360) = 0. Since Ω(360)=3+2+1=6\Omega(360) = 3+2+1 = 6 is even, λ(360)=(−1)6=1\lambda(360) = (-1)^6 = 1. Since 360360 is not a prime power (it has three distinct prime factors), Λ(360)=0\Lambda(360) = 0.

Example 2: n=1,001=7⋅11⋅13n = 1{,}001 = 7 \cdot 11 \cdot 13. This is a product of three distinct primes, each to the first power, so k=3k=3, all ai=1a_i=1. Divisor count. τ(1001)=(1+1)(1+1)(1+1)=8\tau(1001) = (1+1)(1+1)(1+1) = 8. Direct check: divisors are 1,7,11,13,77,91,143,10011,7,11,13,77,91,143,1001 — exactly 88 numbers. Sum of divisors.

σ(1001)=72−16⋅112−110⋅132−112=486⋅12010⋅16812=8⋅12⋅14=1344.\sigma(1001) = \frac{7^2-1}{6}\cdot\frac{11^2-1}{10}\cdot\frac{13^2-1}{12} = \frac{48}{6}\cdot\frac{120}{10}\cdot\frac{168}{12} = 8 \cdot 12 \cdot 14 = 1344.

Direct check: 1+7+11+13+77+91+143+1001=13441+7+11+13+77+91+143+1001 = 1344. ✓. Totient.

φ(1001)=1001(1−17)(1−111)(1−113)=1001⋅67⋅1011⋅1213.\varphi(1001) = 1001\left(1-\tfrac17\right)\left(1-\tfrac1{11}\right)\left(1-\tfrac1{13}\right) = 1001 \cdot \frac{6}{7}\cdot\frac{10}{11}\cdot\frac{12}{13}.

Compute stepwise: 1001/7=1431001/7 = 143, so first factor gives 143⋅6=858143 \cdot 6 = 858. Then 858/11=78858/11 = 78, so 78⋅10=78078 \cdot 10 = 780. Then 780/13=60780/13 = 60, so 60⋅12=72060 \cdot 12 = 720. Hence φ(1001)=720\varphi(1001) = 720. Möbius, Liouville, von Mangoldt. Since 10011001 is squarefree with k=3k=3 distinct prime factors, μ(1001)=(−1)3=−1\mu(1001) = (-1)^3 = -1. Since Ω(1001)=1+1+1=3\Omega(1001) = 1+1+1 = 3 is odd, λ(1001)=−1\lambda(1001) = -1 (agreeing with μ(1001)\mu(1001) here, as always happens for squarefree nn, since then Ω(n)=k\Omega(n)=k). Since 10011001 has three distinct prime factors, it is not a prime power, so Λ(1001)=0\Lambda(1001) = 0. These two examples deliberately use non-symmetric, composite factorizations (different exponents, different prime patterns) so that every step of the formulas — the geometric series in σ\sigma, the subtraction pattern in φ\varphi, the case distinctions in μ,λ,Λ\mu,\lambda,\Lambda — is genuinely exercised rather than trivialized.

CounterexampleWhy the prime factorization must be used correctly — dropping distinctness of primes in the totient formula

The formula

φ(n)=n∏p∣n(1−1p)\varphi(n) = n\prod_{p \mid n} \left(1 - \frac1p\right)

is proved above by summing over primes p1,…,pkp_1,\dots,p_k that are pairwise distinct divisors of nn; the inclusion–exclusion argument in Step 4 crucially uses that ∏i∈Ipi\prod_{i \in I} p_i correctly counts multiples divisible by all pi,i∈Ip_i, i\in I simultaneously, which requires the pip_i to be distinct primes (so that "divisible by the product" is equivalent to "divisible by each factor"). If one instead — incorrectly — tries to run the same product formula using the prime factorization with multiplicity, i.e. using each prime factor listed aia_i times instead of once, the formula breaks down. Concretely take n=8=23n = 8 = 2^3. The correct formula (using the distinct prime 22 once) gives

φ(8)=8(1−12)=4,\varphi(8) = 8\left(1-\tfrac12\right) = 4,

which matches direct counting: among 1,…,81,\dots,8, the integers coprime to 88 are 1,3,5,71,3,5,7, so φ(8)=4\varphi(8)=4. But if one mistakenly used the multiplicity-repeated "factorization" 2,2,22,2,2 (treating each of the three copies of the prime 22 as contributing its own factor (1−12)(1-\tfrac12)), one would compute

8(1−12)3=8⋅18=1,8\left(1-\tfrac12\right)^3 = 8 \cdot \frac18 = 1,

which is wrong — it does not equal 44. This shows the hypothesis "p1,…,pkp_1,\dots,p_k are the distinct primes dividing nn" in the theorem is not a cosmetic bookkeeping choice: dropping distinctness and instead ranging over prime factors with multiplicity gives a genuinely false formula, because the inclusion–exclusion count of multiples of a squared prime power like 4=224 = 2^2 inside {1,…,8}\{1,\dots,8\} is not the same as counting multiples of 22 twice independently — sets SiS_i built from repeated copies of the same prime are not distinct events that combine multiplicatively in the inclusion–exclusion sense used in the proof.

Scope, edge cases & common traps

SituationWhat to watch for
n=1n = 1Empty product convention: τ(1)=σ(1)=φ(1)=1\tau(1)=\sigma(1)=\varphi(1)=1, μ(1)=1\mu(1)=1, λ(1)=1\lambda(1)=1 (Ω(1)=0\Omega(1)=0), Λ(1)=0\Lambda(1)=0 (not a prime power).
nn primeτ(p)=2\tau(p)=2, σ(p)=p+1\sigma(p)=p+1, φ(p)=p−1\varphi(p)=p-1, μ(p)=−1\mu(p)=-1, λ(p)=−1\lambda(p)=-1, Λ(p)=log⁡p\Lambda(p)=\log p.
nn squarefreeμ(n)=λ(n)=(−1)k\mu(n) = \lambda(n) = (-1)^{k} where kk is the number of prime factors (they coincide exactly when nn is squarefree, since then Ω(n)=k\Omega(n)=k).
nn has a squared prime factorμ(n)=0\mu(n)=0 always; λ(n)\lambda(n) is still generally nonzero (it only depends on parity of Ω(n)\Omega(n), not on repetition).
nn a prime power pap^a, a≥2a\ge2Λ(n)=log⁡p≠0\Lambda(n) = \log p \ne 0 even though nn is not prime — a frequent point of confusion, since Λ\Lambda detects prime powers, not primes.
Confusing μ\mu and λ\lambdaThey agree on squarefree nn but differ once a square factor appears: μ(4)=0\mu(4)=0 but λ(4)=(−1)2=1\lambda(4)=(-1)^2=1.

The mathematician behind it

Origins · 1 minLeonhard Euler and how this was discovered
LE
Leonhard Euler
1707–1783 · 18th-century analytic and elementary number theory

Euler is the figure most responsible for introducing systematic arithmetic functions into number theory, most notably his totient function φ(n)\varphi(n), which he used in generalizing Fermat's Little Theorem to composite moduli. His work established the pattern — factor an integer, extract a number from the factorization, study how that number behaves — that this entire branch of number theory still follows.

History
- 1640: Fermat states his "Little Theorem" for prime moduli, the special case Euler later generalizes.
- 1736: Euler proves a form of Fermat's Little Theorem using early divisibility arguments.
- 1760s: Euler introduces and studies the totient function φ(n)\varphi(n) systematically, proving the product formula over distinct prime factors.
- 1832: Möbius introduces the function μ(n)\mu(n) in connection with inversion formulas for sums over divisors.
- 1919: Ramanujan and others develop deeper analytic techniques (Ramanujan sums) built on these same canonical arithmetic functions.
Is every arithmetic function required to be multiplicative?

No. The definition of an arithmetic function only requires it to be a function from Z+\mathbb{Z}^+ to C\mathbb{C}; nothing about how it interacts with products of integers is assumed. Multiplicativity — the property that f(mn)=f(m)f(n)f(mn) = f(m)f(n) whenever gcd⁡(m,n)=1\gcd(m,n)=1 — is a separate, extra structural property that some arithmetic functions (like τ\tau, σ\sigma, φ\varphi, μ\mu, λ\lambda) happen to satisfy and others do not. Recognizing which functions are multiplicative, and why, is the subject of a later, dedicated treatment; here the point is only that the raw definition is deliberately unconstrained, so that all these functions and many "badly behaved" ones (for instance f(n)=nf(n) = n's digit sum) fall under the same umbrella term.

Why does μ(n) = 0 whenever n has a squared prime factor?

This is simply part of the definition of μ\mu, not a derived fact requiring separate proof, but its motivation comes from Möbius inversion, where μ\mu is engineered to make certain divisor sums telescope to zero except in a single case. Concretely, if p2∣np^2 \mid n for some prime pp, the theorem's definition assigns μ(n)=0\mu(n)=0 directly; there is no computation to do — one only needs to detect whether nn's factorization has any exponent ai≥2a_i \ge 2. This is different from τ,σ,φ\tau,\sigma,\varphi, whose values are always positive integers computed by a formula; μ\mu instead only ever takes the three values −1,0,1-1,0,1, and the value 00 acts as a flag for "non-squarefree."

What is the difference between μ(n) and λ(n)?

Both depend on the prime factorization of nn and both take values in {−1,0,1}\{-1,0,1\} conceptually, but λ(n)=(−1)Ω(n)\lambda(n) = (-1)^{\Omega(n)} never actually equals 00 — it always equals ±1\pm 1, because Ω(n)\Omega(n) (prime factors counted with multiplicity) is always a well-defined nonnegative integer. By contrast μ(n)\mu(n) equals 00 whenever nn has any repeated prime factor. They agree exactly on squarefree integers, since there Ω(n)\Omega(n) equals the number of distinct prime factors kk, matching the exponent in μ(n)=(−1)k\mu(n)=(-1)^k. On non-squarefree integers they diverge: e.g. μ(12)=0\mu(12)=0 but λ(12)=(−1)3=−1\lambda(12) = (-1)^3 = -1.

Why is Λ(n) defined using log p rather than just an indicator of prime powers?

The choice of log⁡p\log p (rather than, say, the constant 11) is designed so that Λ\Lambda interacts correctly with the logarithm of nn under Dirichlet convolution, giving the clean identity ∑d∣nΛ(d)=log⁡n\sum_{d \mid n} \Lambda(d) = \log n. This identity, provable directly from unique factorization, is the reason Λ\Lambda becomes indispensable in the analytic proof of the Prime Number Theorem: it converts additive information about log⁡n\log n into a divisor-sum that isolates prime-power locations. Without the logarithmic weighting, one would only get a cruder "prime power indicator" function, losing this convolution identity and its analytic consequences entirely.

Can two different-looking arithmetic functions be equal as functions?

Yes, and this is a common point of confusion: two arithmetic functions are equal (as elements of A\mathcal{A}) precisely when they agree at every positive integer nn, regardless of how differently their defining formulas are written. For instance, μ(n)\mu(n) and λ(n)\lambda(n) are different functions in general (they disagree at n=12n=12, for instance) but agree at every squarefree nn; this is a partial, not total, equality. Establishing full equality of two arithmetic functions in general requires either a direct term-by-term proof for every nn, or an identity provable via Dirichlet convolution / generating function techniques, covered under Dirichlet Convolution.

Does the formula for σ(n) only work when n is a prime power?

No — the formula σ(n)=∏ipiai+1−1pi−1\sigma(n) = \prod_i \frac{p_i^{a_i+1}-1}{p_i-1} works for any positive integer n>1n>1 with prime factorization n=p1a1⋯pkakn=p_1^{a_1}\cdots p_k^{a_k}, including nn with many distinct prime factors, as proved in Step 3 above using the distributive expansion of a product of independent geometric sums. It happens to specialize, when k=1k=1 (i.e. n=pan=p^a is a prime power), to the single geometric series pa+1−1p−1\frac{p^{a+1}-1}{p-1}, but the general multi-prime case is the actual content of the theorem, verified explicitly for n=360n=360 (three distinct primes) and n=1001n=1001 (three distinct primes, all exponent 11) above.

Is τ(n) ever equal to n itself, and what does that reveal about the definition?

Only for n=1n=1 (where τ(1)=1=n\tau(1)=1=n) and n=2n=2 (where τ(2)=2=n\tau(2)=2=n); for every n≥3n \ge 3, τ(n)<n\tau(n) < n because τ(n)\tau(n) counts divisors while nn has at least n−2n-2 non-divisors among {1,…,n}\{1,\ldots,n\} once n≥3n\ge3, and in fact the growth rate of τ(n)\tau(n) is known to be far smaller than nn on average (its average order is log⁡n\log n, a fact from analytic number theory building on these same definitions). This illustrates a broader point: while an arithmetic function's definition imposes no growth restriction whatsoever, the canonical examples introduced here turn out, upon further study, to have very specific, provable growth behaviors — a phenomenon investigated once the algebraic tools of multiplicative functions and Dirichlet convolution are available.

Where this leads