Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.