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
Let's say there is some $$$i$$$ such that $$$\gcd(i,n) = d$$$. This would imply that there exists $$$i'$$$ and $$$n'$$$ such that $$$i'$$$ and $$$n'$$$ are coprime and $$$di'= i$$$ and $$$dn' = n$$$. If there exists $$$i'$$$ that is coprime to $$$n'$$$, then it is easy to see $$$\gcd(di', n) =\gcd(di', dn') = d$$$. Since all numbers $$$i$$$ that have $$$\gcd(i,n) = d$$$ correspond to exactly one $$$i'$$$ that is coprime to $$$n'$$$, and vice versa. We can claim they are equal in number.
The number of such $$$i'$$$, is $$$\phi(n') = \phi(n/d)$$$