Arithmetic functions · Definition

Divisor functions

elementary number theoryarithmetic functions

Before you start you need to know

Divisor functions measure arithmetically how many divisors an integer has and how they are distributed. They are the most basic example of multiplicative arithmetic functions.

Definition

The divisor functions \( \sigma_k(n) \) and \( \tau(n) \) give, respectively, the sum of the \( k \)-th powers and the number of positive divisors of an integer \( n \geq 1 \).

\[\sigma_k(n)=\sum_{d\mid n} d^{k},\quad \tau(n)=\sigma_0(n)\]

If \( \gcd(m,n)=1 \), then \( \tau(mn)=\tau(m)\tau(n) \) and \( \sigma_k(mn)=\sigma_k(m)\sigma_k(n) \), so both functions are multiplicative. It therefore suffices to know their values at prime powers: \( \tau(p^a)=a+1 \) and \( \sigma_k(p^a)=1+p^k+\cdots+p^{ak} \).

For \( n=360=2^3\cdot 3^2\cdot 5 \) we get \( \tau(360)=4\cdot 3\cdot 2=24 \). Similarly, \( \sigma_1(360)=15\cdot 13\cdot 6=1170 \), using the prime-power formula for each factor.

A typical error is to assume \( \sigma_k(p^a)=(p^{k(a+1)}-1)/(p^k-1) \) without requiring \( p^k\neq 1 \), or to apply multiplicativity to sums such as \( \tau(m+n) \), which has no relation to \( \tau(m)\tau(n) \).

Think about it

Why does \( \tau(mn)=\tau(m)\tau(n) \) fail in general when \( \gcd(m,n)\neq 1 \)?

Because common divisors are counted differently: for example \( \tau(4)=3 \) but \( \tau(2)\tau(2)=4 \).

Exercises 10

  1. How many positive divisors does \( 12 \) have?
  2. Compute \( \sigma_1(6) \), the sum of the positive divisors of \( 6 \).
  3. State the formula for \( \tau(p^a) \) for a prime \( p \) and \( a\geq 0 \).
  4. What is \( \sigma_0(n) \) for any \( n\geq 1 \)?
  5. Compute \( \tau(7) \), where \( 7 \) is prime.
  6. Compute \( \tau(72) \) using the factorization \( 72=2^3\cdot 3^2 \).
  7. Compute \( \sigma_1(15) \) using that \( \sigma_1 \) is multiplicative.
  8. Compute \( \sigma_2(4) \), the sum of the squares of the positive divisors of \( 4 \).
  9. Let \( n=2^4\cdot 3^2 \). Compute \( \tau(n^2) \) and compare it with \( \tau(n)^2 \). Are they equal?
  10. Prove or disprove: if \( \tau(m)=\tau(n) \) for positive integers \( m,n \), then \( m=n \). Give a counterexample if it is false.

What comes next

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 6
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 4