4.2: Multiplicative Number Theoretic Functions

Last updated
Save as PDF

Page ID: 8839

$Wissam_Raji.jpg$
Contributed by Wissam Raji
Associate Professor and the Chairman (Mathematics) at American University of Beirut

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

We now present several multiplicative number theoretic functions which will play a crucial role in many number theoretic results. We start by discussing the Euler phi-function which was defined in an earlier chapter. We then define the sum-of-divisors function and the number-of-divisors function along with their properties.

The Euler $\phi$-Function

As defined earlier, the Euler $\phi$-function counts the number of integers smaller than and relatively prime to a given integer. We first calculate the value of the $phi$-function at primes and prime powers.

If $p$ is prime, then $\phi(p)=p-1$. Conversely, if $p$ is an integer such that $\phi(p)=p-1$, then $p$ is prime.

The first part is obvious since every positive integer less than $p$ is relatively prime to $p$. Conversely, suppose that $p$ is not prime. Then $p=1$ or $p$ is a composite number. If $p=1$, then $\phi(p)\neq p-1$. Now if $p$ is composite, then $p$ has a positive divisor. Thus $\phi(p)\neq p-1$. We have a contradiction and thus $p$ is prime.

We now find the value of $\phi$ at prime powers.

Let $p$ be a prime and $m$ a positive integer, then $\phi(p^m)=p^m-p^{m-1}$.

Note that all integers that are relatively prime to $p^m$ and that are less than $p^m$ are those that are not multiple of $p$. Those integers are $p,2p,3p,...,p^{m-1}p$. There are $p^{m-1}$ of those integers that are not relatively prime to $p^m$ and that are less than $p^m$. Thus \[\phi(p^m)=p^m-p^{m-1}.\]

$\phi(7^3)=7^3-7^2=343-49=294$. Also $\phi(2^{10})=2^{10}-2^9=512.$

We now prove that $\phi$ is a multiplicative function.

Let $m$ and $n$ be two relatively prime positive integers. Then $\phi(mn)=\phi(m)\phi(n)$.

Denote $\phi(m)$ by $s$ and let $k_1,k_2,...,k_s$ be a reduced residue system modulo $m$. Similarly, denote $\phi(n)$ by $t$ and let $k_1',k_2',...,k_t'$ be a reduced residue system modulo $n$. Notice that if $x$ belongs to a reduced residue system modulo $mn$, then \[(x,m)=(x,n)=1.\] Thus \[x\equiv k_i(mod\ m) \mbox{and} \ \ x\equiv k_j'(mod \ n)\] for some $i,j$. Conversely, if \[x\equiv k_i(mod\ m) \mbox{and} \ \ x\equiv k_j'(mod \ n)\] some $i,j$ then $(x,mn)=1$ and thus $x$ belongs to a reduced residue system modulo $mn$. Thus a reduced residue system modulo $mn$ can be obtained by by determining all $x$ that are congruent to $k_i$ and $k_j'$ modulo $m$ and $n$ respectively. By the Chinese remainder theorem, the system of equations \[x\equiv k_i(mod\ m) \mbox{and} \ \ x\equiv k_j'(mod \ n)\] has a unique solution. Thus different $i$ and $j$ will yield different answers. Thus $\phi(mn)=st$.

We now derive a formula for $\phi(n)$.

Let $n=p_1^{a_1}p_2^{a_2}...p_s^{a_s}$ be the prime factorization of $n$. Then \[\phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_s}\right).\]

By Theorem 37, we can see that for all $1\leq i\leq k$ \[\phi(p_i^{a_i})=p_i^{a_i}-p_i^{a_i-1}=p_i^{a_i}\left(1-\frac{1}{p_i}\right).\] Thus by Theorem 38, \[\begin{aligned} \phi(n)&=&\phi(p_1^{a_1}p_2^{a_2}...p_s^{a_s})\\&=& \phi(p_1^{a_1})\phi(p_2^{a_2})...\phi(p_s^{a_s})\\&=&p_1^{a_1}\left(1-\frac{1}{p_1}\right) p_2^{a_2}\left(1-\frac{1}{p_2}\right)...p_s^{a_s}\left(1-\frac{1}{p_s}\right)\\&=& p_1^{a_1}p_2^{a_2}...p_k^{a_k}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)... \left(1-\frac{1}{p_s}\right)\\&=& n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_s}\right).\end{aligned}\]

Note that \[\phi(200)=\phi(2^35^2)=200\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=80.\]

Let $n$ be a positive integer greater than 2. Then $\phi(n)$ is even.

Let $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$. Since $\phi$ is multiplicative, then \[\phi(n)=\prod_{j=1}^k\phi(p_j^{a_j}).\] Thus by Theorem 39, we have \[\phi(p_j^{a_j})=p_j^{a_j-1-1}(p_j-1).\] We see then $\phi(p_j^{a_j})$is even if $p_j$ is an odd prime. Notice also that if $p_j=2$, then it follows that $\phi(p_j^{a_j})$ is even. Hence $\phi(n)$ is even.

Let $n$ be a positive integer. Then \[\sum_{d\mid n}\phi(d)=n.\]

Split the integers from 1 to $n$ into classes. Put an integer $m$ in the class $C_d$ if the greatest common divisor of $m$ and $n$ is $d$. Thus the number of integers in the $C_d$ class is the number of positive integers not exceeding $n/d$ that are relatively prime to n/d. Thus we have $\phi(n/d)$ integers in $C_d$. Thus we see that \[n=\sum_{d\mid n}\phi(n/d).\] As $d$ runs over all divisors of $n$, so does $n/d$. Hence \[n=\sum_{d\mid n}\phi(n/d)=\sum_{d\mid n}\phi(d).\]

The Sum-of-Divisors Function

The sum of divisors function, denoted by $\sigma(n)$, is the sum of all positive divisors of $n$.

$\sigma(12)=1+2+3+4+6+12=28.$

Note that we can express $\sigma(n)$ as $\sigma(n)=\sum_{d\mid n}d$.

We now prove that $\sigma(n)$ is a multiplicative function.

The sum of divisors function $\sigma(n)$ is multiplicative.

We have proved in Theorem 35 that the summatory function is multiplicative once $f$ is multiplicative. Thus let $f(n)=n$ and notice that $f(n)$ is multiplicative. As a result, $\sigma(n)$ is multiplicative.

Once we found out that $\sigma(n)$ is multiplicative, it remains to evaluate $\sigma(n)$ at powers of primes and hence we can derive a formula for its values at any positive integer.

Let $p$ be a prime and let $n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}$ be a positive integer. Then \[\sigma(p^a)=\frac{p^{a+1}-1}{p-1},\] and as a result, \[\sigma(n)=\prod_{j=1}^{t}\frac{p_j^{a_j+1}-1}{p_j-1}\]

Notice that the divisors of $p^{a}$ are $1,p,p^2,...,p^a$. Thus \[\sigma(p^a)=1+p+p^2+...+p^a=\frac{p^{a+1}-1}{p-1}.\] where the above sum is the sum of the terms of a geometric progression.

Now since $\sigma(n)$ is multiplicative, we have \[\begin{aligned} \sigma(n)&=&\sigma(p^{a_1})\sigma(p^{a_2})...\sigma(p^{a_t})\\&=& \frac{p_1^{a_1+1}-1}{p_1-1}.\frac{p_2^{a_2+1}-1}{p_2-1}...\frac{p_t^{a_t+1}-1}{p_t-1}\\ &=&\prod_{j=1}^{t}\frac{p_j^{a_j+1}-1}{p_j-1}\end{aligned}\]

$\sigma(200)=\sigma(2^35^2)=\frac{2^4-1}{2-1}\frac{5^3-1}{5-1}=15.31=465.$

The Number-of-Divisors Function

The number of divisors function, denoted by $\tau(n)$, is the sum of all positive divisors of $n$.

$\tau(8)=4.$

We can also express $\tau(n)$ as $\tau(n)=\sum_{d\mid n}1$.

We can also prove that $\tau(n)$ is a multiplicative function.

The number of divisors function $\tau(n)$ is multiplicative.

By Theorem 36, with $f(n)=1$, $\tau(n)$ is multiplicative.

We also find a formula that evaluates $\tau(n)$ for any integer $n$.

Let $p$ be a prime and let $n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}$ be a positive integer. Then \[\tau(p^a)=a+1,\] and as a result, \[\tau(n)=\prod_{j=1}^{t}(a_j+1).\]

The divisors of $p^{a}$ as mentioned before are $1,p,p^2,...,p^a$. Thus \[\tau(p^a)=a+1\]

Now since $\tau(n)$ is multiplicative, we have \[\begin{aligned} \tau(n)&=&\tau(p^{a_1})\tau(p^{a_2})...\tau(p^{a_t})\\&=& (a_1+1)(a_2+1)...(a_t+1)\\ &=&\prod_{j=1}^{t}(a_j+1).\end{aligned}\]

$\tau(200)=\tau(2^35^2)=(3+1)(2+1)=12$.

Exercises

Find $\phi(256)$ and $\phi(2.3.5.7.11)$.
Show that $\phi(5186)=\phi(5187)$.
Find all positive integers $n$ such that $\phi(n)=6$.
Show that if $n$ is a positive integer, then $\phi(2n)=\phi(n)$ if $n$ is odd.
Show that if $n$ is a positive integer, then $\phi(2n)=2\phi(n)$ if $n$ is even.
Show that if $n$ is an odd integer, then $\phi(4n)=2\phi(n)$.
Find the sum of positive integer divisors and the number of positive integer divisors of 35
Find the sum of positive integer divisors and the number of positive integer divisors of $2^53^45^37^313$.
Which positive integers have an odd number of positive divisors.
Which positive integers have exactly two positive divisors.

Contributors

Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.

The Euler \(\phi\)-Function

The Sum-of-Divisors Function

The Number-of-Divisors Function

Contributors