• Aug 18th 2010, 03:38 AM
HorseStar2
(Worried)

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

Thank you

xx
• Aug 18th 2010, 06:52 AM
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$ .
• Aug 18th 2010, 07:12 AM
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$
• Aug 19th 2010, 10:23 PM
HorseStar2
Quote:

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!!! (Itwasntme)
• Aug 19th 2010, 10:27 PM
HorseStar2
Quote:

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!!! :)
• Aug 19th 2010, 10: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 $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.
• Aug 19th 2010, 11:39 PM
HorseStar2
Quote:

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? (Itwasntme)
• Aug 19th 2010, 11: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, 11: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, 11: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 $1-\frac{1}{p_i}$ as a single fraction.