2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This paper is relevant, but does not provide a direct answer to this question. $\endgroup$ – vadim123 Jun 9 '13 at 20:56
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ it took me a while to understand, but now i see how it works. thank you for your complete answer! $\endgroup$ – user75148 Jun 10 '13 at 6:59

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.