Results 1 to 13 of 13

Math Help - Euler's phi function

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    4

    Euler's phi function

    I'm 14, and have been given a project over the holidays. It's about Euler's phi function and I am completely stuck. I've been struggling through the project and am particulary stuck on two questions.

    If we take P as a prime number, obtain an expression for phi(p^3). So far, I know that
    phi(3^3)=18
    phi(5^3)=100
    phi(7^3)=294

    I don't know how to obtain an expression. If it helps, phi(p^2)=p(p-1)

    I don't even know wehre to get started on phi(p^n) as well.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by xWhiteyx View Post
    I'm 14, and have been given a project over the holidays. It's about Euler's phi function and I am completely stuck. I've been struggling through the project and am particulary stuck on two questions.

    If we take P as a prime number, obtain an expression for phi(p^3). So far, I know that
    phi(3^3)=18
    phi(5^3)=100
    phi(7^3)=294

    I don't know how to obtain an expression. If it helps, phi(p^2)=p(p-1)

    I don't even know wehre to get started on phi(p^n) as well.
    Hello Whitey,

    Quick question, what definition of Euler's Phi function are you using? I ask because there are many equivalent definitions for it, and helping you might be difficult not knowing which one you are using.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    4
    Quote Originally Posted by pomp View Post
    Hello Whitey,

    Quick question, what definition of Euler's Phi function are you using? I ask because there are many equivalent definitions for it, and helping you might be difficult not knowing which one you are using.
    Two positive intergers are coprime if they have no factors other than 1 in common. For any positive interger n, the phi function phi(n) is defined as the number of positive intergers less than n, which are coprime to it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by xWhiteyx View Post
    Two positive intergers are coprime if they have no factors other than 1 in common. For any positive interger n, the phi function phi(n) is defined as the number of positive intergers less than n, which are coprime to it.
    OK that's cool, I thought that would be it although I'm really surprised you managed to compute \phi(7^3) using that definition!

    Consider the nth power of a prime, p^n, what numbers less than this share a factor with p^n ?

    Firstly what are the factors of p^n ? Clearly just 1 and p. So any number less than p^n that share a factor must have p as a factor. Can you figure out how many such numbers there are? When you work this out, subtract this number from p^n and you will have the result for  \phi(p^n)  (Effectively what you have done, is instead of working out how many numbers are coprime, you have worked out how many are not coprime, and subtracted this from p^n)

    This will give you a quick generel result for \phi(p^n) and you can just change the n to a three to give you your answer.


    Good luck, and let us know where you get stuck.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2010
    Posts
    4
    Quote Originally Posted by pomp View Post
    OK that's cool, I thought that would be it although I'm really surprised you managed to compute \phi(7^3) using that definition!

    Consider the nth power of a prime, p^n, what numbers less than this share a factor with p^n ?

    Firstly what are the factors of p^n ? Clearly just 1 and p. So any number less than p^n that share a factor must have p as a factor. Can you figure out how many such numbers there are? When you work this out, subtract this number from p^n and you will have the result for  \phi(p^n)  (Effectively what you have done, is instead of working out how many numbers are coprime, you have worked out how many are not coprime, and subtracted this from p^n)

    This will give you a quick generel result for \phi(p^n) and you can just change the n to a three to give you your answer.


    Good luck, and let us know where you get stuck.
    Right, SO these are my workings- can you tell me if I have gone wrong or can you help me with certain bits. (Forgiver me if I copy you a bit.)

    The factors of P^n are 1 and P. Any number less than P^n that shares a factor must have p as a factor. (yeah, you told me that.... :P )

    there are 3 numbers less than p^n. These are 1, P, and P^2.
    Therefore phi(P^n)=P^n-3

    But that doesn't work, because there are also common factors. For example, with 5^3 you have to take in all the factors of 5.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by xWhiteyx View Post
    Right, SO these are my workings- can you tell me if I have gone wrong or can you help me with certain bits. (Forgiver me if I copy you a bit.)

    The factors of P^n are 1 and P. Any number less than P^n that shares a factor must have p as a factor. (yeah, you told me that.... :P )

    there are 3 numbers less than p^n. These are 1, P, and P^2.
    Therefore phi(P^n)=P^n-3

    But that doesn't work, because there are also common factors. For example, with 5^3 you have to take in all the factors of 5.
    The mistake you have made is that I said the numbers share a factor, not have only p as a factor.

    Take 3^3 for example. Which numbers less than 27 share a factor with it?

    Clearly 1 does, 2 doesn't, 3 does, 4 doesn't, 5 doesn't. Does 6? Are 6 and 27 coprime? No, since 6 factors as 2*3, and so shares a factor of 3 with 27, yet it is't a power of three.

    Can you see where to go now?
    Last edited by pomp; January 10th 2010 at 01:15 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2010
    Posts
    4
    Quote Originally Posted by pomp View Post
    The mistake you have made is that I said the numbers share a factor, not have only p as a factor.

    Take 3^3 for example. Which numbers less than 27 share a factor with it?

    Clearly 1 does, 2 doesn't, 3 does, 4 doesn't, 5 doesn't. Does 6? Are 6 and 27 coprime? No, since 6 factors as 2*3, and so shares a factor of 3 with 27, yet it is't a power of three.

    Can you see where to go now?
    so 1, and all the factors of p go into p. So with 3^3, it's every 3rd, with 5^3, It's every 5th and so on. But I need to obtain an expression for that, and frankly, that just isn't coming into my head right now- and I'm still on the easy questions. ;(
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by xWhiteyx View Post
    so 1, and all the factors of p go into p. So with 3^3, it's every 3rd, with 5^3, It's every 5th and so on. But I need to obtain an expression for that, and frankly, that just isn't coming into my head right now- and I'm still on the easy questions. ;(
    Totient Function -- from Wolfram MathWorld
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by xWhiteyx View Post
    so 1, and all the factors of p go into p. So with 3^3, it's every 3rd, with 5^3, It's every 5th and so on. But I need to obtain an expression for that, and frankly, that just isn't coming into my head right now- and I'm still on the easy questions. ;(
    You've got it! You're so close, just keep going.

    If every third number of 27 has a factor in common, how many such numbers are there? Can you see why it's just 27/3 ? Can you finish now?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    The 'fundamental theorem of arithmetic' extablishes that for any integer n is...

    n=p_{1}^{k_{1}}\dots p_{r}^{k_{r}} (1)

    ... where p_{1},\dots , p_{r} are distinct primes, and as consequence is...

    \varphi(n)= (p_{1}-1)\cdot p_{1}^{k_{1}-1} \dots (p_{r}-1)\cdot p_{r}^{k_{r}-1} (2)

    If r=1 is...

    \varphi(n)= (p-1)\cdot p^{k-1} (3)

    ... and for k=3 is...

    \varphi(p^{3})= (p-1)\cdot p^{2} (4)

    Kind regards

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

  11. #11
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by chisigma View Post
    The 'fundamental theorem of arithmetic' extablishes that for any integer n is...

    n=p_{1}^{k_{1}}\dots p_{r}^{k_{r}} (1)

    ... where p_{1},\dots , p_{r} are distinct primes, and as consequence is...

    \varphi(n)= (p_{1}-1)\cdot p_{1}^{k_{1}-1} \dots (p_{r}-1)\cdot p_{r}^{k_{r}-1} (2)

    If r=1 is...

    \varphi(n)= (p-1)\cdot p^{k-1} (3)

    ... and for k=3 is...

    \varphi(p^{3})= (p-1)\cdot p^{2} (4)

    Kind regards

    \chi \sigma
    Although this is correct, OP is 14 and is doing this as a project, I don't think he'd be able to get away with saying

    The 'fundamental theorem of arithmetic' establishes that for any integer n is

    n=p_{1}^{k_{1}}\dots p_{r}^{k_{r}}

    ... where p_{1},\dots , p_{r} are distinct primes, and as consequence is...

    \varphi(n)= (p_{1}-1)\cdot p_{1}^{k_{1}-1} \dots (p_{r}-1)\cdot p_{r}^{k_{r}-1}



    Besides, he so nearly got there on his own.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    The fact that OP is 14 doesn't mean that He doesn't understand the mathematical language... in fact He spoke of 'Euler phi function' and I dont think that He has heard this in a Lady Gaga's song ...

    Kind regards

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

  13. #13
    Member
    Joined
    Jun 2009
    Posts
    220
    Thanks
    1
    Quote Originally Posted by chisigma View Post
    The fact that OP is 14 doesn't mean that He doesn't understand the mathematical language... in fact He spoke of 'Euler phi function'

    \chi \sigma

    Sorry, I didn't mean to patronise OP by implying he wouldn't understand the language, all I meant was that by the age of 14, the material you would have covered probably wouldn't allow the step from TFA to the formula for phi(n).
    You usually do it the other way round anyway, the formula for phi(n) is usually deduced from the formula for phi(p^k), not the other way round. Potato potato I suppose.


    I dont think that He has heard this in a Lady Gaga's song...

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler Function phi(n)
    Posted in the Number Theory Forum
    Replies: 22
    Last Post: May 29th 2010, 07:29 AM
  2. the Euler φ-function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 31st 2010, 02:59 AM
  3. euler phi-function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 29th 2009, 07:42 PM
  4. Euler's Phi Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 26th 2009, 04:42 PM
  5. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 29th 2008, 04:07 AM

Search Tags


/mathhelpforum @mathhelpforum