3
$\begingroup$

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

$\endgroup$
9
  • 1
    $\begingroup$ 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? $\endgroup$ Apr 6, 2015 at 1:53
  • 1
    $\begingroup$ For the revised version, can you think of a bunch of $n$ that work? That could be a good start. $\endgroup$ Apr 6, 2015 at 1:59
  • 1
    $\begingroup$ Yes, and it turns out that's all. $\endgroup$ Apr 6, 2015 at 2:04
  • 1
    $\begingroup$ No it isn't all right, but the proof is straightforward, there are already two answers with fairly detailed proofs. $\endgroup$ Apr 6, 2015 at 2:08
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 6, 2015 at 2:18

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – pranav
    Apr 6, 2015 at 2:02
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 6, 2015 at 2:06
  • 1
    $\begingroup$ Thanks @JackDAurizio , I got it :) $\endgroup$
    – pranav
    Apr 6, 2015 at 2:07
2
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 6, 2015 at 2:04
  • 1
    $\begingroup$ I was unsure how much detail to give to be considered a hint, if I'm honest. $\endgroup$
    – flabby99
    Apr 6, 2015 at 2:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .