Problem related to Euler Toitent Property

Revision en1, by Evan_Shareef, 2020-08-30 08:40:55

https://forthright48.com/spoj-lcmsum-lcm-sum/

I found this blog extremely helpful . But I can't understand one line. If anyone summarize it to me then it would be helpful. It says ,

"How many values i can we put such that gcd(i,n)=d? There are ϕ(n/d) possible values of i for which we get gcd(i,n)=d. "

My question is how we can conclude this that ; number of possible pairs for any i with n where gcd(i,n) = d will be phi(n/d) ? Can anyone explain it ? Or suggest some blog that can actually help me to understand the concept.

Thanks in advance

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Evan_Shareef 2020-08-30 08:40:55 602 Initial revision (published)