I'm asked to find all integers $n$ such that $\phi(n)+\sigma(n)=2n.$ I know that when $n$ is a prime, $\phi(n)+\sigma(n)=(n-1)+(n+1)=2n.$ My guess is that $n$ can be primes only, and I want to derive a contradiction when $n$ is a composite number. But I can only show that when $n=pq$ ($p$, $q$ distinct primes), $\phi(n)+\sigma(n)=2pq+2=2n+2.$ How do I generalize from here?
Number Theory – Positive Integers n Such That ?(n) + ?(n) = 2n
arithmetic-functionsnumber theory
Related Solutions
Partial answer:
Lemma: Let $n=am+1$ where $a\ge1$ and $m\ge2$ are integers. Suppose that $m\mid\phi(n)$ and $a<p$ where $p=\min\{p^*\in\Bbb P:p^*\mid m\}$. If $n$ is not prime then either
$n$ is of the form $\prod p_i$ where $p_i$ are primes, or
$n$ is of the form $2^kr$ where $k,r$ are positive integers.
Proof: Suppose that $n$ is composite. First, note that $m$ must be odd as otherwise, $a=1$ which yields $n-1=m$. The condition $m\mid\phi(n)$ forces $n$ to be prime which is a contradiction.
Next, write $n=q^kr$ where $k,r$ are positive integers and $q$ is a prime such that $(q,r)=1$. As $\phi(n)=q^{k-1}(q-1)\phi(r)$ the condition $m\mid\phi(n)$ yields $$q^{k-1}(q-1)\phi(r)=mt\implies aq^{k-1}(q-1)\phi(r)=t(q^kr-1)$$ for some positive integer $t$. It follows that either $k=1$ or $t=q^{k-1}v$ for some integer $v\ne t$. In the latter case, we obtain $$\frac{q^kr-1}{q^{k-1}(q-1)\phi(r)}=\frac{aps}{mt}=\frac at\implies p>\frac{t(q^kr-1)}{q^{k-1}(q-1)\phi(r)}.$$ Combining this with the trivial result $p<q^{k-1}(q-1)\phi(r)/t$ yields $$t<\frac{q^{k-1}(q-1)\phi(r)}{\sqrt{q^kr-1}}\implies v<\frac{(q-1)\phi(r)}{\sqrt{q^kr-1}}.$$ Substituting back into $n=am+1$ gives $$q^kr-1=\frac av(q-1)\phi(r)\implies aq\phi(r)-vq^kr=a\phi(r)-v>\phi(r)\left(a-\frac{q-1}{\sqrt{q^kr-1}}\right)$$ which is positive since $k\ge2$. This yields $a>vq^{k-1}\ge vq$. Since $p$ is the least prime divisor of $m$, we have $p\le q-1$, unless $q=2$ or $q-1=v$.
Evidently, the first case contradicts $a<p$, so $k=1$. This means that $n$ must be of the form $\prod p_i$ where $p_i$ are primes. The condition $m\mid\phi(n)$ gives $\prod(p_i-1)=bm$ for some positive integer $b$, and substituting this into $n=am+1$ yields $$a=b\frac{\prod p_i-1}{\prod(p_i-1)}.$$ When $m$ is even, we have $a<p\implies a<2$ which implies that $m=\prod p_i-1$. Further, $$b<\frac{2\prod(p_i-1)}{\prod p_i-1}<2\implies m=\prod(p_i-1).$$ The only way that $\prod p_i-1=\prod(p_i-1)$ is when $\prod p_i$ is prime, which solves the problem. Finally, notice that $m$ is odd only when $b=2^{\nu_2(\prod(p_i-1))}d$ for some positive integer $d$, so the condition $a<p$ yields $$2^{\nu_2(\prod(p_i-1))}d\frac{\prod p_i-1}{\prod(p_i-1)}<\frac{p_j-1}{2^{\nu_2(p_j-1)}}$$ for some prime $p_j\mid\prod p_i$.
The second case $q=2$ implies that $n=2^kr=am+1$ where $m\mid\phi(r)$; that is, for some positive integer $g$ we have $g(2^kr-1)=a\phi(r)$.
The third case $q-1=v$ forces $m=\phi(r)$, so $m=1$. This is a contradiction as there is no prime $p$ that can divide $m$.
Best Answer
Start with the definitions of $\sigma$ and $\phi$:
$ \sigma(n) = \sum_{d \vert n}{d}$
$ \phi(n) = \prod_i{(p_i - 1) \cdot p_i^{e_i-1}} $
Expand the product and rewrite as:
$ \phi(n) = \sum_{d \vert n}{a_d \cdot d}$
with coefficients $a_d \in \{-1,0,1\}$. So now we have
$ \sigma(n) + \phi(n) = \sum_{d \vert n}{(a_d + 1) \cdot d} $
and since $a_n = 1$:
$ \sigma(n) + \phi(n) = 2 \cdot n + \sum_{d \vert n, d < n}{(a_d + 1) \cdot d}$
Now $\sigma(n) + \phi(n) = 2 \cdot n$ if and only if $a_d = -1$ for all proper divisors $d$. This is only true for prime $n$, and $n=1$. Otherwise some positive terms remain.