find all $n$ such that $\varphi(\sigma(2^n)) = 2^n$

Question

Problem: Find all positive integers $n$ such that $\varphi(\sigma(2^n)) = 2^n$, where $\varphi(n)$ is Euler's totient function and $\sigma(n)$ is the sum of all divisors of $n$.

I know that $\sigma(2^n) = 1+2+2^2+2^3+\dots+2^n = 2^{n+1}-1$, so we only need to find all $n$ such that $\varphi(2^{n+1}-1) = 2^n$. Trying out a few $n$, we find that $n=1,3,7,15,31$ work. Not sure how to prove this though. Any answers?

Answer 1

This problem beautifully connects Mersenne numbers to Fermat numbers.

@RossMillikan hints that $n=2^k-1$ is special. By noting $\prod_{j=0}^{k-1}(2^{2^j}+1)$ is a product of coprime Fermat numbers, you can prove $\varphi(2^{2^k}-1)=2^{2^k-1}$, provided those Fermat numbers are prime.

Now for the converse. If $\varphi(2^{n+1}-1)$ is a power of two, so is $\varphi(p)$ for each prime factor $p$ of $2^{n+1}-1$, so such primes are $1$ more than a power of $2$, i.e. are Fermat primes. Note $\prod_{j\ge1}(1+2^{-2^j})=\frac43$ by the above telescoping logic. So while a product of Fermat numbers exceeds the product of the powers of $2$ below them, the closest it can get to the next power of $2$ is to be $1$ less than it, by using all Fermat numbers up to a certain point, giving us the previous case.

Answer 2

Taking $n=15$ for example, we have $\sigma(2^{15})=2^{16}-1=(2+1)(2^2+1)(2^4+1)(2^8+1)=3\cdot 5 \cdot 17 \cdot 257$ with all the factors prime. We know that for $p$ prime $\varphi(p)=p-1$, so $\varphi(2^{16}-1)=2\cdot 2^2\cdot 2^4\cdot 2^8=2^{15}$. You should show that this factorization works in all the cases you cite. This works again for $n=31$, but not for $n=63$ because $2^{32}+1=4294967297 = 641×6700417$ is not prime. $n=63$ will then not be a solution. If a number has any prime factors not of the form $2^k+1$ the multiplicative nature of $\varphi$ will ensure that it will have some odd factors, so these are all there are.

Answer 3

At the time that I am writing this, the existing comments and solutions are not satisfactory, either because they are not complete or they don't entirely make sense to me. Here is a full solution.

As originally stated, we are seeking positive integers $n$ such that $$\varphi(2^{n+1}-1)=2^n.$$ By a well-known problem of group theory (I actually prefer an elementary proof of that problem using modular orders), it follows that $n+1$ divides $2^n.$ So there exists a positive integer $k$ such that $n=2^k-1,$ and we want to solve $$\varphi(2^{2^k}-1)=2^{2^k -1}.$$ The trick here is to use the pseudo-telescoping identity $$\prod_{i=0}^{k-1}(2^{2^i}+1)=2^{2^k}-1,$$ which can be proven by multiplying the left side of the product by $2^{2^0}-1=1$ and repeatedly applying the difference of squares factorization. We can prove that the multiplicands $2^{2^i}+1$ are all coprime: assuming that there is a prime $p$ that divides both $2^{2^i}+1$ and $2^{2^j}+1$ leads to $$2^{2^i}\equiv 2^{2^j}\equiv -1\pmod{p}.$$ This is impossible unless $i=j,$ because otherwise whichever is smaller can be squared a few times to get the larger one, so the larger one would be congruent to $1\pmod{p}$ (the only thing can can go wrong is $p=2$ which is not possible since the multiplicands are all odd). Now that we have established that the multiplicands are pairwise coprime, the multiplicativity of $\varphi$ applies and we get \begin{align*} 2^{2^k -1} &= \varphi(2^{2^k}-1)\\ &= \varphi\left(\prod_{i=0}^{k-1}{(2^{2^i}+1)}\right)= \prod_{i=0}^{k-1}{\varphi(2^{2^i}+1)}\\ &\le \prod_{i=0}^{k-1}{2^{2^i}}= 2^{2^k -1}, \end{align*} by the sum of a geometric series formula. Equality holds if and only if $2^{2^i}+1$ is prime for $i=0,1,2,\ldots,k-1,$ meaning the Fermat numbers $F_0,F_1,F_2,\ldots, F_{k-1}$ all have to be prime. It is well-known that $F_0,F_1,F_2,F_3,F_4$ are all prime (in fact, there are the only known Fermat primes), and that $$F_5=641\cdot 6700417$$ is not prime. So the only solutions correspond to $k-1=0,1,2,3,4.$ This leads to $k=1,2,3,4,5$ and $$n=2^k -1=1,3,7,15,31.$$ All of the steps were reversible so these all work. If it matters, I tested them out on Wolfram Alpha to be sure and they satisfied the original equation. Note that $n=0$ is also a solution but I did not include them in the list since only positive solutions were requested.