Exercise 4.2.21* ($\phi(n) + \sigma(n) \geq 2n$)

Proof.

(a)

If $n=1$, then $\varphi (n)+\sigma (n)=2=2n$. Suppose now that $n>1$, and consider the set $$\begin{array}{llll}\hfill A& =\{k\in [[1,n]]\mid k\wedge n>1\},& \hfill & \end{array}$$

and for every divisor $d$ of $n$,

$$\begin{array}{llll}\hfill A_d& =\{k\in [[1,n]]\mid k\wedge n=d\}.& \hfill & \end{array}$$

Then

$$A=\underset{d\mid n,d\ne 1}{\bigcup }{A}_d,\text{(disjoint union)}.$$

Therefore

$$|A|=\underset{d\mid n,d\ne 1}{\sum }|A_d|.$$

By definition, $\varphi (n)$ is the cardinality of the set $\{k\in [[1,n]]\mid k\wedge n=1\}$, which is the complementary set of $A$ in $[[1,n]]$, therefore

$$|A|=n-\varphi (n).$$

Moreover, $A_d$ is included in the set of multiples $\mathit{jd}$ of $d$ in $[[1,n]]$, so

$$A_d\subseteq \left\{d,2d,\dots ,\left(\frac{n}{d}\right)d\right\}.$$

Therefore

$$|A_d|\le \frac{n}{d},$$

so

$$\begin{array}{llllll}\hfill n-\varphi (n)& \le \underset{d\mid n,d\ne 1}{\sum }\frac{n}{d}& \hfill & & \hfill & \\ \hfill & =\underset{\delta \mid n,\delta \ne n}{\sum }\delta & \hfill (\delta =n∕d)& & \hfill & & \hfill \\ \hfill & =\sigma (n)-n.& \hfill & & \hfill & \end{array}$$

In conclusion, for all $n\ge 1$,

$$\varphi (n)+\sigma (n)\ge 2n.$$

(b)

If $n=1$, then $\varphi (n)+\sigma (n)=2=2n$, and if $n=p$ is a prime, $$\varphi (p)+\sigma (p)=p-1+p+1=2p.$$

Conversely, suppose that $\varphi (n)+\sigma (n)=2n$. Then $n-\varphi (n)=\sigma (n)-n$, so the inequalities of part (a)

$$n-\varphi (n)=|A|=\underset{d\mid n,d\ne 1}{\sum }|A_d|\le \underset{d\mid n,d\ne 1}{\sum }\frac{n}{d}=\sigma (n)-n$$

are equalities:

$$n-\varphi (n)=|A|=\underset{d\mid n,d\ne 1}{\sum }|A_d|=\underset{d\mid n,d\ne 1}{\sum }\frac{n}{d}=\sigma (n)-n.$$

Since $|A_d|\le \frac{n}{d}$, for every $d\mid n$, $d\ne 1$, $|A_d|=\frac{n}{d}$, where $A_d\subseteq \left\{d,2d,\dots ,\left(\frac{n}{d}\right)d\right\}$, thus

Assume, for the sake of contradiction, that $n>1$ is composite. Then $n$ has a divisor $d$ such that $d\ne 1,d\ne n$. Then $n=\left(\frac{n}{d}\right)d\in A_d$, thus by definition of $A_d$, $n=n\wedge n=d$. Since $d\ne n$, this is a contradiction. Therefore $n=1$ or $n$ is a prime.

For any positive integer $n$, $\varphi (n)+\sigma (n)\ge 2n$, with equality if and only if $n=1$ or $n$ is a prime. □