# Finding number of solutions to $\phi(x) = 2^{2013}$

As the title says, I would like to find the number of solutions to $\phi(x) = 2^{2013}$ where $\phi$ is the Euler-totient function. Here are some facts I could use.

$2^{2^{n}} + 1$ is prime for $0 \le n \le 4$ and composite for $5 \le n \le 32$. Help would be appreciated.

-
Presumably, another fact you could use is the formula for $\phi(n)$ in terms of the factorization of $n$ into prime powers. Do you know this formula? – Gerry Myerson Feb 20 '13 at 5:10
Yes, $\phi(n) = n\prod_{p \mid n} (1 - 1/p)$. – user63082 Feb 20 '13 at 5:11
And does that tell you something about which primes can divide $x$? – Gerry Myerson Feb 20 '13 at 5:46

As $\phi(\prod q_i^{s_i+1})=\prod q_i^{s_i}(q_i-1)$ so here $x$ can not have any prime factor $>2$ with power $\ge2$

Clearly, $x$ is of the form $2^t\prod p_i$ where prime $p_i=2^{r_i}+1$

So, $\phi(x)=2^{t-1}\prod2^{r_i}\implies t-1+\sum r_i=2013$ or $t=2014-\sum r_i$

Now, with the supplied fact, $r_i$ can assume $5$ values corresponding to $n=0,1,2,3,4$ of which we can choose $0,1,2,3,4,5$ elements.

Now, $r,$ where $0\le r\le n$ elements from $n$ elements can be chosen in $\binom nr$ ways.

So, the number of possible combinations is $\binom 50+\cdots+\binom 55=(1+1)^5=2^5$

-
There seems to be a minor typo. Shouldn't $n = 0, 1, 2, 3, 4$? – user63082 Feb 20 '13 at 5:41
@user63082, thanks for your observation. Rectified. – lab bhattacharjee Feb 20 '13 at 5:44
@Mike, in my answer $r_i=2^{n}$ where $n=0,1,2,3,4,5$ – lab bhattacharjee Feb 20 '13 at 9:48
@labbhattacharjee My apologies. It wasn't clear. Still, there is a gap here: showing $r_i$ must be in the form $2^n$, although that part should be easy in comparison. – Mike Feb 20 '13 at 9:59
@Mike, do you mean to show : for prime $2^r+1$ we need $r=2^n$? – lab bhattacharjee Feb 20 '13 at 10:30