8
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Why do you require $n$ to be an odd integer? $\endgroup$ – Daniel Mar 25 '15 at 11:44
  • $\begingroup$ The task limits $n$ to be an odd integer. $\endgroup$ – Atvin Mar 25 '15 at 11:44
  • 1
    $\begingroup$ $\phi(9) = 6$ right? $\endgroup$ – Atvin Mar 25 '15 at 11:45
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice answer :) $\endgroup$ – Atvin Apr 3 '15 at 14:39
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

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.