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


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook