For every positive integer $n$, let $\sigma(n)$ denote the sum of all positive divisors of $n$ ($1$ and $n$, inclusive). Show that a positive integer $n$, which has at most two distinct prime factors, satisfies the condition $\sigma(n)=2n-2$ if and only if $n=2^k(2^{k+1}+1)$, where $k$ is a non-negative integer and $2^{k+1}+1$ is prime.
Problem
Source: Romania TST 2014 Day 3 Problem 2
Tags: number theory unsolved, number theory
27.01.2015 02:39
If $n$ is a positive integer which has at most two prime divisors, then $(1) \;\; \sigma(n) = 2n-2$ iff ${n=2^k(2^{k+1} + 1})$, where $k$ is an non-negative integer and $2^{k+1} + 1$ is a prime. Proof: Clearly $n \neq 1$ by (1). Hence $n$ has one or two prime divisors. Thus we have the following two cases: Case 1: $n=p^r$, where $p$ is a prime and $r$ is positive integer. Inserting $n=p^r$ in (1), the result is ${\textstyle \frac{p^{r+1}-1}{p-1} = 2p^r - 2}$, i.e. $(2) \;\; p^r(p - 2) = 2p - 3$. Hence $3|p$, implying $p=3$, which inserted in (2) give us $3^r = 3$, yielding $r=1$. So the only solution of (1) is $n = p^r = 3^1 = 3 = 2^0(2^1 + 1)$. Case 2: $n=p^r \cdot q^s$, where $p,q$ are primes with $p<q$ and $r,s$ are positive integers. By inserting $n=p^rq^s$ in (2), we obtain ${\textstyle \frac{p^{r+1}-1}{p-1} \cdot \frac{q^{s+1}-1}{q-1} = 2p^rq^s - 2}$, i.e. $(p^{r+1} - 1)(q^{s+1} - 1) = 2(p^rq^s - 1)(p - 1)(q - 1)$, which is equivalent to $(3) \;\; p^rq^s(pq - 2p - 2q + 2) = 2(p - 1)(q - 1) - p^{r+1} - q^{s+1} + 1$. The RHS of (3) is $2(p - 1)(q - 1) - p^{r+1} - q^{s+1} + 1$ $= 2pq - p^{r+1} - q^{s+1} - 2(p + q) + 3$ $\leq 2pq - p^2 - q^2 - 2(p + q) + 3$ since $r,s \geq 1$ $= -(p - q)^2 - 2(p + q) + 3$ $< 0$ since $p,q > 1$. Therefore $pq - 2p - 2q + 2 < 0$ by (3), i.e. $(4) \;\; (p - 2)(q - 2) < 2$. If $p \neq 2$, then $p \geq 3$ and $q \geq 5$, which implies $(p - 2)(q - 2) \geq 1 \cdot 3 = 3$, contradicting (4). Consequently $p=2$, which inserted in (3) result in $-2^{r+1}q^s = 2(q - 1) - 2^{r+1} - q^{s+1} + 1$, i.e. ${\textstyle 2^{r+1} = \frac{q^{s+1} - 2q + 1}{q^s - 1} = q - \frac{q-1}{q^s-1}}$. Therefore ${\textstyle \frac{q - 1}{q^s - 1} \in \mathbb{N}}$, implying $q^s \leq q$. Hence $s=1$ and $2^{r+1} = q - 1$, yielding $n=p^rq^s = 2^rq = 2^r(2^{r+1}-1)$, where $2^{r+1}+1=q$ is a prime. Summa summarum, these two cases give us $n=2^k(2^{k+1} + 1)$, where $k$ is a non-negative integer and $2^{k+1} + 1$ is a prime, as the only possible solutions of equation (1). These are indeed solutions of $(1)$ since $\sigma(n) = \sigma(2^k(2^{k+1} + 1)) = \sigma(2^k) \cdot \sigma(2^{k+1} + 1) = (2^{k+1} - 1)(2^{k+1} + 2) = 2n - 2$. q.e.d.