Proving Euler's Phi Function: Any Help Appreciated!

[kingwinner]

"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!

 

[dodo]

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).

 

[kingwinner]

hmm...sorry I don't understand. What do you mean by "Coprimes repeat in a kind of 'modular' fashion"?

 

[CRGreathouse]

hmm...sorry I don't understand. What do you mean by "Coprimes repeat in a kind of 'modular' fashion"?

If c is coprime to m, then c+m is coprime to m, and in general c+km is coprime to m.