# Number Theory : Find the values of $x$ for which $\phi(x)=\frac{x}{3}$

I was working my way through some basic Number Theory Problems , when I came across :

Find the values of $x$ for which $\phi(x)=\frac{x}{3}$ , where $\phi(x)$ is the euler phi function

I am unable to start the solution , can someone help me out : a hint would suffice ...

• Well, we can certainly think of a few (for the $\frac{\varphi(x)}{2}$ of the body, the title is different): $2,4,8,16,\dots$. Are there any others? Apr 6, 2015 at 1:53
• For the revised version, can you think of a bunch of $n$ that work? That could be a good start. Apr 6, 2015 at 1:59
• Yes, and it turns out that's all. Apr 6, 2015 at 2:04
• No it isn't all right, but the proof is straightforward, there are already two answers with fairly detailed proofs. Apr 6, 2015 at 2:08
• Rosen is just fine, lots of problems to practice on. Silverman (Friendly Introduction) is a very good first book, but there is no real reason to switch. Apr 6, 2015 at 2:18

Consider that: $$\frac{\varphi(n)}{n}=\prod_{p\mid n}\left(1-\frac{1}{p}\right)\tag{1}$$ and for every odd $p$, $$\nu_2\left(1-\frac{1}{p}\right) \geq 1, \tag{2}$$ hence in order that the RHS of $(1)$ equals $\frac{1}{3}$, since $\nu_2\left(\frac{1}{3}\right)=0$, the prime divisors of $n$ must be $2$ and just another odd prime, that is forced to be $3$. That gives that the only positive integers fulfilling $(1)$ are the ones of the form: $$n= 2^a 3^b\tag{3}$$ for $a,b\in\mathbb{N}\setminus\{0\}$.

Here $\nu_2$ is intended as the $2$-adic height, i.e., assuming $\gcd(p,q)=1$, $\nu_2\left(\frac{p}{q}\right)$ is $\max\{m\in\mathbb{N}:2^m\mid p\}$ if $p$ is even, $-\max\{m\in\mathbb{N}:2^m\mid q\}$ if $q$ is even and zero if both $p$ and $q$ are odd.

• Hi , @JackDAurizio ,thanks a ton - that does it ; though I am not sure what $adic$ $height$ means - is it something to do with group theory ? Apr 6, 2015 at 2:02
• @pranav: it is a concept deeply related with $p$-adic integers. Anyway, you can think to $\nu_2$ as just a measure of "how even" an integer, or a rational number, is. Apr 6, 2015 at 2:06
• Thanks @JackDAurizio , I got it :) Apr 6, 2015 at 2:07

Let $p$ be the largest prime which divides $x$, and write $x=p^nk$ with $p \nmid k$.

Then by the formula of the totient function, the power of $p$ in $\phi(x)$ is exactly $p^{n-1}$. [note that this is only true in general for the largest prime].

This shows that the power of $p$ in $\frac{p^nk}{3}$ is $n-1$, and hence $p=3$.

Now, if $p=3$ is the largest prime dividing $x$, it follows that $x=2^a3^b$ with $b \geq 1$ and $a \geq 0$.

Now, use the totient formula to find which of the above $x$ work.

Check the Euler's product formula for the totient function perhaps?

Hint: Think about what primes your $x$ is divisible by.

• This argument should be expanded in order that it could be considered as a hint. The product representation for $\frac{\phi(n)}{n}$ is just the starting point. Apr 6, 2015 at 2:04
• I was unsure how much detail to give to be considered a hint, if I'm honest. Apr 6, 2015 at 2:12