1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler's totient function

  1. Aug 4, 2014 #1
    1. The problem statement, all variables and given/known data
    How would you calculate, without computers,
    [itex] \phi(m) = 12? [/itex]
    Would you just try enough m integers one by one until it works?
    What if m were bigger like
    [itex] \phi(m) = 52? [/itex]
    Is there a softer way to solve without guessing the number?

    2. Relevant equations
    Number's theory equations

    3. The attempt at a solution
    [itex] \phi(m) = m(1-1/p1)(1-1/p2)... [/itex]
    where p|m
     
  2. jcsd
  3. Aug 4, 2014 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Find the prime factorization. For numbers like these that's easy. Then use the formula you quoted in your attempt at a solution.
     
  4. Aug 4, 2014 #3
    So, without computers, no softer way?
     
  5. Aug 4, 2014 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    For 12 and 52 you don't need a computer to factorize it. The prime factors of 12 are 2 and 3. So ##\phi(12)## is 12(1-1/2)(1-1/3)=4. I didn't need a computer for that. And it's certainly easier than checking all of the numbers from 1...12 to see if they are relatively prime to 12. What kind of numbers are you thinking about? If it's easy to factor it's easy to find the totient.
     
    Last edited: Aug 4, 2014
  6. Aug 4, 2014 #5
    Thanks, but note that
    [itex] \phi(m) = 12 [/itex]
    not m = 12.
    I want to find m.
    xD
     
  7. Aug 4, 2014 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I read the question badly. Sorry. 12 is easy. 13 is prime so ##\phi(13)=12##. All I can suggest is try to use that phi is multiplicative. So if you want 52 then 52=2*26. So one factor should be a number that satisfies ##\phi(m)=2##, plenty of those. Then you want another relatively prime m such that ##\phi(m)=26##. So you can break it down somewhat. I'm sort of getting stuck there.
     
  8. Aug 4, 2014 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Doh, wait. 53 is prime too. So?
     
    Last edited: Aug 4, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Euler's totient function
  1. Euler equations (Replies: 9)

  2. Euler's identity (Replies: 4)

  3. Eulers Formula variant (Replies: 1)

  4. Using Euler's formula (Replies: 3)

  5. Eulers Relationship (Replies: 6)

Loading...