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 phi function

  1. Feb 21, 2010 #1
    "Let m and k be positive integers and φ(m) is the Euler's phi function. Then the number of integers n such that 1≤n≤mk and (n,m)=1 is kφ(m)."


    I can't figure out why this is true. How can we prove it?

    Can someone explain this, please?
    Any help is appreciated!
     
  2. jcsd
  3. Feb 21, 2010 #2
    Coprimes repeat in a kind of "modular" fashion. You may try using the division algorithm on n, and expressing it as n=qm+r; then try to prove that (n,m)=(r,m).
     
  4. Feb 21, 2010 #3
    hmm...sorry I don't understand. What do you mean by "Coprimes repeat in a kind of 'modular' fashion"?
     
  5. Feb 21, 2010 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    If c is coprime to m, then c+m is coprime to m, and in general c+km is coprime to m.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Euler's phi function
  1. Euler, phi and division (Replies: 11)

  2. Euler phi function (Replies: 5)

  3. Euler phi function (Replies: 7)

Loading...