Given $N = 2^ap_1p_2...p_m$, $m \ge 1$, $a \in N$ with $p_1, p_2,..., p_m$ are different primes. It is known that $\sigma (N) = 3N $ where $\sigma (N)$ is the sum of all positive integers which are factors of $N$. Show that there exists a prime number $p$ such that $2^p- 1$ is also a prime, and $2^p - 1|N$.
Problem
Source: 2011 Indonesia TST stage 2 test 3 p4
Tags: number theory, prime, sum of divisors, divides
17.12.2020 12:52
Indonesia TST 2011 Test 3 P4 wrote: Given $N = 2^ap_1p_2...p_m$, $m \ge 1$, $a \in N$ with $p_1, p_2,..., p_m$ are different primes. It is known that $\sigma (N) = 3N $ where $\sigma (N)$ is the sum of all positive integers which are factors of $N$. Show that there exists a prime number $p$ such that $2^p- 1$ is also a prime, and $2^p - 1|N$. WLOG suppose that $2<p_1<p_2<\ldots<p_m$ (if $p_1=2$ we can proceed similarly as in the solution below by writing $N=2^{a+1}p_2 \cdots p_m$). It is known that $\sigma(N)=(2^{a+1}-1)(p_1+1)\cdots(p_m+1)$, hence $$(2^{a+1}-1)(p_1+1) \cdots (p_m+1)=3 \cdot 2^ap_1 \cdots p_m \, (*)$$We proceed with two Claims. Claim 1: $(p_1+1) \nmid p_t$ for all $t \leq m$. Proof: Suppose a $t$ existed such that $(p_1+1) \mid p_t$. Then since $p_1+1>1$ we must have $p_1+1=p_t$, hence $p_1=2$ and $p_t=3$, contradiction $\blacksquare$ Claim 2: If $p_i+1$ is a power of $2$ for some $i$ then we are done. Proof: Suppose that $p_i+1=2^k$ for a positive integer $k$, hence $p_i=2^k-1$. If $k$ is composite, let $k=ab$ with $a,b \geq 2$ then $$(2^a-1) \mid (2^{ab}-1)=(2^k-1)=p_1 \Rightarrow 2^a-1 \in \{1,p_1 \}$$hence $a=1$ or $b=1$, which is a contradiction. Therefore $p_1=2^k-1$ with $k$ non-composite. If $k=1$ then $p_1=1$ so we may assume that $k$ is prime. Hence, $p_1=2^k-1$ is prime, divides $N$, and $k$ is prime, as desired $\blacksquare$ __________________________________________________________________________________________________________________ From now on assume that $p_i+1$ is not a power of $2$ for all $i$. From $(*)$ we have $(p_1+1) \mid 3 \cdot 2^a p_1 \cdots p_m$ and using the result from Claim 1 we obtain that $(p_1+1) \mid 3 \cdot 2^a$ hence we may write $p_1+1=3 \cdot 2^{x_1}$ with $x_1 \in \mathbb{N}$. Therefore, $$(2^{a+1}-1)(p_2+1) \cdots (p_m+1)=2^{a-x_1}p_1p_2\cdots p_m$$so similarly we may write $p_2+1=p_2 \cdot 2^{x_2}$. Continuing like that, we conclude that $p_i+1=p_{i-1}2^{x_i}$ for all $i \geq 2$. Comparing the $v_2$'s we obtain $x_1+\ldots+x_m=a$, hence substituing these in $(*)$ we have $2^{a+1}-1=p_m$, which is a contradiction to what we assumed before. In any case, we are done. Edit: Credit to grupyorum for the last part of the solution (from the line and on)