The Central Idea
An arithmetic function is a function whose input is a positive integer and whose output records some arithmetic property of that integer.
Symbolically,
\[ \boxed{f:\mathbb Z_{>0}\to\mathbb C} \]is a common general form, although many elementary arithmetic functions take integer values.
Examples include functions that count divisors, sum divisors, count relatively prime integers, or indicate whether a number has a certain divisibility property.
Patterns Before Functions
Arithmetic functions often formalize patterns already visible in the integers.
Examples include:
- even and odd numbers alternating;
- multiples of \(3\) appearing every third integer;
- prime numbers occurring irregularly but infinitely often;
- perfect squares having an odd number of positive divisors;
- divisor counts depending on prime exponents;
- totient values depending on which primes divide the input.
Parity as an Integer Pattern
Every integer belongs to exactly one of two congruence classes modulo \(2\):
\[ n\equiv0\pmod2 \]or
\[ n\equiv1\pmod2. \]These are the even and odd integers.
The pattern repeats every two steps.
Multiples as Periodic Patterns
Multiples of a positive integer \(m\) occur at regular intervals:
\[ \ldots,-2m,-m,0,m,2m,3m,\ldots \]Equivalently,
\[ n\equiv0\pmod m \]identifies the multiples of \(m\).
This turns divisibility into a periodic modular pattern.
Prime Numbers Produce a Different Pattern
Prime numbers do not occur at a fixed interval.
The sequence begins
\[ 2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ldots \]The gaps vary.
Even though the distribution is not periodic, prime numbers control the multiplicative structure of every positive integer greater than \(1\).
Prime Factorization as Structural Data
Suppose
\[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}. \]This factorization records the prime building blocks of \(n\).
Many arithmetic functions can be computed directly from the primes \(p_i\) and their exponents \(a_i\).
The Divisor-Count Function
Let
\[ \tau(n) \]denote the number of positive divisors of \(n\).
This function is also commonly written
\[ d(n). \]If
\[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \]then
\[ \boxed{ \tau(n)=(a_1+1)(a_2+1)\cdots(a_k+1) }. \]Why the Divisor-Count Formula Works
A positive divisor of
\[ n=p_1^{a_1}\cdots p_k^{a_k} \]may use
\[ p_i^0,p_i^1,\ldots,p_i^{a_i} \]for each prime \(p_i\).
Thus there are
\[ a_i+1 \]choices for the exponent of each prime.
The multiplication principle gives the total number of divisors.
Example: Counting Divisors
Factor
\[ 360=2^3\cdot3^2\cdot5. \]Therefore,
\[ \tau(360) = (3+1)(2+1)(1+1) = 4\cdot3\cdot2. \]Hence
\[ \boxed{\tau(360)=24}. \]Prime Numbers Through \(\tau\)
A positive integer \(p>1\) is prime exactly when it has two positive divisors.
Therefore,
\[ \boxed{ p\text{ is prime} \iff \tau(p)=2 }. \]This gives an arithmetic-function characterization of primality.
Perfect Squares and Odd Divisor Counts
Most divisors occur in pairs:
\[ d \qquad\text{and}\qquad \frac{n}{d}. \]A divisor pairs with itself only when
\[ d^2=n. \]Therefore,
\[ \boxed{ n\text{ is a perfect square} \iff \tau(n)\text{ is odd} }. \]Prime-Exponent View of the Square Pattern
If
\[ n=p_1^{a_1}\cdots p_k^{a_k}, \]then
\[ \tau(n)=(a_1+1)\cdots(a_k+1). \]This product is odd exactly when every
\[ a_i+1 \]is odd, which means every \(a_i\) is even.
But having all even prime exponents is exactly the condition for \(n\) to be a perfect square.
The Divisor-Sum Function
Let
\[ \sigma(n) \]denote the sum of the positive divisors of \(n\).
For example, the positive divisors of \(12\) are
\[ 1,\ 2,\ 3,\ 4,\ 6,\ 12. \]Therefore,
\[ \sigma(12)=1+2+3+4+6+12=28. \]Thus
\[ \boxed{\sigma(12)=28}. \]Divisor Sum for a Prime Power
If \(p\) is prime, then the positive divisors of \(p^a\) are
\[ 1,p,p^2,\ldots,p^a. \]Therefore,
\[ \boxed{ \sigma(p^a) = 1+p+p^2+\cdots+p^a }. \]This is a finite geometric series.
Geometric-Series Form
For prime \(p\),
\[ 1+p+p^2+\cdots+p^a = \frac{p^{a+1}-1}{p-1}. \]Therefore,
\[ \boxed{ \sigma(p^a) = \frac{p^{a+1}-1}{p-1} }. \]Divisor Sum from Prime Factorization
If
\[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \]then
\[ \boxed{ \sigma(n) = \prod_{i=1}^{k} \left( 1+p_i+p_i^2+\cdots+p_i^{a_i} \right) }. \]Each factor chooses the exponent of one prime in a divisor.
Example: \(\sigma(18)\)
Factor
\[ 18=2\cdot3^2. \]Then
\[ \sigma(18) = (1+2)(1+3+3^2). \]Therefore,
\[ \sigma(18) = 3(13) = 39. \]Thus
\[ \boxed{\sigma(18)=39}. \]Proper Divisor Sum
The sum of the positive divisors of \(n\) excluding \(n\) itself is
\[ \boxed{\sigma(n)-n}. \]For example,
\[ \sigma(12)-12=28-12=16. \]Therefore the proper divisors of \(12\) sum to \(16\).
Perfect Numbers
A positive integer is called perfect when the sum of its proper positive divisors equals the number itself.
Equivalently,
\[ \boxed{\sigma(n)=2n}. \]For example, the proper divisors of \(6\) are
\[ 1,\ 2,\ 3, \]and
\[ 1+2+3=6. \]Therefore,
\[ \boxed{6\text{ is perfect}}. \]Deficient and Abundant Numbers
Comparing the sum of proper divisors with \(n\) creates two additional classifications.
A number is deficient when
\[ \sigma(n)-nA number is abundant when
\[ \sigma(n)>2n. \]Euler's Totient as an Arithmetic Function
The totient function
\[ \varphi(n) \]counts the positive integers from \(1\) through \(n\) that are relatively prime to \(n\).
For example,
\[ \varphi(10)=4 \]because
\[ 1,\ 3,\ 7,\ 9 \]are the positive integers at most \(10\) relatively prime to \(10\).
Totient from Prime Structure
If
\[ n=p_1^{a_1}\cdots p_k^{a_k}, \]then
\[ \boxed{ \varphi(n) = n \prod_{i=1}^{k} \left(1-\frac1{p_i}\right) }. \]The formula depends on which distinct primes divide \(n\).
Example: \(\varphi(60)\)
Factor
\[ 60=2^2\cdot3\cdot5. \]Then
\[ \varphi(60) = 60 \left(1-\frac12\right) \left(1-\frac13\right) \left(1-\frac15\right). \]Therefore,
\[ \varphi(60) = 60\cdot\frac12\cdot\frac23\cdot\frac45 = 16. \]Thus
\[ \boxed{\varphi(60)=16}. \]An Indicator Function
Arithmetic functions can also record whether a property is true.
For example, define
\[ I_2(n) = \begin{cases} 1,&2\mid n,\\ 0,&2\nmid n. \end{cases} \]This function identifies even integers.
It converts a yes-or-no divisibility property into numerical data.
The Möbius Function: A Gentle Introduction
One important arithmetic function is the Möbius function
\[ \mu(n). \]It is defined by prime-factor structure:
\[ \mu(n) = \begin{cases} 1,&n=1,\\ 0,&n\text{ is divisible by the square of a prime},\\ (-1)^k,&n\text{ is a product of }k\text{ distinct primes}. \end{cases} \]At this level, its value is useful mainly as an example of how a function can encode factorization structure.
Examples of the Möbius Function
Since
\[ 6=2\cdot3 \]is a product of two distinct primes,
\[ \boxed{\mu(6)=1}. \]Since
\[ 30=2\cdot3\cdot5 \]is a product of three distinct primes,
\[ \boxed{\mu(30)=-1}. \]Since
\[ 12=2^2\cdot3 \]contains a squared prime factor,
\[ \boxed{\mu(12)=0}. \]Multiplicative Arithmetic Functions
An arithmetic function \(f\) is called multiplicative when
\[ \boxed{ \gcd(a,b)=1 \implies f(ab)=f(a)f(b) }. \]The relative-primality condition is essential.
Many important number-theoretic functions are multiplicative, including \(\tau\), \(\sigma\), and \(\varphi\).
Example: Multiplicativity of \(\tau\)
Since
\[ \gcd(8,9)=1, \]multiplicativity gives
\[ \tau(72)=\tau(8)\tau(9). \]Now
\[ \tau(8)=4 \]and
\[ \tau(9)=3. \]Therefore,
\[ \boxed{\tau(72)=12}. \]Why Relative Primality Matters
Multiplicativity does not mean
\[ f(ab)=f(a)f(b) \]for every pair \(a,b\).
For example,
\[ \tau(4)=3, \qquad \tau(2)=2. \]But
\[ \tau(2)\tau(2)=4\neq3. \]The issue is that
\[ \gcd(2,2)\neq1. \]Example: Multiplicativity of \(\varphi\)
Since
\[ \gcd(8,9)=1, \]we have
\[ \varphi(72)=\varphi(8)\varphi(9). \]Now
\[ \varphi(8)=4 \]and
\[ \varphi(9)=6. \]Therefore,
\[ \boxed{\varphi(72)=24}. \]A Divisor-Sum Identity
The divisor-count function can be written as a sum over divisors:
\[ \boxed{ \tau(n)=\sum_{d\mid n}1 }. \]The notation
\[ \sum_{d\mid n} \]means “sum over all positive divisors \(d\) of \(n\).”
Since each divisor contributes \(1\), the sum simply counts them.
The Divisor-Sum Function in Summation Notation
Similarly,
\[ \boxed{ \sigma(n)=\sum_{d\mid n}d }. \]Each positive divisor contributes its own value.
This notation is compact and prepares for more advanced arithmetic identities.
Counting Prime Divisors
Two useful functions count prime factors in different ways.
Let
\[ \omega(n) \]count the number of distinct prime divisors of \(n\).
Let
\[ \Omega(n) \]count prime factors with multiplicity.
Example: \(\omega\) and \(\Omega\)
Consider
\[ 72=2^3\cdot3^2. \]There are two distinct prime divisors:
\[ 2,\ 3. \]Therefore,
\[ \boxed{\omega(72)=2}. \]Counting repeated prime factors gives
\[ 3+2=5, \]so
\[ \boxed{\Omega(72)=5}. \]Squarefree Integers
A positive integer is squarefree when no square of a prime divides it.
Equivalently, every exponent in its prime factorization is either \(0\) or \(1\).
For example,
\[ 30=2\cdot3\cdot5 \]is squarefree, while
\[ 12=2^2\cdot3 \]is not.
Prime-Factor Patterns and Squarefree Numbers
The Möbius function detects squarefree structure:
\[ \boxed{ \mu(n)\neq0 \iff n\text{ is squarefree} }. \]When \(n\) is squarefree,
\[ \mu(n)=(-1)^{\omega(n)}. \]Thus the sign depends on whether the number of distinct prime factors is even or odd.
Sequences Built from Arithmetic Functions
Evaluating an arithmetic function at consecutive positive integers creates a sequence.
For example,
\[ \tau(1),\tau(2),\tau(3),\tau(4),\tau(5),\ldots \]begins
\[ 1,\ 2,\ 2,\ 3,\ 2,\ 4,\ 2,\ 4,\ 3,\ldots \]This sequence records how divisor complexity changes from integer to integer.
Arithmetic Functions Need Not Be Monotonic
A larger input does not necessarily produce a larger output.
For example,
\[ \tau(12)=6, \]but
\[ \tau(13)=2. \]The function falls sharply even though the input increases.
Arithmetic functions often reflect factor structure rather than ordinary size.
Prime Inputs Often Simplify Formulas
If \(p\) is prime, then
\[ \tau(p)=2, \] \[ \sigma(p)=p+1, \] \[ \varphi(p)=p-1, \] \[ \omega(p)=1, \]and
\[ \Omega(p)=1. \]Prime numbers therefore provide especially simple test cases for many arithmetic functions.
Prime Powers Also Have Simple Structure
If \(p\) is prime, then for \(a\ge1\),
\[ \tau(p^a)=a+1, \] \[ \sigma(p^a)=1+p+\cdots+p^a, \] \[ \varphi(p^a)=p^a-p^{a-1}, \] \[ \omega(p^a)=1, \]and
\[ \Omega(p^a)=a. \]Prime-power cases reveal how exponent data controls arithmetic functions.
Integer Patterns from Modular Powers
Arithmetic patterns also appear in powers modulo a fixed integer.
For example, powers of \(2\) modulo \(5\) cycle:
\[ 2,\ 4,\ 3,\ 1,\ 2,\ 4,\ 3,\ 1,\ldots \]This pattern is governed by multiplicative structure in the residue classes modulo \(5\).
Digital Patterns as Modular Patterns
Last-digit patterns are residue patterns modulo \(10\).
For example, powers of \(3\) have last digits
\[ 3,\ 9,\ 7,\ 1,\ 3,\ 9,\ 7,\ 1,\ldots \]because the powers repeat modulo \(10\) with period \(4\).
Triangular Numbers and Divisibility Patterns
The \(n\)-th triangular number is
\[ T_n=\frac{n(n+1)}{2}. \]Because \(n\) and \(n+1\) are consecutive, one is always even.
Therefore,
\[ n(n+1) \]is always divisible by \(2\), making \(T_n\) an integer.
This illustrates how divisibility can prove that a formula always produces integers.
Sums of Consecutive Integers
Integer patterns often emerge from simple algebra.
The sum of two consecutive integers is
\[ n+(n+1)=2n+1, \]which is always odd.
The sum of three consecutive integers is
\[ n+(n+1)+(n+2)=3(n+1), \]which is always divisible by \(3\).
Products of Consecutive Integers
Among any \(m\) consecutive integers, one is divisible by \(m\).
Therefore the product of \(m\) consecutive integers is divisible by \(m\).
For example,
\[ n(n+1)(n+2) \]is always divisible by \(3\).
It is also divisible by \(2\), so
\[ \boxed{6\mid n(n+1)(n+2)}. \]Common Error: Confusing a Formula with an Arithmetic Function
An arithmetic function is defined by what it assigns to each positive integer.
The notation
\[ \tau(n) \]means “the number of positive divisors of \(n\),” not merely an algebraic expression to manipulate without reference to its definition.
Common Error: Using the Divisor-Count Formula Before Factoring Correctly
The formula
\[ \tau(n)=(a_1+1)\cdots(a_k+1) \]depends on the complete prime factorization
\[ n=p_1^{a_1}\cdots p_k^{a_k}. \]Missing a prime factor or using a composite base gives the wrong divisor count.
Common Error: Omitting the Divisor \(1\)
Both
\[ \tau(n) \]and
\[ \sigma(n) \]use all positive divisors, including \(1\) and \(n\).
Proper-divisor questions are different because they exclude \(n\).
Common Error: Assuming Multiplicative Means Fully Multiplicative
A multiplicative arithmetic function satisfies
\[ f(ab)=f(a)f(b) \]only when
\[ \gcd(a,b)=1. \]Do not omit the relative-primality condition.
Common Error: Expecting Smooth Growth
Arithmetic functions often fluctuate.
A number with many small prime factors may have a large divisor count, while a nearby prime has only two divisors.
Number-theoretic structure can matter more than numerical size.
A Reliable Procedure for Divisor-Count Problems
- Find the complete prime factorization of \(n\).
- Identify the exponents \(a_1,\ldots,a_k\).
- Add \(1\) to each exponent.
- Multiply the resulting values.
- Check the answer against a small divisor list when practical.
A Reliable Procedure for Divisor-Sum Problems
- Find the complete prime factorization of \(n\).
- For each prime power \(p^a\), form \(1+p+\cdots+p^a\).
- Multiply these geometric sums.
- If the proper-divisor sum is wanted, subtract \(n\).
- Check against a direct divisor list for small values.
A Reliable Procedure for Recognizing Multiplicative Structure
- Identify the arithmetic function involved.
- Check whether the inputs being separated are relatively prime.
- If they are, apply the multiplicative rule.
- If they are not, return to prime factorization or the function's direct formula.
- Verify that the result agrees with the structural definition.
Example: Full Arithmetic-Function Workflow
Let
\[ n=180. \]First factor:
\[ 180=2^2\cdot3^2\cdot5. \]The divisor count is
\[ \tau(180) = (2+1)(2+1)(1+1) = 18. \]Thus
\[ \boxed{\tau(180)=18}. \]Continuing the Workflow: Divisor Sum
Compute
\[ \sigma(180) = (1+2+4)(1+3+9)(1+5). \]Therefore,
\[ \sigma(180) = 7\cdot13\cdot6 = 546. \]Hence
\[ \boxed{\sigma(180)=546}. \]Continuing the Workflow: Totient
The distinct prime divisors are \(2\), \(3\), and \(5\).
\[ \varphi(180) = 180 \left(1-\frac12\right) \left(1-\frac13\right) \left(1-\frac15\right). \]Therefore,
\[ \varphi(180) = 180\cdot\frac12\cdot\frac23\cdot\frac45 = 48. \]Thus
\[ \boxed{\varphi(180)=48}. \]Continuing the Workflow: Prime-Factor Counts
Since
\[ 180=2^2\cdot3^2\cdot5, \]there are three distinct prime factors:
\[ \boxed{\omega(180)=3}. \]Counting multiplicity gives
\[ 2+2+1=5, \]so
\[ \boxed{\Omega(180)=5}. \]Practice 1: Divisor Count
Find
\[ \tau(72). \]Practice 2: Divisor Sum
Find
\[ \sigma(20). \]Practice 3: Proper Divisor Sum
Find the sum of the proper positive divisors of
\[ 28. \]Practice 4: Perfect Number
Use the divisor-sum function to verify that
\[ 28 \]is perfect.
Practice 5: Totient
Find
\[ \varphi(45). \]Practice 6: Prime-Factor Counts
For
\[ 360=2^3\cdot3^2\cdot5, \]find
\[ \omega(360) \]and
\[ \Omega(360). \]Practice 7: Möbius Values
Find
\[ \mu(10),\qquad \mu(18),\qquad \mu(30). \]Practice 8: Odd Divisor Count
Explain why
\[ 144 \]has an odd number of positive divisors.
Practice 9: Multiplicativity
Use multiplicativity to find
\[ \tau(50) \]from
\[ 50=2\cdot25. \]Practice 10: Integer Pattern
Prove that the sum of five consecutive integers is divisible by \(5\).
Practice Answers
Practice 1
\[ 72=2^3\cdot3^2. \]Therefore,
\[ \tau(72)=(3+1)(2+1)=12. \]Thus
\[ \boxed{\tau(72)=12}. \]Practice 2
\[ 20=2^2\cdot5. \]Therefore,
\[ \sigma(20) = (1+2+4)(1+5) = 7\cdot6 = 42. \]Thus
\[ \boxed{\sigma(20)=42}. \]Practice 3
The positive divisors of \(28\) are
\[ 1,\ 2,\ 4,\ 7,\ 14,\ 28. \]Therefore,
\[ \sigma(28)=56. \]The proper-divisor sum is
\[ 56-28=28. \]Thus
\[ \boxed{28}. \]Practice 4
Since
\[ \sigma(28)=56=2(28), \]we have
\[ \boxed{28\text{ is perfect}}. \]Practice 5
\[ 45=3^2\cdot5. \]Therefore,
\[ \varphi(45) = 45 \left(1-\frac13\right) \left(1-\frac15\right) = 24. \]Thus
\[ \boxed{\varphi(45)=24}. \]Practice 6
The distinct prime factors are
\[ 2,\ 3,\ 5, \]so
\[ \boxed{\omega(360)=3}. \]Counting multiplicity,
\[ 3+2+1=6, \]so
\[ \boxed{\Omega(360)=6}. \]Practice 7
Since
\[ 10=2\cdot5 \]is a product of two distinct primes,
\[ \boxed{\mu(10)=1}. \]Since
\[ 18=2\cdot3^2 \]contains a squared prime factor,
\[ \boxed{\mu(18)=0}. \]Since
\[ 30=2\cdot3\cdot5 \]is a product of three distinct primes,
\[ \boxed{\mu(30)=-1}. \]Practice 8
\[ 144=2^4\cdot3^2. \]Therefore,
\[ \tau(144) = (4+1)(2+1) = 15. \]The divisor count is odd. This agrees with the fact that
\[ 144=12^2 \]is a perfect square.
Practice 9
Since
\[ \gcd(2,25)=1, \]multiplicativity gives
\[ \tau(50)=\tau(2)\tau(25). \]Now
\[ \tau(2)=2 \]and
\[ \tau(25)=3. \]Therefore,
\[ \boxed{\tau(50)=6}. \]Practice 10
Let the five consecutive integers be
\[ n,\ n+1,\ n+2,\ n+3,\ n+4. \]Their sum is
\[ 5n+10. \]Factor:
\[ 5n+10=5(n+2). \]Therefore,
\[ \boxed{ 5\mid \bigl[n+(n+1)+(n+2)+(n+3)+(n+4)\bigr] }. \]What to Remember
- Arithmetic functions assign numerical information to positive integers.
- Prime factorization controls many arithmetic-function formulas.
- The divisor-count function satisfies \[ \tau(n)=\prod(a_i+1). \]
- The divisor-sum function satisfies \[ \sigma(n)=\prod(1+p_i+\cdots+p_i^{a_i}). \]
- The totient \(\varphi(n)\) counts positive integers up to \(n\) that are relatively prime to \(n\).
- Functions such as \(\tau\), \(\sigma\), and \(\varphi\) are multiplicative on relatively prime inputs.
- \(\omega(n)\) counts distinct prime factors, while \(\Omega(n)\) counts prime factors with multiplicity.
- Many integer patterns can be understood through divisibility, congruence, and prime-exponent structure.
The central structural lesson is: prime factorization turns many irregular-looking integer patterns into formulas that can be counted, summed, classified, and compared.
Where We Go Next
This lesson completes 4.6 Number Theory and Modular Structures. Across the section, divisibility led to primes and factorization, greatest common divisors led to the Euclidean Algorithm, congruence led to residue classes and linear congruences, and those tools supported Diophantine equations, Fermat and Euler relationships, and introductory cryptography.
The next section of Discrete and Stochastic Relationships can now build on this foundation whenever integer structure, modular cycles, arithmetic functions, or number-theoretic reasoning reappears.