Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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.

share|cite|improve this question
This paper is relevant, but does not provide a direct answer to this question. – vadim123 Jun 9 '13 at 20:56
up vote 1 down vote accepted

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.

share|cite|improve this answer
it took me a while to understand, but now i see how it works. thank you for your complete answer! – user75148 Jun 10 '13 at 6:59

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.