# Combinatorial Study of Phi(n)

• Oct 29th 2009, 09:57 AM
kyldn6
Combinatorial Study of Phi(n)
Prove that $\phi(m)$ is even if m > 2.

and

Find all integers n such that $\phi(n) = 12$.

For the second one is it possible to do it simply with inspection or is there a formula I'm just missing?
• Oct 29th 2009, 10:36 AM
tonio
Quote:

Originally Posted by kyldn6
Prove that $\phi(m)$ is even if m > 2.

and

Find all integers n such that $\phi(n) = 12$.

For the second one is it possible to do it simply with inspection or is there a formula I'm just missing?

If $m=\prod\limits_{n=1}^r p_i^{a_i}$ $\,,\,\,p_i\,\,primes\,,\,\,0, then

$\phi(m)=m\,\prod\limits_{n=1}^r\left(1-\frac{1}{p_i}\right)$

This answers question 1 at once, and for question 2 you have a little maths to do. Enjoy!(Wink)

Tonio
• Nov 5th 2009, 07:33 AM
harkapobi
Quote:

Originally Posted by tonio
If $m=\prod\limits_{n=1}^r p_i^{a_i}$ $\,,\,\,p_i\,\,primes\,,\,\,0, then

$\phi(m)=m\,\prod\limits_{n=1}^r\left(1-\frac{1}{p_i}\right)$

This answers question 1 at once, and for question 2 you have a little maths to do. Enjoy!(Wink)

Tonio

Hi, I dont understand how you use this formula for $\phi(m)$ to find m for question 2. Could you please explain a little further?

Katy :)
• Nov 5th 2009, 08:06 AM
chisigma
For the second question see here...

http://www.mathhelpforum.com/math-he...t-problem.html

Kind regards

$\chi$ $\sigma$
• Nov 5th 2009, 11:13 AM
tonio
Quote:

Originally Posted by harkapobi
Hi, I dont understand how you use this formula for $\phi(m)$ to find m for question 2. Could you please explain a little further?

Katy :)

I'll give you a little additional hint: if $n=p_1^{r_1}\cdot...\cdot p_k^{r_k}\,,\,\,then\,\,\phi(n)=p_1^{r_1}\cdot...\ cdot p_k^{r_k}\left(1-\frac{1}{p_1}\right)\cdot...\cdot \left(1-\frac{1}{p_k}\right)$ $=p_1^{r_1-1}\cdot...\cdot p_k^{r_k-1}(p_1-1)\cdot...\cdot (p_k-1)$.

OTOH, we know $12=2^2\cdot 3$, so...

Tonio
• Nov 5th 2009, 01:10 PM
harkapobi
I'm sorry, i know i'm probably being really dumb but I still dont get it.

$2^{2}3$ http://www.mathhelpforum.com/math-he...4ad3ebfd-1.gif

How do you find n?
• Nov 5th 2009, 02:03 PM
tonio
Quote:

Originally Posted by harkapobi
I'm sorry, i know i'm probably being really dumb but I still dont get it.

$2^{2}3$ http://www.mathhelpforum.com/math-he...4ad3ebfd-1.gif

How do you find n?

Check cases: $p_i-1$ is even unless $p_i=2$, so you can have $12=12\cdot 1=6\cdot 2=4\cdot 3$:

1) $12=12\cdot 1=\left[p_1^{r_1-1}\cdot...\cdot p_k^{r_k-1}\right]\left[(p_1-1)\cdot...\cdot (p_k-1)\right]$
The only form $(p_1-1)\cdot...\cdot (p_k-1)$ can be 1 is if there's only one prime and it is 2, but then the prime 3 lacks us, so this can't be:

2) $12=1\cdot 12=\left[p_1^{r_1-1}\cdot...\cdot p_k^{r_k-1}\right]\left[(p_1-1)\cdot...\cdot (p_k-1)\right]$
The only way we can have $1 =\left[p_1^{r_1-1}\cdot...\cdot p_k^{r_k-1}\right]$ is if all the primes appear raised to 1, but then we must have $12 = \left[(p_1-1)\cdot...\cdot (p_k-1)\right]$ , which is possible only if there's one single prime which then must equal 13.

So we already have $\phi(13)=12\Longrightarrow \phi(2*13)=\phi(26)=12$ , since $\phi(2)=1$

Now you try $6\cdot 2\,,\,\,2\cdot 6\,,\,\,4\cdot 3\,\,and\,\,3\cdot 4$

Tonio
• Nov 5th 2009, 02:54 PM
harkapobi
Ok, I understand that I think. My question is actually $\phi(n) = 6$

So I have
Case 1: $6\cdot 1$ where http://www.mathhelpforum.com/math-he...71b264d4-1.gif can only be 1 if there is only 1 prime and its 2. But then no 3 to make 6.

Case 2: $1\cdot 6$ where I get that there is a single prime 7. Then I also get n = 14 because $\phi(2\cdot 7) = 1\cdot 6$

Case 3: $2\cdot 3$
here I get $\left[p_1^{r_1-1}\cdot ... \cdot p_k^{r_k-1}\right] = 2$ so then there is one prime 2 raised to the power of 2, then all others raised to the power of 1.

But http://www.mathhelpforum.com/math-he...71b264d4-1.gif = (2 - 1) $\cdot ... (p_k - 1)$ = 3 and this is not possible.

Case 4: $2\cdot 3$

$\left[p_1^{r_1-1}\cdot ... \cdot p_k^{r_k-1}\right] = 3$ so there is one prime 3 raised to the power of 2 and all others raised to 1.

So (3-1) $\cdot ... (p_k - 1)$ = 2 $\cdot ... (p_k - 1)$ = 2 so there is only one other prime which is 2. Giving me $3^2\cdot 2$ = 18

but i know i'm supposed to get a 9 from somewhere. I can't see where tho. Sorry to be a pain. Thank you for all the help.

Katy :)