(Worried)

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?!(Crying)

Thank you

xx

- Aug 18th 2010, 02:38 AMHorseStar2Can any one please help with this Euler's function question ?
(Worried)

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?!(Crying)

Thank you

xx - Aug 18th 2010, 05:52 AMsimplependulum
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 $ . - Aug 18th 2010, 06:12 AMthorin
Hi,

if you don't know the formula used by simplependulum, you can also write $\displaystyle n=2^m*q$, with $\displaystyle q=2k+1$, and use $\displaystyle \phi (m)* \phi(n) =\phi (mn) $when $\displaystyle GCD(m,n)=1$ - Aug 19th 2010, 09:23 PMHorseStar2
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!!! (Itwasntme) - Aug 19th 2010, 09:27 PMHorseStar2
- Aug 19th 2010, 09:59 PMundefined
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. - Aug 19th 2010, 10:39 PMHorseStar2
- Aug 19th 2010, 10:44 PMundefined
- Aug 19th 2010, 10:47 PMHorseStar2
- Aug 19th 2010, 10:49 PMundefined