Page 1 of 2 12 LastLast
Results 1 to 15 of 23

Math Help - Euler Function phi(n)

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Euler Function phi(n)

    Hello All,

    I am reading about the Euler Function phi(n), which my book defines counts the number of positive integers less then or equal to n, which are relatively prime. The book has a couple examples of how this works, but I do have some questions about a couple of the examples:

    1. \sum_{d|n}^{} phi(d) can be evaluated and proven correct. Can someone explain this?

    2. Analyzing n:
    If n is odd, then phi(2n)=phi(n)
    If n is even, then phi(2n)=2*phi(n).
    How can this be proven?

    3. An n exists where phi(n)=phi(n+1)=phi(n+2). What is the n?
    There are a few guidelines to this one, it says try taking phi(n)=2592. Then note that phi(2n)=phi(n) when n is odd. Then note that phi(p)=p-1 for a prime 'p'.

    Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie BBAmp's Avatar
    Joined
    May 2010
    From
    Cleveland,OH/Madison,WI/Queens,NY
    Posts
    17
    1. I think you may have meant to say : \sum_{d|n}{phi(n)} = n in which case you can work it out like so - a method by Gauss that I learned from my book - and I'll go through it step by step since I am new to this myself:

    Suppose n = 12 and we have a class of numbers C_{d} where C_{d} holds any number less than n that has its highest divisor as d. Then we have a set of classes:
    C_{1} = \{1, 5, 7, 11\}
    C_{2} = \{2, 10\}
    C_{3} = \{3, 9\}
    C_{4} = \{4, 8\}
    C_{6} = \{6\}
    C_{12} = \{12\}

    A number m only exists in C_{d} if (m, n) = d. Further, (m/d, n/d) = 1 so a number m only exists in C_{d} if m/d and n/d are relatively prime. By definition the number of integers less than n/d and relatively prime to n/d is \phi(n/d) so the number of elements in C_{d} is \phi(n/d).

    From here it is a simple matter.

    We just proved that \sum_{d|n}{phi(d/n)} = n and if you work it out manually with a small number like n = 12 you will find that \sum_{d|n}{phi(d/n)} = \sum_{d|n}{phi(n)} and with that we have proved \sum_{d|n}{phi(n)} = n

    For the record I relied quite heavily on my book for much of the above so I cannot take credit for this work.

    2. I know there is a much more complete way of proving this, but at the moment I can only think of a proof by contradiction:

    Lets suppose \phi(2n) = \phi(n) works for even numbers as well. If n = 2^1, then we can use the equation \phi(p^{e}) = p^{e-1}(p-1) where p is a prime and e is its power. If we work it out with n = 2 (a prime) then \phi(4) = 2^0(2-1) = 2 while \phi(2) = 1. We have reached a contradiction and we at least know for the even number 2 this does not work. The only problem is I do not know how to extend this to all even numbers. This is a very weak proof and I would like to see someone else write one better.

    3. I can't figure this one out either.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Is the statement \sum_{d|n}{phi(n)} = n true? My book just says "it can be evaluated", it doesn't say what it is equal too.

    Also, can anyone confirm his results?

    Does anyone also have an idea of approaching my 3rd point?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie BBAmp's Avatar
    Joined
    May 2010
    From
    Cleveland,OH/Madison,WI/Queens,NY
    Posts
    17
    If your book just says it can be evaluated then I believe I have shown that it in fact can though there may be a more direct proof showing that it can be evaluated. I hope my example helped
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by BBAmp View Post
    If your book just says it can be evaluated then I believe I have shown that it in fact can though there may be a more direct proof showing that it can be evaluated. I hope my example helped
    Yes, I just hope someone can confirm your 2nd point result and someone can chime in on my 3rd point question. Thank you for all your help thus far! Let's keep rolling with this!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    1.) This proof comes from Apostol's book on analytic number theory.

    Let  N=\{1,2,3,\ldots,n\} . For each divisor  d of  n define  S(d) = \{k \; | \; (k,n)=d, \; 1\leq k \leq n \} i.e  S(d) contains all elements of  N which have gcd  d with  n . The sets  S(d) form a disjoint collection whose union is  N . Thus if  f(d) denotes the number of integers in  S(d) , we have  \sum_{d\mid n}f(d) = n .

    But  (k,n)=d \iff (k/d,n/d)=1 and  1\leq k \leq n \iff 1\leq k/d \leq n/d . So if we let  q=k/d there is a one-to-one correspondence between the elements in  S(d) and those integers  q satisfying  1\leq q \leq n/d and  (q,n/d)=1 . The number of such  q is  \phi(n/d) . Thus  f(d) = \phi(n/d) .

    Therefore  n = \sum_{d\mid n} \phi(n/d) = \sum_{d\mid n} \phi(d) .

    3.) The only number known that satisfies this property is  n=5186 .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    1.) This proof comes from Apostol's book on analytic number theory.

    Let  N=\{1,2,3,\ldots,n\} . For each divisor  d of  n define  S(d) = \{k \; | \; (k,n)=d, \; 1\leq k \leq n \} i.e  S(d) contains all elements of  N which have gcd  d with  n . The sets  S(d) form a disjoint collection whose union is  N . Thus if  f(d) denotes the number of integers in  S(d) , we have  \sum_{d\mid n}f(d) = n .

    But  (k,n)=d \iff (k/d,n/d)=1 and  1\leq k \leq n \iff 1\leq k/d \leq n/d . So if we let  q=k/d there is a one-to-one correspondence between the elements in  S(d) and those integers  q satisfying  1\leq q \leq n/d and  (q,n/d)=1 . The number of such  q is  \phi(n/d) . Thus  f(d) = \phi(n/d) .

    Therefore  n = \sum_{d\mid n} \phi(n/d) = \sum_{d\mid n} \phi(d) .

    3.) The only number known that satisfies this property is  n=5186 .
    Thank you! A few comments:

    -Do you know how to prove the second point I listed in my original post?
    -How did you come to n=5186 ? Is there some sort of proof or methodology?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    Thank you! A few comments:

    -Do you know how to prove the second point I listed in my original post?
    -How did you come to n=5186 ? Is there some sort of proof or methodology?
    3.) As far as I know, there isn't a proof or methodology...

    2.) If  n is odd, then  \phi(2n) = \phi(2)\phi(n)\ldots


    What are these problems for?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    3.) As far as I know, there isn't a proof or methodology...

    2.) If  n is odd, then  \phi(2n) = \phi(2)\phi(n)\ldots


    What are these problems for?
    3. So where did you come up with the number?

    2. What is your relation pointing out? I'm missing the link and how it relates to 1729.

    These problems are "suggested exercises" and examples that my book gives. Point 2 came from my book stating, "There exists a set of numbers that are pseudoprimes, e.g. 1729" , and I didn't understand why. I casually am trying to get back into mathematical studying after being out of it for so long. I figured Number Theory was a good place to start, followed by combinatorics (which I'll get into once I finish getting through this book).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    3. So where did you come up with the number?

    2. What is your relation pointing out? I'm missing the link and how it relates to 1729.
    Since  n is odd,  (2,n)=1 . Thus  \phi(2n) = \phi(2)\phi(n) = \phi(n) because  \phi(2)=1 .
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    Since  n is odd,  (2,n)=1 . Thus  \phi(2n) = \phi(2)\phi(n) = \phi(n) because  \phi(2)=1 .
    I'm sorry, I'm just not seeing how you're connecting the dots here.

    If you could give the explicit example of how your relationship applies to the number 1729 that would greatly help.

    Also, is there any sort of method to the madness for how you got that other number? Where did you find it from?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie BBAmp's Avatar
    Joined
    May 2010
    From
    Cleveland,OH/Madison,WI/Queens,NY
    Posts
    17
    Quote Originally Posted by 1337h4x View Post
    I'm sorry, I'm just not seeing how you're connecting the dots here.

    If you could give the explicit example of how your relationship applies to the number 1729 that would greatly help.

    Also, is there any sort of method to the madness for how you got that other number? Where did you find it from?
    for the first part if you're still not seeing it: \phi(2) is the same as 1. So \phi(2)\phi(n) = \phi(n) and this works for all odd numbers because  (2, n) = 1. That's about as simple as it gets.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by BBAmp View Post
    for the first part if you're still not seeing it: \phi(2) is the same as 1. So \phi(2)\phi(n) = \phi(n) and this works for all odd numbers because  (2, n) = 1. That's about as simple as it gets.
    So how do you prove that if n is even that phi(2n)=2*phi(n) ?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie BBAmp's Avatar
    Joined
    May 2010
    From
    Cleveland,OH/Madison,WI/Queens,NY
    Posts
    17
    suppose (2, n) = 2 or in other words n is an even number. Also remember our original equation for even numbers that we are looking to prove ( \phi(2n)= \phi(2)\phi(n) = 2\phi(n))

    The definition of \phi(n) is as follows:

    \phi(n) = n(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})

    Using this definition if you take \phi(n/2) you get \phi(n/2) = n/2(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})

    if you multiply \phi(n/2) by 2 you get 2\phi(n/2) = 2(n/2(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})) which by simple cancellation of the 2 becomes

    2\phi(n/2) = n(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k}) = \phi(n).

    That proves that \phi(2n)= \phi(2)\phi(n) = 2\phi(n)

    I think I may have run into an error and I might be wrong. I don't have time at the moment so if you can spot it please point it out and I will get back to this later.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by BBAmp View Post
    suppose (2, n) = 2 or in other words n is an even number. Also remember our original equation for even numbers that we are looking to prove ( \phi(2n)= \phi(2)\phi(n) = 2\phi(n))

    The definition of \phi(n) is as follows:

    \phi(n) = n(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})

    Using this definition if you take \phi(n/2) you get \phi(n/2) = n/2(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})

    if you multiply \phi(n/2) by 2 you get 2\phi(n/2) = 2(n/2(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})) which by simple cancellation of the 2 becomes

    2\phi(n/2) = n(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k}) = \phi(n).

    That proves that \phi(2n)= \phi(2)\phi(n) = 2\phi(n)

    I think I may have run into an error and I might be wrong. I don't have time at the moment so if you can spot it please point it out and I will get back to this later.
    did anyone else find an error? I was just confused about why you used n/2 as your example and how you at all used the fact that (2,n)=2 ...
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Euler Phi function II
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 27th 2009, 04:33 AM
  2. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 16th 2008, 05:54 PM
  3. Euler's Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 02:52 PM
  4. euler phi function and others
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 4th 2008, 05:43 PM
  5. Help with euler-phi function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 1st 2007, 06:42 PM

Search Tags


/mathhelpforum @mathhelpforum