Does the totient function reach all its values when restricted to odd numbers?

Question

This question might be a duplicate, if so, I apologise in advance. It is simple, but answering it is probably harder :)

Is it true, that the $\phi(n)$ function(Euler's totient function) takes on all of it's values, when $n$ is an odd integer?

I obviously tried it for the first some $n$:

$\phi(1) = 1, \phi(3) = 2, \phi(5) = 4, $ and so on.

It is obvious, that if $n$ is a prime, than $\phi(n) = n-1$, so we cover all the $p-1$ numbers, where $p$ is a prime. I just can't really prove if any number is missing on this list.

The question can be asked in this way too: Is it true, that if we use the totient function with only odd integers, we get all the values from it. I hope you can understand it, if not, just comment below, and I try to answer. :) Thanks for any comments!

Answer 1

The answer is no - for no odd number $n$ we can have $\varphi(n)=2^{32}$, even though $\varphi(2^{33})=2^{32}$. Assuming there is such an $n$, if $n=p_1^{e_1}...p_i^{e_i}$ (with all primes odd) then $\varphi(n)=\varphi(p_1^{e_1})...\varphi(p_i^{e_i})=p_1^{e_1-1}(p_1-1)...p_i^{e_i-1}(p_i-1)$. If any $e_k>1$ then we would have $\varphi(n)$ divisible by $p_k$, so it couldn't be equal to $2^{32}$. So every $e_k=1$, and all the $p_k-1$ are powers of two, so the $p_k$ are Fermat primes, say $p_k=F_{a_k}=2^{2^{a_k}}+1$. So we have $2^{32}=\varphi(n)=2^{2^{a_1}}...2^{2^{a_i}}=2^{2^{a_1}+...+2^{a_i}}$, so $32=2^{a_1}+...+2^{a_i}$. By the uniqueness of binary expansion, we get $i=1$ and $a_1=5$, but then we get that $F_5=2^{2^5}+1$ is prime, which it isn't. Contradiction.

Answer 2

The answer is no. Let $m = 2^kn$, with $k=3$ or $4<k<15$ and $n$ odd. Then $\phi(m) = \phi(2^k)\phi(n)=2^{k-1}\phi(n)$. I claim there is no odd number $x$ with $\phi(x) = \phi(m) = 2^{k-1}\phi(n)$.

Let $x$ be an odd number. It can be written as $\Pi_{i=1}^n p_i^{e_i}$, where because $x$ is odd, none of the $p_i$ is $2$. The formula for the totient given a prime factorization yields $\phi(x) = \Pi_{i=1}^n p_i^{e_i-1}(p_i-1)$.

$p_i^{e_i-1}$ is clearly not a power of two for $p_i \neq 2$, and $(p_i-1)$ is a power of two only for $p_i$ a Fermat prime. The only known such primes are $3,5,17,257, 65537$. This means the only known powers of two that can appear in $\phi(x)$ are $2,4,16,256,65536$, or $2^1,2^2,2^4,2^{16}$. So if $k =4$ or $5<k<17$, $\phi(x)$ cannot equal $\phi(2^kn)$.

Answer 3

No.
$\let\phi\varphi\let\leq\leqslant$ Observe that if $\phi(n)=2^k$ and $n$ is odd, then all prime divisors of $n$ are Fermat primes (primes of the form $F_a=2^{2^a}+1$) and have multiplicity $1$. The only known Fermat primes correspond to $a=0,1,2,3,4$ and it is known that $5\leq a\leq32$ gives composite numbers.
Claim. There exists no odd number $n$ with $\phi(n)=2^{32}$.
Proof. Every prime divisor of $n$ is a Fermat prime $F_a$ with $a\leq5$ and has multiplicity $1$. Hence the only possible prime divisors of $n$ are $F_0,F_1,F_2,F_3,F_4$. But $\phi(F_0F_1F_2F_3F_4)=2^{1+2+4+8+16}=2^{31}$, meaning that such $n$ cannot exist.