# Can any one please help with this Euler's function question ?

• Aug 18th 2010, 02:38 AM
HorseStar2
Can 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 AM
simplependulum
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 AM
thorin
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 PM
HorseStar2
Quote:

Originally Posted by thorin
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$

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 PM
HorseStar2
Quote:

Originally Posted by simplependulum
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$ .

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!!! :)
• Aug 19th 2010, 09:59 PM
undefined
Quote:

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 $\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 PM
HorseStar2
Quote:

Originally Posted by undefined
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.

Hello undefined, thank you for replying. I wondered if you could submit the full answer plwwwease? (Itwasntme)
• Aug 19th 2010, 10:44 PM
undefined
Quote:

Originally Posted by HorseStar2
Hello undefined, thank you for replying. I wondered if you could submit the full answer plwwwease? (Itwasntme)

But which part are you having trouble with?
• Aug 19th 2010, 10:47 PM
HorseStar2
Quote:

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
• Aug 19th 2010, 10:49 PM
undefined
Quote:

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 $\displaystyle 1-\frac{1}{p_i}$ as a single fraction.