Results 1 to 8 of 8

Math Help - Combinatorial Study of Phi(n)

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by kyldn6 View Post
    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<a_i\in \mathbb{N}, 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!

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    Quote Originally Posted by tonio View Post
    If m=\prod\limits_{n=1}^r p_i^{a_i}  \,,\,\,p_i\,\,primes\,,\,\,0<a_i\in \mathbb{N}, 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!

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    For the second question see here...

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

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by harkapobi View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    I'm sorry, i know i'm probably being really dumb but I still dont get it.

    2^{2}3

    How do you find n?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by harkapobi View Post
    I'm sorry, i know i'm probably being really dumb but I still dont get it.

    2^{2}3

    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    Ok, I understand that I think. My question is actually \phi(n) = 6

    So I have
    Case 1: 6\cdot 1 where 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 = (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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help on Study Guide
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 11th 2011, 11:13 AM
  2. A study shows...
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 24th 2010, 03:54 PM
  3. combinatorial sum
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2009, 10:46 AM
  4. What to study?
    Posted in the Statistics Forum
    Replies: 21
    Last Post: June 2nd 2008, 10:46 PM
  5. Study
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 29th 2008, 05:21 PM

Search Tags


/mathhelpforum @mathhelpforum