Chapter 6 Number Theoretic Functions
Definition 6.0.1.
Any function \(f:\mathbb{N}\rightarrow\mathbb{C}\) is said to be an arithmetic function (or a number-theoretic function).
Example 6.0.2.
Consider the function \(\Omega:\mathbb{N}\rightarrow\mathbb{N}\cup\{0\}, \) defined by \(\Omega(n) =k_1 + k_2 +\cdots+ k_r,\) where \(n = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}\) is the prime factorization of \(n.\) \(\Omega(n)\) is the number of prime factors of \(n\) with multiplicity. This is an arithmetic function, since \(\mathbb{N}\cup\{0\} \subset \mathbb{C}.\)
A similar function is the function \(\omega:\mathbb{N}\rightarrow\mathbb{N}\cup\{0\},\) defined by \(\omega(n) = r,\) where \(n = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}\) is the prime factorization of \(n.\) \(\omega(n)\) is the number of distinct prime factors of \(n.\)
Definition 6.0.3.
Denote by \(\varphi(n),\) the number of positive integers \(k\) less than or equal to \(n\) such that \(\gcd(k, n) = 1;\) that is, the number of relatively prime integers between \(1\) and \(n.\) By convention, we define \(\omega(1) = 1.\) This function is called the Euler phi-function (or totient function).
Example 6.0.4.
Consider the first few natural numbers.
Remark 6.0.5.
It is easy to see by the definitions that \(\varphi(n)\) is the number of invertible elements in \(\mathbb{Z}_n.\)