Kvant Math Problem 967

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m20s
Source on kvant.digital

Problem

Let $\sigma(n)$ denote the sum of all positive divisors of the number $n$ (including $1$ and $n$), and let $\varphi(n)$ denote the number of integers less than $n$ that are relatively prime to it. Prove that for every positive integer $n\ge 2$, $$\sigma(n)+\varphi(n) \ge 2n.$$

V. F. Lev

Exploration

For small values,

$$n=2:\quad \sigma(2)+\varphi(2)=3+1=4=2n,$$

$$n=3:\quad \sigma(3)+\varphi(3)=4+2=6=2n,$$

$$n=4:\quad \sigma(4)+\varphi(4)=7+2=9>8,$$

$$n=6:\quad \sigma(6)+\varphi(6)=12+2=14>12.$$

The inequality is sharp for primes. This suggests that equality may occur exactly when $n$ is prime.

The quantity $\sigma(n)$ involves divisors, while $\varphi(n)$ counts integers relatively prime to $n$. A natural idea is to compare each separately with $n$.

For every divisor $d$ of $n$, the number $n/d$ is also a divisor. Pairing divisors in this way often yields estimates for $\sigma(n)$. Since every divisor is at least $1$,

$$\sigma(n)=\sum_{d\mid n} d =\sum_{d\mid n}\frac{n}{d} =n\sum_{d\mid n}\frac1d.$$

Because the divisors $1$ and $n$ always occur,

$$\sum_{d\mid n}\frac1d \ge 1+\frac1n,$$

hence

$$\sigma(n)\ge n+1.$$

For $\varphi(n)$, among the integers $1,2,\dots,n-1$, the number $1$ is always relatively prime to $n$, so

$$\varphi(n)\ge 1.$$

Adding these inequalities immediately gives

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

This is still weaker than the desired bound when $n>2$. Thus the previous estimate is insufficient.

A stronger relation is needed. The classical identity

$$\sum_{d\mid n}\varphi(d)=n$$

looks promising. Since every term is nonnegative,

$$n=\varphi(n)+\sum_{\substack{d\mid n\ d<n}}\varphi(d).$$

If the sum over proper divisors could be bounded by $\sigma(n)-n$, then the result would follow. Indeed, for every divisor $d$,

$$\varphi(d)\le d,$$

and for $d>1$ the inequality is strict. Therefore

$$\sum_{\substack{d\mid n\ d<n}}\varphi(d) \le \sum_{\substack{d\mid n\ d<n}} d =\sigma(n)-n.$$

Combining this with the identity for $\sum\varphi(d)$ yields exactly the desired inequality. The most delicate step is the use and proof of the identity

$$\sum_{d\mid n}\varphi(d)=n.$$

Problem Understanding

We must prove that for every integer $n\ge2$,

$$\sigma(n)+\varphi(n)\ge2n,$$

where $\sigma(n)$ is the sum of the positive divisors of $n$ and $\varphi(n)$ is Euler's totient function.

This is a Type B problem. The statement is already specified, so the task is to establish it rigorously.

The core difficulty is connecting two different arithmetic functions. The standard divisor-sum identity

$$\sum_{d\mid n}\varphi(d)=n$$

provides the bridge between them.

Proof Architecture

First prove the identity

$$\sum_{d\mid n}\varphi(d)=n.$$

The reason is that each integer $k$ with $1\le k\le n$ has a unique value of $\gcd(k,n)$, and grouping numbers according to this gcd counts exactly $\varphi(d)$ numbers for each divisor $d$.

Next show that for every positive integer $d$,

$$\varphi(d)\le d.$$

This holds because $\varphi(d)$ counts certain integers among $1,2,\dots,d$.

Then deduce

$$\sum_{\substack{d\mid n\ d<n}}\varphi(d) \le \sum_{\substack{d\mid n\ d<n}}d = \sigma(n)-n.$$

Finally substitute this estimate into the divisor-sum identity and rearrange.

The lemma most likely to fail under scrutiny is the identity

$$\sum_{d\mid n}\varphi(d)=n,$$

so it must be proved carefully.

Solution

Consider the integers

$$1,2,\dots,n.$$

For each divisor $e$ of $n$, let us count the numbers $k$ in this set satisfying

$$\gcd(k,n)=e.$$

Write $k=e t$. Since $e\mid n$, put

$$n=e m.$$

Then

$$\gcd(k,n)=e \iff \gcd(et,em)=e \iff \gcd(t,m)=1.$$

Also, because $1\le k\le n$,

$$1\le t\le m.$$

Hence the number of integers $k$ with $\gcd(k,n)=e$ equals the number of integers $t$ satisfying

$$1\le t\le m,\qquad \gcd(t,m)=1,$$

which is precisely $\varphi(m)=\varphi(n/e)$.

Summing over all divisors $e$ of $n$, every integer from $1$ to $n$ is counted exactly once, so

$$n=\sum_{e\mid n}\varphi!\left(\frac ne\right).$$

Replacing $n/e$ by a divisor variable $d$ gives

$$\sum_{d\mid n}\varphi(d)=n.$$

Now write

$$n=\varphi(n)+\sum_{\substack{d\mid n\ d<n}}\varphi(d).$$

For every positive integer $d$,

$$\varphi(d)\le d,$$

because $\varphi(d)$ counts some of the integers among $1,2,\dots,d$.

Therefore

$$\sum_{\substack{d\mid n\ d<n}}\varphi(d) \le \sum_{\substack{d\mid n\ d<n}} d = \sigma(n)-n.$$

Substituting into the previous identity yields

$$n = \varphi(n)+\sum_{\substack{d\mid n\ d<n}}\varphi(d) \le \varphi(n)+\sigma(n)-n.$$

Adding $n$ to both sides gives

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

Thus

$$\sigma(n)+\varphi(n)\ge2n$$

for every integer $n\ge2$.

This completes the proof.

∎

Verification of Key Steps

The identity

$$\sum_{d\mid n}\varphi(d)=n$$

depends on counting numbers with a prescribed gcd. If $\gcd(k,n)=e$, writing $k=et$ and $n=em$ gives

$$\gcd(t,m)=1.$$

The range $1\le t\le m$ is essential. It produces exactly $\varphi(m)$ admissible values of $t$, neither more nor fewer. Every integer $k$ belongs to exactly one gcd class because $\gcd(k,n)$ is uniquely determined.

The inequality

$$\sum_{\substack{d\mid n\ d<n}}\varphi(d) \le \sum_{\substack{d\mid n\ d<n}}d$$

uses only the termwise estimate $\varphi(d)\le d$. No cancellation is involved. A careless argument might replace $\varphi(d)$ by a stronger bound that fails for $d=1$. The inequality $\varphi(1)=1\le1$ remains valid, so every divisor contributes correctly.

After substitution one obtains

$$n\le \varphi(n)+\sigma(n)-n.$$

The final rearrangement is

$$2n\le \sigma(n)+\varphi(n),$$

which is exactly the required statement. No hidden assumption about primality or parity of $n$ enters the argument.

Alternative Approaches

Using the formula

$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$$

and

$$\sigma(n)=n\prod_{p^\alpha\parallel n} \left(1+\frac1p+\cdots+\frac1{p^\alpha}\right),$$

one can divide the desired inequality by $n$ and reduce it to

$$\prod_{p^\alpha\parallel n} \left(1+\frac1p+\cdots+\frac1{p^\alpha}\right) + \prod_{p\mid n} \left(1-\frac1p\right) \ge2.$$

A proof can then be obtained by estimating each factor and using induction on the number of distinct prime divisors. Such an approach is longer and requires careful multiplicative estimates.

The divisor-sum identity for $\varphi$ is preferable because it converts the problem into a direct comparison between $\varphi(d)$ and $d$ on proper divisors of $n$. The argument is short, transparent, and uses only one standard counting fact.