1.15: Number Theoretic Functions
- Page ID
- 93798
We will return to the Mersenne primes in the next chapter. Before we do, we introduce a few concepts that will be helpful both then and later in the text.
The prime-counting function \(\pi(x)\) appearing in the Prime Number Theorem (Theorem 1.11.3) and the prime-generating functions imagined and studied in Section 1.14 are by no means the only functions studied in number theory. Mathematicians through history have profitably looked at several additional functions tied to our key questions about the integers. In this chapter we introduce three of these. Though their definitions may seem a bit strange at first, hopefully the results of this chapter and the exercises that follow will convince you that their properties are interesting enough to make studying these functions worthwhile.
Functions related to divisors
We start with two functions related to the positive divisors of an integer \(n\).
For each integer \(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}\]
The integer \(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 \]
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 \]
Carrying our last example further, \[\sigma^\ast(12)=16.\nonumber \]
The next theorem shows a simple way to compute \(\sigma(n)\) and \(\tau(n)\) from the prime factorization of \(n\).
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
- \(\tau(n)=(e_1+1)(e_2+1)\dotsm(e_r+1)\);
- \(\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
(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\) if and only if \(d=p_1^{f_1}p_2^{f_2}\dotsm p_r^{f_r}\) for some integer exponents \(f_i\) 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\), and by the Fundamental Theorem of Arithmetic, each set of choices yields a different factor. So (1) holds.
To prove (2), we first establish two lemmas.
Before proving this let’s look at an example. Take \(n=72=8\cdot 9=2^3\cdot 3^2\). The theorem says that \[\begin{aligned} \tau(72) &=(3+1)(2+1)=12 \qquad \text{and}\\ \sigma(72) &=\left(\frac{2^4-1}{2-1}\right)\left(\frac{3^3-1}{3-1}\right)=15\cdot 13=195.\end{aligned}\] You can compute \(\tau(72)\) and \(\sigma(72)\) from their original definitions to verify that these results are correct (and much quicker to compute!).
Let \(n=ab\) where \(a,b>0\) and \(\gcd(a,b)=1\). Then \(\sigma(n)=\sigma(a)\sigma(b)\).
Proof
Since \(a\) and \(b\) have only \(1\) as a positive 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+\dotsb+a_s, \\ \sigma(b) &=1+b_1+b_2+\dotsb+b_t.\end{aligned}\] The divisors of \(n=ab\) can be listed as follows \[\begin{gathered} 1,b_1,b_2,\dotsc,b_t, \\ a_1\cdot 1, a_1\cdot b_1, a_1\cdot b_2,\dotsc, a_1\cdot b_t, \\ a_2\cdot 1, a_2\cdot b_1, a_2\cdot b_2,\dotsc, a_2\cdot b_t, \\ \vdots \\ a_s\cdot 1, a_s\cdot b_1, a_s\cdot b_2,\dotsc, 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+\dotsb+b_t=\sigma(b) \\ a_11+a_1b_1+\dotsb+a_1b_t=a_1\sigma(b) \\ \vdots \\ a_s\cdot 1+a_sb_1+\dotsb+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)+\dotsb+a_3\sigma(b) \\ &=(1+a_1+a_2+\dotsb+a_s)\sigma(b) \\ &=\sigma(a)\sigma(b). \end{split}\] This proves the lemma.
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\). A standard formula for geometric series yields \[\sigma(p^k)=1+p+p^2+\dotsb+p^k=\frac{p^{k+1}-1}{p-1},\nonumber \] as desired.
Proof
(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\).
The functions \(\sigma(n)\) and \(\sigma^*(n)\) will appear in the next chapter as we introduce perfect numbers. Additional properties of \(\tau(n)\) and \(\sigma(n)\) are discussed in the exercises.
Euler’s totient function
The final function we will introduce in this chapter is known as Euler’s phi-function, or the Euler totient function. As opposed to \(\tau\) and \(\sigma\), which dealt with divisors of their input, \(\phi\) will deal with numbers that have no prime factor in common with \(n\).
If \(X\) is a set, the number of elements in \(X\) is denoted by \(|X|\).
For example, \(|\{1\}|=1\) and \(|\{0,1,3,9\}|=4\).
If \(m\ge 1\), the Euler totient function of \(n\) is defined by \[\phi(n)=|\{i\in\mathbb{Z}\mid 1\le i\le n\text{ and }\gcd(i,n)=1\}|.\nonumber \]
At first glance, \(\phi(n)\) may seem tedious to calculate. For instance, in order to compute \(\phi(1000)\), would a person need to list all numbers relatively prime to 1000 and then count them?
Fortunately, the following theorems show that once the prime factorization of \(n\) is given, computing \(\phi(n)\) is easy.
If \(a>0\) and \(b>0\) and \(\gcd(a,b)=1\), then \[\phi(ab)=\phi(a)\phi(b).\nonumber \]
If \(p\) is prime and \(n>0\) then \[\phi\left(p^n\right)=p^n-p^{n-1}.\nonumber \]
Let \(p_1,p_2,\dotsc,p_k\) be distinct primes and let \(n_1,n_2,\dotsc,n_k\) be positive integers, then \[\phi\left(p_1^{n_1}p_2^{n_2}\dotsm p_k^{n_k}\right)=\left(p_1^{n_1}-p_1^{n_1-1}\right)\dotsm\left(p_k^{n_k}-p_k^{n_k-1}\right).\nonumber \]
Before discussing the proofs of these three theorems, let’s illustrate their use:
\[\begin{gathered} \phi(12)=\phi\left(2^2\cdot 3\right)=\left(2^2-2^1\right)\left(3^1-3^0\right)=2\cdot 2=4 \\ \begin{split} \phi(9000)=\phi\left(2^3\cdot 5^3\cdot 3^2\right) &=\left(2^3-2^2\right)\left(5^3-5^2\right)\left(3^2-3^1\right) \\ &=4\cdot 100\cdot 6=2400. \end{split}\end{gathered}\]
Note that if \(p\) is any prime then \[\phi(p)=p-1.\nonumber \]
We will postpone a proof of Theorem \(\PageIndex{2}\) until Section 1.23. Here we give the proof of Theorem \(\PageIndex{3}\).
Proof
We want to count the number of elements in the set \(A=\{1,2,\dotsc,p^n\}\) that are relatively prime to \(p^n\). Let \(B\) be the set of elements of \(A\) that have a factor greater than \(1\) in common with \(A\). Note that if \(b\in B\) and \(\gcd\left(b,p^n\right)=d>1\), then \(d\) is a factor of \(p^n\) and \(d>1\) so \(d\) has \(p\) as a factor. Hence \(b=pk\), for some \(k\), and \(p\le b\le p^n\), so \(p\le kp\le p^n\). It follows that \(1\le k\le p^{n-1}\). That is, \[B=\left\{p,2p,3p,\dotsc,kp,\dotsc,p^{n-1}p\right\}.\nonumber \] We are interested in the number of elements of \(A\) not in \(B\). Since \(|A|=p^n\) and \(|B|=p^{n-1}\), this number is \(p^n-p^{n-1}\). That is, \(\phi\left(p^n\right)=p^n-p^{n-1}\).
The proof of Theorem \(\PageIndex{4}\) follows from Theorems \(\PageIndex{2}\) and \(\PageIndex{3}\). The proof is by induction on \(n\) and is quite similar to the proof of Theorem \(\PageIndex{1}\)(2), so we omit the details. Other properties of the \(\phi\)-function are developed in the exercises.
Multiplicative functions
The functions \(\tau\), \(\sigma\), and \(\phi\) all have a common property, shown in Theorem \(\PageIndex{1}\), Lemma \(\PageIndex{1}\), and Theorem \(\PageIndex{2}\).
A function \(f(n)\) defined for positive integers \(n\) is called multiplicative if \(f(ab)=f(a)f(b)\) whenever \(\gcd(a,b)=1\).
From the results mentioned above, \(\tau\), \(\sigma\), and \(\phi\) are all multiplicative functions. If you are so inclined, do some additional reading on your own to learn about several pleasing properties that multiplicative functions have in common; it will be worth the effort!
Some final words
Later studies in number theory will lead you into greater depth with \(\tau\), \(\sigma\), and \(\phi\), as well as with the prime-counting function \(\pi\), and will introduce you to still other functions satisfying remarkable properties. Though we will say little more in this book about number theoretic functions,\(^{1}\) we finish our discussion with an intriguing unsolved problem in number theory.
In 1907 Robert Carmichael announced that he had proved the following statement:
For every positive integer n there exists a different positive integer \(m\) for which \(\phi(n)=\phi(m)\).
In other words, Carmichael’s statement is that if we were to list \(\phi(n)\) for all positive integers \(n\), each value would show up at least twice; every integer shares its \(\phi\)-value with at least one other integer.
Unfortunately, Carmichael’s proof was faulty, and today the conjecture still has not been proved true (or disproved!). In 1998 Kevin Ford proved that if Carmichael’s conjecture is not true, then the the smallest counterexample (i.e., the smallest number \(n\) such that no other number has the same \(\phi\)-value as \(n\)) must be larger than \(10^{10^{10}}\). That’s huge! On the other hand, mathematicians have shown that if any counterexample exists, then there are infinitely many counterexamples.
You can find more about Carmichael’s conjecture with a quick internet or library search. Happy reading!
Exercises
Find \(\sigma(n)\) and \(\tau(n)\) for the following values of \(n\).
- \(n=900\)
- \(n=496\)
- \(n=32\)
- \(n=128\)
- \(n=1024\)
Does Lemma \(\PageIndex{1}\) hold if we replace \(\sigma\) by \(\sigma^\ast\)?
(Hint: The answer is no, but find explicit numbers \(a\) and \(b\) such that the result fails yet \(\gcd(a,b)=1\).)
Prove that \(\tau(n)\) is odd if and only if \(n\) is a square.
Prove that \(\displaystyle\prod_{d|n} d = n^{\tau(n)/2}\), where the product is over all positive divisors \(d\) of \(n\).
Observe that \(n=30\) can be written in multiple ways as the sum of one or more consecutive positive integers: \[30, \qquad 9+10+11, \qquad 6+7+8+9, \qquad 4+5+6+7+8.\nonumber \] Show that for every positive integer \(n\), if \(n=2^p q\), where \(p \geq 0\) and \(q\) is odd, then \(\tau(q)\) is the number of ways that \(n\) can be written as the sum of a sequence of consecutive integers.
(Hint: For multiple values of \(n\), try looking at all the ways that \(n\) can be written as a sum of consecutive positive integers. Try to match different sums up with different divisors of \(q\) in a way that always works, no matter what \(n\) is.)
Show that if \[m=p_1^{n_1}p_2^{n_2}\dotsm p_k^{n_k}\nonumber \] where \(p_1,\dotsc,p_k\) are distinct primes and each \(n_i\ge 1\), then \[\phi(m)=m\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\dotsm\left(1-\frac1{p_k}\right).\nonumber \]
Prove that \(\phi(n)\) is even for all positive integers \(n\) other than 1 or 2.
Determine, with proof, all numbers \(n\) such that
- \(\phi(n)=2\)
- \(\phi(n)=4\)
- \(\phi(n)=6\)
Prove that if \(\phi(n) \mid (n-1)\), then no prime appears more than once in the prime factorization of \(n\).
Let \[S(n) = \sum_{d \mid n} \phi(d),\nonumber \] i.e., \(S(n)\) is the sum of the values we get when we evaluate \(\phi(d)\) for all positive divisors \(d\) of \(n\). For example, \[S(4)=\phi(1)+\phi(2)+\phi(4)=1+1+2=4,\quad\text{and}\nonumber\] \[S(15)=\phi(1)+\phi(3)+\phi(5)+\phi(15)=1+2+4+18=15.\nonumber\]
Compute \(S(n)\) for \(1 \leq n \leq 10\) and conjecture\(^{2}\) a formula for \(S(n)\).
For each function below, decide whether the function is multiplicative or not. (Assume that functions are defined on the set of positive integers.)
- \(f(n) = 1\)
- \(f(n) = n\)
- \(f(n) = 1+n\)
- \(f(n) = \log(n)\)
- \(f(n) = 2^n\)
- \(f(n) = 1/n\)
For positive integers \(n\), define the function \(\rho\) by \[\rho(n) = \text{the number of prime factors of}\;n;\nonumber \] for example, \(\rho(4)=1\) (since 4 is divisible by 2 and no other prime) and \(\rho(100)=2\) (since 100 is divisible by 2 and 5 and no other prime).
- Is the function \(\rho(n)\) multiplicative? Explain why or why not.
- Is the function \(f(n) = (-1)^{\rho(n)}\) multiplicative? Explain why or why not.
Show that for any positive integers \(a\) and \(b\), if \(f\) is a multiplicative function, then \(f(a)\cdot f(b) = f(\gcd(a,b)) \cdot f(\operatorname{lcm}(a,b))\).