Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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 ...
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.
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.
