2
$\begingroup$

This question already has an answer here:

prove or disprove the following statement:

There are infinitely many integers $n$ such that $φ(n)=n/3$. where $φ(n)$ is Euler Phi-Function.

Could you please help me with the prove of this , I try it many time but I do not how can I start to prove it or disprove?.

$\endgroup$

marked as duplicate by Batominovski, lab bhattacharjee elementary-number-theory Dec 2 '17 at 9:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

From the totient formula: $$\varphi(n)=n\prod_{p\mid n}\frac{p-1}p$$ we find that $\varphi(n)=n/3$ is true if $n$ only contains 2 and 3 as prime factors: $\varphi(n)=n×\frac12×\frac23$. Thus there are infinitely many such $n$, of the form $2^a3^b$ with $a,b>0$: 6, 12, 18, 24, etc.

$\endgroup$
  • $\begingroup$ @dr.rise Why, you could do that. $\endgroup$ – Parcly Taxel Dec 7 '17 at 11:22
2
$\begingroup$

Hint: Look at integers in the form $n = 2^a3^b$ where $a$ and $b$ are positive integers. Can you calculate $\varphi(n)$ for integers $n$ in that form?

$\endgroup$
2
$\begingroup$

I take it that $\phi$ is the Euler totient function, that is $\phi(n)$ is the cardinality of $\{1 \leq k \leq n : \gcd(n,k) = 1\}$.

For this, we can look at the formula: $$ n = \prod p_i^{\alpha_i} \implies \phi(n) = n \times \prod\frac{(p_i - 1)}{p_i} $$

Then, our expression is basically telling us to find a distinct list of primes $p_i$ such that $\prod \frac{p_i - 1}{p_i} = \frac 13$. You can see that if $p_1 = 2, p_2 = 3$ then $\frac{2-1}{2} \frac{3-1}{3} = \frac 13$.

Therefore, for any number of the form $2^a3^b$, where $a,b \geq 1$, it follows that $\phi(2^a3^b) = 2^a3^{b-1}$.

Since there are infinitely many such numbers, you can conclude.

Using similar arguments, you can also conclude statements like this:

Taking $p_1=2,p_2 = 3,p_3 = 5$, we get $\prod \frac{p_i-1}{p_i} = \frac{4}{15}$, so the ratio $\frac{n}{\phi(n)}$ is $\frac{4}{15}$ infinitely often. Similarly, for any prime q, taking $p_1 = 2$ and $p_2 = q$ gives that $\frac{n}{\phi(n)}$ is $\frac{q-1}{2q}$ infinitely often.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.