SPOJ LCMSUM - LCM Sum | forthright48

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

visit code n code channel number theory playlist

1 Like


Here you can find the proof. :slightly_smiling_face:

1 Like

Its a whole play list!! Thanks man!