Section 2.1 Examples of arithmetic functions
Here are a number of arithmetic functions:
- \(\phi\) Euler totient: \(\phi(n)\) is the number of \(k\) such that \(1 \leq k \leq n\) and \((n,k)=1\)
- \(d(n)\text{:}\) number of positive divisors of \(n\text{.}\) \(d(n) = \sum_{k \mid n} 1\text{.}\) (This function is also often denoted \(\tau\text{.}\))
- \(\sigma\) sum of positive divisors of \(n\text{.}\) \(\sigma(n) = \sum_{k \mid n} k\text{.}\)
- \(1(n) = 1\) for all \(n\text{.}\) (In Crisman’s book this function was denoted \(u\text{.}\))
- \(N(n) = n\) for all \(n\)
- \(e(n) = \begin{cases} 1 \amp \text{if } n=1 \\ 0 \amp \text{otherwise } \end{cases} \text{.}\) (In Crisman’s book this function was denoted \(I\text{.}\))
- \(\sigma_s(n) = \sum_{k \mid n} k^s\text{.}\) So \(d = \sigma_0\text{,}\) \(\sigma = \sigma_1\text{.}\)
- Möbius function:\begin{equation} \mu(n) = \begin{cases} 1 \amp \text{if } n = 1 \\ (-1)^k \amp \text{if } n = p_1 \dotsm p_k, \text{ where } p_1,\dotsc,p_k \text{ are distinct primes} \\ 0 \amp \text{if } p^2 \mid n \text{ for some } p \end{cases}\tag{2.1.1} \end{equation}
- Liouville function:\begin{equation} \lambda(n) = (-1)^{a_1+\dotsb+a_k} \text{ where } n = p_1^{a_1} \dotsm p_k^{a_k} \tag{2.1.2} \end{equation}(In particular \(\lambda(1)=1\) as all \(a_i=0\text{.}\))
- Von Mangoldt function:\begin{equation} \Lambda(n) = \begin{cases} \log p \amp \text{if } n = p^k \text{ for some prime } p \\ 0 \amp \text{if } n \text{ is not a power of a prime} \end{cases} \tag{2.1.3} \end{equation}
- \(\omega(n)\text{:}\) number of distinct prime divisors of \(n\)
- \(\Omega(n)\text{:}\) number of prime divisors of \(n\) counted with multiplicity, i.e., \(\Omega(n) = \sum a_i\) where \(n = p_1^{a_1} \dotsm p_k^{a_k}\text{.}\)
Observe \(\lambda(n) = (-1)^{\Omega(n)}\text{.}\)
Think of the Von Mangoldt function as a modification of the prime indicator function. The prime indicator function is the function that equals \(1\) on primes, and \(0\) on non-primes. The Von Mangoldt function changes the value to \(\log p\) instead of \(1\text{,}\) and detects powers of primes along with the primes themselves.
Theorem 2.1.2.
For a prime \(p\) and \(k \geq 1\text{,}\) \(\phi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p})\text{.}\)Proof.
There are \(p^k / p = p^{k-1}\) multiples of \(p\) less than or equal to \(p^k\text{;}\) all other integers in the interval \([1,p^k]\) are coprime to \(p^k\text{.}\)Theorem 2.1.3.
For all \(n \geq 1\text{,}\) \(\sum_{d \mid n} \phi(d) = n\text{.}\)Proof.
Let \(d \mid n \text{.}\)
\begin{align*}
\phi(d) \amp = \# \{ k : 1 \leq k \leq d, (k,d)=1 \} \\
\amp = \# \{ k : \frac{n}{d} \leq k \frac{n}{d} \leq n, (k \frac{n}{d}, n) = \frac{n}{d} \} \\
\amp = \# \{ m : \frac{n}{d} \leq m \leq n, (m, n) = \frac{n}{d} \} \\
\amp = \# \{ m : 1 \leq m \leq n, (m,n) = \frac{n}{d} \} \text{.}
\end{align*}
So
\begin{align*}
\sum_{d \mid n} \phi(d) \amp = \sum_{d \mid n} \# \{ m : 1 \leq m \leq n, (m,n) = \frac{n}{d} \} \\
\amp = \# \bigcup_{d \mid n} \{ m : 1 \leq m \leq n, (m,n) = \frac{n}{d} \} \\
\amp = \# \{ m : 1 \leq m \leq n \} \\
\amp = n \text{.}
\end{align*}
We used that the union is disjoint. Next, every value \(1 \leq m \leq n\) has some gcd with \(n\text{,}\) and the gcd must be a divisor of \(n\text{.}\) As \(d\) runs through the divisors of \(n\text{,}\) so does \(n/d\text{.}\) This shows that the union is equal to the set of \(1 \leq m \leq n\text{.}\)
Remark 2.1.4.
Note that the sets \(\{k : 1 \leq k \leq d, (k,d)=1 \}\) are not at all disjoint; for example they all contain \(1\text{.}\)
Theorem 2.1.5.
- \(\displaystyle \phi(1) = 1\)
- \(\displaystyle \phi(p) = p-1\)
- \(\displaystyle \phi(p^k) = p^k - p^{k-1} = p ( 1 - \frac{1}{p})\)
- If \((m,n) = 1\) then \(\phi(mn) = \phi(m)\phi(n)\)
- \(\displaystyle \phi(n) = n \prod_{p \mid n} ( 1 - \frac{1}{p} )\)
Proof.
The first two are left as exercises. The numbers coprime to \(p^k\) are the non-multiples of \(p\text{.}\) There are \(p^k/p = p^{k-1}\) multiples of \(p\) in the interval \([1,p^k]\text{.}\)
The Chinese Remainder Theorem gives an isomorphism of rings \(\bbZ_{mn} \cong \bbZ_{m} \times \bbZ_{n}\text{.}\) Among other things, this gives an isomorphism of the groups of units (invertible elements):
\begin{equation*}
\bbZ_{mn}^\times \cong (\bbZ_m \times \bbZ_n)^\times
\cong \bbZ_m^{\times} \times \bbZ_n^{\times}\text{.}
\end{equation*}
(It is left as an exercise that for rings \(R,S\) in general, \((R \times S)^\times \cong R^\times \times S^\times\text{.}\)) Now \(\#(\bbZ_{mn}^\times) = \phi(mn)\text{,}\) and
\begin{equation*}
\#(\bbZ_m^\times \times \bbZ_n^\times)
= (\# \bbZ_m^\times) \cdot (\# \bbZ_n^\times)
= \phi(m) \phi(n)\text{.}
\end{equation*}
Finally for \(n = \prod p_i^{a_i}\) we have
\begin{equation*}
\phi(n) = \prod \phi(p_i^{a_i}) = \prod p_i^{a_i} ( 1 - \frac{1}{p_i} )
= n \prod ( 1 - \frac{1}{p_i} ).
\end{equation*}
