Determine all integers n for which Euler's function (phi) = n/2?

Thank you

xx

2. We have this famous result $\phi(n) = n \prod \left( 1 - \frac{1}{p_i } \right)$ where $p_i | n$ .

Then we are going to show $\prod \left( 1 - \frac{1}{p_i } \right) = \frac{1}{2}$ . The key to the problem is using inequality :

We know the smallest prime is $2$ , thus $p_i \geq 2$ or $\frac{1}{p_i} \leq \frac{1}{2}$

$1 - \frac{1}{p^i} \geq 1- \frac{1}{2} = \frac{1}{2}$

Therefore , $\frac{1}{2} = \prod \left( 1 - \frac{1}{p_i } \right) \geq \frac{1}{2^n}$ where $n$ denotes the number of primes involving in the product , since $n \geq 1$ , we must have $n=2$ and the only one prime $p_1$ is $2$ . We find that $2$ is the only prime divisor of $n$ so it is a power of $2$ namely $2^k$ .

3. Hi,
if you don't know the formula used by simplependulum, you can also write $n=2^m*q$, with $q=2k+1$, and use $\phi (m)* \phi(n) =\phi (mn)$when $GCD(m,n)=1$

4. Originally Posted by thorin
Hi,
if you don't know the formula used by simplependulum, you can also write $n=2^m*q$, with $q=2k+1$, and use $\phi (m)* \phi(n) =\phi (mn)$when $GCD(m,n)=1$
Hello thorin, thank you very much for your help, I wondered if you could please solve the question using the method you suggested too please as I'm not sure how to do it?

Also, (sorry to ask soo much) but I am also trying to solve..

Determine all integers n for which Euler's (phi) function = n/6

and I cannot do it, can you please explain ho to do this too?

THANK YOU SO MUCH!!!

5. Originally Posted by simplependulum
We have this famous result $\phi(n) = n \prod \left( 1 - \frac{1}{p_i } \right)$ where $p_i | n$ .

Then we are going to show $\prod \left( 1 - \frac{1}{p_i } \right) = \frac{1}{2}$ . The key to the problem is using inequality :

We know the smallest prime is $2$ , thus $p_i \geq 2$ or $\frac{1}{p_i} \leq \frac{1}{2}$

$1 - \frac{1}{p^i} \geq 1- \frac{1}{2} = \frac{1}{2}$

Therefore , $\frac{1}{2} = \prod \left( 1 - \frac{1}{p_i } \right) \geq \frac{1}{2^n}$ where $n$ denotes the number of primes involving in the product , since $n \geq 1$ , we must have $n=2$ and the only one prime $p_1$ is $2$ . We find that $2$ is the only prime divisor of $n$ so it is a power of $2$ namely $2^k$ .
Hi Simplependulum, Thank you so much for your help!! Can you also please explain the solution to...

Determine all integers n for which Euler's (phi) function = n/6

..to me as I am finding it difficult?

THANK YOU!!!

6. Originally Posted by HorseStar2
Determine all integers n for which Euler's (phi) function = n/6
I believe we can prove there are no such integers.

Suppose we write $n$ as its prime decomposition $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ where as usual $p_1 < \dots < p_r$. Consider the product $x=\prod \left( 1 - \frac{1}{p_i } \right)$ which must equal $\frac{1}{6}$ to satisfy the given condition. When $x$ is written as a fraction in lowest terms, the denominator must be divisible by $p_r$. (Details left for you to fill in.) So n cannot be divisible by a prime greater than 3. There are a trivially small number of cases to test to complete an exhaustive search.

7. Originally Posted by undefined
I believe we can prove there are no such integers.

Suppose we write $n$ as its prime decomposition $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ where as usual $p_1 < \dots < p_r$. Consider the product $x=\prod \left( 1 - \frac{1}{p_i } \right)$ which must equal $\frac{1}{6}$ to satisfy the given condition. When $x$ is written as a fraction in lowest terms, the denominator must be divisible by $p_r$. (Details left for you to fill in.) So n cannot be divisible by a prime greater than 3. There are a trivially small number of cases to test to complete an exhaustive search.
Hello undefined, thank you for replying. I wondered if you could submit the full answer plwwwease?

8. Originally Posted by HorseStar2
Hello undefined, thank you for replying. I wondered if you could submit the full answer plwwwease?
But which part are you having trouble with?

9. Originally Posted by undefined
But which part are you having trouble with?
Ohh the bit which says..Details left for you to fill in....I'm really sorry to ask... I just really need it spelt out for me..

Thank you

10. Originally Posted by HorseStar2
Ohh the bit which says..Details left for you to fill in....I'm really sorry to ask... I just really need it spelt out for me..

Thank you
Rewrite $1-\frac{1}{p_i}$ as a single fraction.