Determine all integers n for which Euler's function (phi) = n/2?
Can anyone please help me, I'm really not sure what to do?!
Thank you
xx
We have this famous result $\displaystyle \phi(n) = n \prod \left( 1 - \frac{1}{p_i } \right) $ where $\displaystyle p_i | n $ .
Then we are going to show $\displaystyle \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 $\displaystyle 2 $ , thus $\displaystyle p_i \geq 2 $ or $\displaystyle \frac{1}{p_i} \leq \frac{1}{2} $
$\displaystyle 1 - \frac{1}{p^i} \geq 1- \frac{1}{2} = \frac{1}{2} $
Therefore , $\displaystyle \frac{1}{2} = \prod \left( 1 - \frac{1}{p_i } \right) \geq \frac{1}{2^n} $ where $\displaystyle n $ denotes the number of primes involving in the product , since $\displaystyle n \geq 1 $ , we must have $\displaystyle n=2 $ and the only one prime $\displaystyle p_1 $ is $\displaystyle 2 $ . We find that $\displaystyle 2 $ is the only prime divisor of $\displaystyle n $ so it is a power of $\displaystyle 2 $ namely $\displaystyle 2^k $ .
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!!!
I believe we can prove there are no such integers.
Suppose we write $\displaystyle n$ as its prime decomposition $\displaystyle n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ where as usual $\displaystyle p_1 < \dots < p_r$. Consider the product $\displaystyle x=\prod \left( 1 - \frac{1}{p_i } \right)$ which must equal $\displaystyle \frac{1}{6}$ to satisfy the given condition. When $\displaystyle x$ is written as a fraction in lowest terms, the denominator must be divisible by $\displaystyle 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.