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