With $\sigma (n)$ we denote the sum of the positive divisors of the natural number $n$. Prove that there exist infinitely many natural numbers $n$, for which $n$ divides $2^{\sigma (n)} -1$.
Problem
Source: VIII International Festival of Young Mathematicians Sozopol 2017, Theme for 10-12 grade
Tags: number theory
20.08.2019 19:45
Sketch: Idea is to construct a sequence $a_n$ inductively, where $a_n = a_{n-1}p_n$ with $p_n\mid 2^{\sigma(a_{n-1})}-1$ is a prime. The details are as follows. Take $a_1=3$, and observe that $3\mid 2^4-1$ (motivation: I took $a_1=p$, and $\sigma(p)=p+1$, yielding $p\mid 2^{p+1}-1$. Since $2^{p-1}\equiv 1\pmod{p}$, we get $p=3$). Now, observe that, $2^{\sigma(a_1)}-1=15$, and take $p_2=5$, set $a_2=p_1p_2$, and observe, $15\mid 2^{24}-1$, where $24=\sigma(15)=\sigma(3)\sigma(5)$. The inductive step is as follows. Let $a_{n-1} = p_1p_2\cdots p_{n-1}$, with $a_{n-1}\mid 2^{\sigma(a_{n-1})}-1$. The idea is to show, there exists a prime $p_n$ such that $p_n \notin \{p_1,\dots,p_{n-1}\}$, and $p_n\mid 2^{\sigma(a_{n-1}}-1$. Then, setting $a_n = a_{n-1}p_n$, we have the claim, since $\sigma(a_n) = \sigma(a_{n-1})\sigma(p_n)$. To see this, observe first: $\sigma(a_{n-1})=\prod_{i=1}^{n-1}(p_i+1)=\prod_{i=1}^{n-1}(2^{k_i}q_i)$, where $k_i\geqslant 1$ (since all primes involved are odd), and $2\nmid q_i$. In particular, since $k_1=2$, we then have $k_1+\cdots+k_n\geqslant n$. With this, the object $2^{\sigma(a_{n-1})}-1$ then equals $a^{2^K}-1$, where $K=k_1+\cdots+k_n\geqslant n$, and $a=2^{m'}$, where $m'=\prod_{i=1}^{n-1}q_i$ (observe that $a$ is even). Now, we have $a^{2^n}-1$ divides $2^{\sigma(a_{n-1})}-1$. Observe that, $a^{2^n}-1=(a-1)(a+1)(a^{2^1}+1)\cdots (a^{2^{n-1}}+1)$. Now, observe that, ${\rm gcd}(a^{2^{t_1}}+1,a^{2^{t_2}}+1)=1$, for any $t_1\neq t_2$ (indeed, if the gcd is $d$, then taking $t_1<t_2$ wlog we have $a^{2^{t_2}}\equiv 1\pmod{d}$, and thus, $a^{2^{t_2}}+1\equiv 2\pmod{d}$, and since these objects are all odd -thanks to $a$ being even- we have the claim). In particular, each of them generate a distinct prime divisor, and thus, $2^{\sigma(a_{n-1})}-1$ has at least $n$ distinct prime divisors. The end.
29.12.2021 20:09