Results 1 to 8 of 8

Math Help - Phi(n)

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Phi(n)

    Let phi(n) = # of pos. integers < n that's relatively prime to n.

    1.) Theorem: phi(n) | n if and only if _______

    a.) Show three numbers that will satisfy phi(n) | n.

    b.) Fill in the above blank.

    c.) Prove this theorem.



    -------------

    What I know about phi(n)...

    n is prime iff phi(n) = n - 1

    phi(n) is a multiplicative func.... that is, phi(n) = phi((p_1)^(a_1)*phi((p_2)^(a_2)*...*phi((p_k)^(a_k )

    A formula for phi(n) ...

    n*(1 - 1/(p_1))*(1 - 1/(p_2))* ... *(1 - 1/(p_k))
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    Let phi(n) = # of pos. integers < n that's relatively prime to n.

    1.) Theorem: phi(n) | n if and only if _______
    Are you sure this has an easy answer to it. It looks a little too extreme for me.

    I would guess the following....

    Conjecture: All the positive integers described above are:
    1,2, 2^n, 2^a*3^b
    Where n,a,b are positive integers.

    I leave it to you to show that phi(n) will divide n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2006
    Posts
    221
    According to my prof. this is not correct TPH. I have to apparently look at some values. I am trying it again now and will see what I can come up with. If you have any suggestions please let me know.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2006
    Posts
    221
    Okay, I did what my prof. suggested but it didn't (seem) to help:

    When n = 1, phi(n) = 1

    n = 2, phi(n) = 1

    Below will be n = the first number and phi(n) will = the second number.

    3...2
    4...2
    5...4
    6...2
    7...6
    8...4
    9...6
    10...4
    11...10
    12...4
    13...12
    14...6
    15...8
    16...8
    17...16
    18...6
    19...18
    20...8
    21...12
    22...10
    23...22
    24...8
    25...20
    26...12
    27...18
    28...12
    29...28
    30...8
    31...30
    32...16
    33...20
    34...16
    35...24
    36...12
    37...36
    38...18
    39...24
    40...16
    41...40
    42...12
    43...42
    44...20
    45...24
    46...22
    47...46
    48...16
    49...42
    50...20
    .
    .
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Actually I think I am correct. I managed to proof it.

    I will try to post a proof, it is a little long.
    And LaTeX is down, I will modify this post with my first LaTeX image, for you to read.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2006
    Posts
    221
    Quote Originally Posted by ThePerfectHacker View Post
    Actually I think I am correct. I managed to proof it.

    I will try to post a proof, it is a little long.
    And LaTeX is down, I will modify this post with my first LaTeX image, for you to read.
    Haha, smarter than a professsor..

    It was also suggested that I list the numbers and break them into prime factorization
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    Haha, smarter than a professsor..

    It was also suggested that I list the numbers and break them into prime factorization
    Here is my first LaTeX post.
    Attached Thumbnails Attached Thumbnails Phi(n)-picture20.gif  
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Continued.

    Note, when I show that r=3.

    That means,

    n=2^a*3^b for n>2 exactly what I said.

    (This is a necesary condition. I assume that it is also sufficient. But that is easy if it is really true. I leave the easy part to thee).
    Attached Thumbnails Attached Thumbnails Phi(n)-picture21.gif  
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum