Find all positive integers $n$ such that $$\phi(n) + \sigma(n) = 2n + 8.$$
Problem
Source: KMO 2023 P5
Tags: number theory
04.11.2023 16:11
05.11.2023 18:35
Here is a slightly different approach: Note that $\varphi(n) \ge n-\sum_{p \mid n} \frac{n}{p}$ and $\sigma(n) \ge n+\sum_{p \mid n} \frac{n}{p}$ and hence $\varphi(n)+\sigma(n) \ge 2n$ with equality iff $n$ is prime. We are interested in almost-equality cases. If $n$ has three distinct prime divisors $p<q<r$, then $\sigma(n)$ exceeds the lower bound from above by at least $p+q+r>8$, no solution. If $n=p^k$, then $\varphi(n)+\sigma(n)=2n+p^{k-2}+p^{k-3}+\dots+p+1$, hence $p=7$ and $k=3$ and hence $n=343$. Finally, if $n=p^kq^{\ell}$, then both $\varphi(n)$ and $\sigma(n)$ exceed the lower bound above by at least $\frac{n}{pq}$, hence $p^{k-1}q^{\ell-1} \le 4$ and hence w.l.o.g. $\ell=1$, i.e. $n=p^kq$. But then we still get $p^{k-1} \le 4$ and hence either $k=3, p=2$ (which does not lead to a solution) or $k=1$ (which does not lead to a solution) or $k=2, p \le 3$, which leads to $q=3$ and hence the second solution $n=12$.
26.10.2024 19:43
Let $p_1, p_2, ... ,p_k$ be the prime divisors of $n$ and $t$ be the product of them. And let $m=n/t$. Then we can easily get $\sigma(m)-m \le 8$ by factorizing. Then just look at the cases?