1.13: The Functions σ and τ

Definition \(\PageIndex{1}\)

For \(n>0\) define: \[\begin{aligned} \tau(n) &=\text{the number of positive divisors of }n, \\ \sigma(n) &=\text{the sum of the positive divisors of }n.\end{aligned}\]

Example \(\PageIndex{1}\)

\(12=3\cdot 2^2\) has positive divisors \[1,2,3,4,6,12.\nonumber\] Hence \[\tau(12)=6\nonumber\] and \[\sigma(12)=1+2+3+4+6+12=28.\nonumber\]

Definition \(\PageIndex{2}\): Proper Divisor

A positive divisor \(d\) of \(n\) is said to be a proper divisor of \(n\) if \(d<n\). We denote the sum of all proper divisors of \(n\) by \(\sigma^\ast(n)\).

Note that if \(n\ge 2\) then \[\sigma^\ast(n)=\sigma(n)-n.\nonumber\]

Example \(\PageIndex{2}\)

\(\sigma^\ast(12)=16\).

Definition \(\PageIndex{3}\): Perfect

\(n>1\) is perfect if \(\sigma^\ast(n)=n\).

Example \(\PageIndex{3}\)

The proper divisors of \(6\) are \(1\), \(2\) and \(3\). So \(\sigma^\ast(6)=6\). Therefore \(6\) is perfect.

Exercise \(\PageIndex{1}\)

Prove that \(28\) is perfect.

The next theorem shows a simple way to compute \(\sigma(n)\) and \(\tau(n)\) from the prime factorization of \(n\).

Theorem \(\PageIndex{1}\)

Let \[n=p_1^{e_1}p_2^{e_2}\dotsm p_r^{e_r},\quad r\ge 1,\nonumber\] where \(p_1<p_2<\dotsb<p_r\) are primes and \(e_i\ge 0\) for each \(i\in\{1,2,\dotsc,r\}\). Then

1. \(\tau(n)=(e_1+1)(e_2+1)\dotsm(e_r+1)\)
2. \(\sigma(n)=\left(\dfrac{p_1^{e_1+1}-1}{p_1-1}\right)\left(\dfrac{p_2^{e_2+1}-1}{p_2-1}\right)\dotsm \left(\dfrac{p_r^{e_r+1}-1}{p_r-1}\right)\).

Proof

Proof of (1) From the Fundamental Theorem of Arithmetic every positive factor \(d\) of \(n\) will have its prime factors coming from those of \(n\). Hence \(d\mid n\) iff \(d=p_1^{f_1}p_2^{f_2}\dotsm p_r^{f_r}\) where for each \(i\): \[0\le f_i\le e_i.\nonumber\] That is, for each \(f_i\) we can choose a value in the set of \(e_i+1\) numbers \(\{0,1,2,\dotsc,e_i\}\). So, in all, there are \((e_1+1)(e_2+1)\dotsm(e_r+1)\) choices for the exponents \(f_1,f_2,\dotsc,f_r\). So (1) holds.

Proof of (2) We first establish two lemmas, Lemma \(\PageIndex{1}\) and Lemma \(\PageIndex{2}\).

Let \(n=p_1^{e_1}p_2^{e_2}\dotsm p_r^{e_r}\). Our proof is by induction on \(r\). If \(r=1\), \(n=p_1^{e_1}\) and the result follows from Lemma \(\PageIndex{2}\). Suppose the result is true when \(1\le r\le k\). Consider now the case \(r=k+1\). That is, let \[n=p_1^{e_1}\dotsm p_k^{e_k}p_{k+1}^{e_{k+1}}\nonumber\] where the primes \(p_1,\dotsc,p_k,p_{k+1}\) are distinct and \(e_i\ge 0\). Let \(a=p_1^{e_1}\dotsm p_k^{e_k}\), \(b=p_{k+1}^{e_{k+1}}\). Clearly \(\gcd(a,b)=1\). So by Lemma \(\PageIndex{1}\) we have \(\sigma(n)=\sigma(a)\sigma(b)\). By the induction hypothesis \[\sigma(a)=\left(\frac{p_1^{e_1+1}-1}{p_1-1}\right)\dotsm\left(\frac{p_k^{e_k+1}-1}{p_k-1}\right)\nonumber\] and by Lemma \(\PageIndex{2}\) \[\sigma(b)=\frac{p_{k+1}^{e_{k+1}+1}-1}{p_{k+1}-1}\nonumber\] and it follows that \[\sigma(n)=\left(\frac{p_1^{e_1+1}-1}{p_1-1}\right)\dotsm\left(\frac{p_{k+1}^{e_{k+1}+1}-1}{p_{k+1}-1}\right).\nonumber\] So the result holds for \(r=k+1\). By PMI it holds for \(r\ge 1\).

Before proving this let’s look at an example. Take \(n=72=8\cdot 9=2^3\cdot 3^2\). The theorem says \[\begin{aligned} \tau(72) &=(3+1)(2+1)=12 \\ \sigma(72) &=\left(\frac{2^4-1}{2-1}\right)\left(\frac{3^3-1}{3-1}\right)=15\cdot 13=195.\end{aligned}\]

Lemma \(\PageIndex{1}\)

Let \(n=ab\) where \(a>0\), \(b>0\) and \(\gcd(a,b)=1\). Then \(\sigma(n)=\sigma(a)\sigma(b)\).

Proof

Since \(a\) and \(b\) have only \(1\) as a common factor, using the Fundamental Theorem of Arithmetic it is easy to see that \(d\mid ab\Leftrightarrow d=d_1d_2\) where \(d_1\mid a\) and \(d_2\mid b\). That is, the divisors of \(ab\) are products of the divisors of \(a\) and the divisors of \(b\). Let \[1,a_1,\dotsc,a_s\nonumber\] denote the divisors of \(a\) and let \[1,b_1,\dotsc,b_t\nonumber \] denote the divisors of \(b\). Then \[\begin{aligned} \sigma(a) &=1+a_1+a_2+\dots b+a_s, \\ \sigma(b) &=1+b_1+b_2+\dots b+b_t.\end{aligned}\] The divisors of \(n=ab\) can be listed as follows \[\begin{gathered} 1,b_1,b_2,\dots c,b_t, \\ a_1\cdot 1, a_1\cdot b_1, a_1\cdot b_2,\dots c, a_1\cdot b_t, \\ a_2\cdot 1, a_2\cdot b_1, a_2\cdot b_2,\dots c, a_2\cdot b_t, \\ \vdots \\ a_s\cdot 1, a_s\cdot b_1, a_s\cdot b_2,\dots c, a_s\cdot b_t.\end{gathered}\] It is important to note that since \(gcd(a,b)=1\), \(a_ib_j = a_kb_\ell\) implies that \(a_i=a_k\) and \(b_j=b_\ell\). That is there are no repetitions in the above array.

If we sum each row we get \[\begin{gathered} 1+b_1+\dots b+b_t=\sigma(b) \\ a_11+a_1b_1+\dots b+a_1b_t=a_1\sigma(b) \\ \vdots \\ a_s\cdot 1+a_sb_1+\dots b+a_sb_t=a_s\sigma(b).\end{gathered}\] By adding these partial sums together we get \[\begin{split} \sigma(n) &=\sigma(b)+a_1\sigma(b)+a_2\sigma(b)+\dots b+a_3\sigma(b) \\ &=(1+a_1+a_2+\dots b+a_s)\sigma(b) \\ &=\sigma(a)\sigma(b). \end{split}\] This proves the lemma.

Lemma \(\PageIndex{2}\)

If \(p\) is a prime and \(k\ge 0\) we have \[\sigma(p^k)=\frac{p^{k+1}-1}{p-1}.\nonumber\]

Proof

Since \(p\) is prime, the divisors of \(p^k\) are \(1,p,p^2,\dotsc,p^k\). Hence \[\sigma(p^k)=1+p+p^2+\dotsb+p^k=\frac{p^{k+1}-1}{p-1},\nonumber\] as desired.

Exercise \(\PageIndex{2}\)

Find \(\sigma(n)\) and \(\tau(n)\) for the following values of \(n\).

1. \(n=900\)
2. \(n=496\)
3. \(n=32\)
4. \(n=128\)
5. \(n=1024\)

Exercise \(\PageIndex{3}\)

Determine which (if any) of the numbers in Exercise \(\PageIndex{2}\) are perfect.

Exercise \(\PageIndex{4}\)

Does Lemma \(\PageIndex{1}\) hold if we replace \(\sigma\) by \(\sigma^\ast\)?

Answer

The answer is no, but find explicit numbers \(a\) and \(b\) such that the result fails yet \(\gcd(a,b)=1\).