# Values of the Euler-Phi function

I tried to find an answer to the following problem, but i don't even know how to describe it in order to search for it:

Is it true that $\forall n \in \mathbb N: \exists m \in \mathbb N: \exists k \in \mathbb N: \phi(m)=2^k n$. If this holds what is the minimal value of $k=k(n)$ for arbitrary m.

-
This paper is relevant, but does not provide a direct answer to this question. –  vadim123 Jun 9 '13 at 20:56

If $n$ is an odd prime, then $n|\phi(m)$ implies that $n^2|m$ or some prime $q|m$ with $n|q-1$. In the first case, $n(n-1)|\phi(m)$, hence we need that $n-1$ is a power of $2$ (i.e. $n$ is a Fermat prime, only few are known). In the second case, $q-1|\phi(m)$ and hence $\frac{q-1}n$ must be a power of two. The existence of such $q$ seems to be a piece of luck sometimes, e.g. for for $n=47$, the smallest such $q$ is $2^{583}n+1$. And for $n=383$, the smallest such $q$ is $2^{6393}n+1$.
Your function $k(n)$ for prime $n$ can be found at OEIS, where we learn that $271129$ is a Sierpinski prime, i.e. no $m$ with $\phi(m)=2^k\cdot 271129$ exists.