Euler's phi function

  • Thread starter kingwinner
  • Start date
  • #1
1,270
0

Main Question or Discussion Point

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

Answers and Replies

  • #2
695
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).
 
  • #3
1,270
0
hmm...sorry I don't understand. What do you mean by "Coprimes repeat in a kind of 'modular' fashion"?
 
  • #4
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
 

Related Threads for: Euler's phi function

  • Last Post
Replies
5
Views
11K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
11
Views
12K
Replies
4
Views
8K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
13
Views
15K
Top