Let $\varphi(n)$ denote the number of natural numbers less than $n$ that are relatively prime to $n$, and $\sigma(n)$ denote the sum of the divisors of $n$. Determine all exponents $k$ for which

$$
\varphi\left(\sigma\left(2^{k}\right)\right)=2^{k}
$$

holds. (As a hint, we reveal that 641 is a divisor of $\left(2^{32}+1\right)$.)
Let $\varphi(n)$ denote the number of natural numbers less than $n$ and relatively prime to $n$, and $\sigma(n)$ denote the sum of the divisors of $n$. Determine all exponents $k$ for which

$$
\varphi\left(\sigma\left(2^{k}\right)\right)=2^{k}
$$

holds. (As a hint, we reveal that 641 is a divisor of $\left(2^{32}+1\right)$.

Solution. Let the prime factorization of $n$ be $p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \cdot \ldots \cdot p_{s}^{\alpha_{s}}$, where $p_{1}, p_{2}, \ldots, p_{s}$ are distinct primes, and $\alpha_{1}, \ldots, \alpha_{s}$ are positive integers. Then

$$
\varphi(n)=p_{1}^{\alpha_{1}-1}\left(p_{1}-1\right) \cdot \ldots \cdot p_{s}^{\alpha_{s}-1}\left(p_{s}-1\right)
$$

(see, for example, Molnár Emil: Matematikai versenyfeladatok, 490. p.). If now $n$ is odd and $\varphi(n)=2^{k}$, then (2) can only hold if, on the one hand, $\alpha_{1}=\alpha_{2}=\alpha_{s}=\ldots=1$ (since $p_{i}$ is odd), and on the other hand, $p_{i}-1=2^{\beta_{i}}$ for some positive integer $\beta_{i}$. We know that $2^{\beta_{i}}+1$ can only be a prime if $\beta_{i}$ itself is a power of two, and such numbers are called Fermat primes. We have thus obtained that

$$
n=\left(2^{\beta_{1}}+1\right)\left(2^{\beta_{2}}+1\right) \ldots\left(2^{\beta_{s}}+1\right)
$$

where $\beta_{i}=2^{\gamma_{i}}, 0 \leqq \gamma_{1}<\gamma_{2}<\ldots<\gamma_{s}$, and $2^{\beta_{i}}+1$ is a prime. Performing the multiplication in (3),

$$
n=1+2^{\beta_{1}}+2^{\beta_{2}}+2^{\beta_{1}+\beta_{2}}+\ldots+2^{\beta_{s}}+2^{\beta_{s}+\beta_{1}}+\ldots+2^{\beta_{s}+\ldots+\beta_{1}}
$$

Here, a total of $2^{s}$ terms appear, and since the $\beta_{i}$ are distinct powers of two, the exponents are all different. This means that in the binary representation of $n$, 1s appear in the 0th, $\beta_{1}$-th, $\beta_{2}$-th, $\ldots\left(\beta_{1}+\beta_{2}+\ldots+\beta_{s}\right)$-th positions from the right, and 0s in all other positions.

Now let's return to the (1) equation. Since the divisors of $2^{k}$ are $1,2,2^{2}, \ldots, 2^{k}$, then

$$
n=\sigma\left(2^{k}\right)=1+2+2^{2}+\ldots+2^{k}
$$

is an odd number, whose binary representation has 1s in the last $k+1$ positions. Therefore, $\varphi(n)=2^{k}$ can only hold if $n$ can also be written in the form (4). And since a number can only be written in one way in binary, this means that the numbers $\beta_{1}<\beta_{2}<\beta_{1}+\beta_{2}<\ldots \beta_{1}+\beta_{2}+\ldots+\beta_{s}$ must match the numbers 1, $2, \ldots, k$. This is only possible if $\beta_{1}=2^{0}, \beta_{2}=2^{1}, \ldots, \beta_{s}=2^{s-1}, \ldots$, and $k=2^{s}-1$. At the same time, $2^{\beta_{i}}+1=2^{2^{i-1}}+1$ must be a prime for every $1 \leqq i \leqq s$. According to the hint given in the problem, $2^{32}+1=2^{2^{5}}+1$ is not a prime, so only the cases $s=1,2,3,4$ and 5 are possible, i.e., the possible values of $k$ are $1,3,7,15$ and 31. And since $2^{2^{i-1}}+1$ is a prime if $i \leqq 5$, these values of $k$ indeed satisfy (1).