So, I want to prove the theorem in the title.

The implication that if $n$ is product of power of 2 and some Fermat's prime numbers, then $\varphi(n)=2^k$ (where $\varphi$ denotes Euler's totient function and $k$ is some natural number) is, I think, obvious (directly from that formula). The problem is the other implication.

If we have $\varphi(n)=2^l$ then first $2\mid n$ and we could write $n=2^kn_1$ where $k \in \mathbb{N}$ and $2$ does not divide $n_1$. Then, if $p_1,\ldots,p_k$ were all different prime divisors of $n$, then now we have $p_1=2$, while $n_1$ has prime divisors $p_2,\ldots,p_k$, none of which is $2$. Note that if $p_i^{k_i}$ divided $n_1$ for some $i$ , where $k_i>1$, then that $p_i$ divides $\varphi(n)$, and $\varphi(n)$ is not the power of $2$. So, $n_1=p_2p_3\cdots p_n$ and now when we write formula for $\varphi(n)$ we get $$\varphi(n) = 2^k(p_2-1)\cdots(p_k-1)$$ and $\varphi(n)$ is a power of $2$, meaning all its divisors are power of $2$, meaning $p_i = 2^{k_i}+1$ for all $2 \leq i \leq n$ and for some $k_i$, such that $p_i$ is a prime.

The problem is that I can not conclude that $k_i = 2^{m_i}$, which I need for Fermat's numbers (of type $2^{2^n}+1$). Please help.

  • $\begingroup$ "If we have $\varphi(n)=2^l$ then first $2|n$..." that's false for all fermat primes except $2$ $\endgroup$ – vrugtehagel Apr 2 '17 at 17:36

You can prove that if $2^m+1$ is prime, then $m$ must itself be a power of $2$; see this math.SE thread.

  • 2
    $\begingroup$ Without external links, simply: if $m$ has an odd divisor $d>1$, then $2^d+1$ is a divisor of $2^m+1$. It follows that $2^m+1$ being a prime implies that $m$ has no non-trivial odd divisors, i.e. $m=2^k$. $\endgroup$ – Jack D'Aurizio Apr 2 '17 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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