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
Unable to parse markup [type=CF_MATHJAX]
. This would imply that there exists $$$i'$$$ and $$$n'$$$ such that $$$i'$$$ and $$$n'$$$ are coprime andUnable to parse markup [type=CF_MATHJAX]
andUnable to parse markup [type=CF_MATHJAX]
. If there exists $$$i'$$$ that is coprime to $$$n'$$$, then it is easy to seeUnable to parse markup [type=CF_MATHJAX]
. Since all numbers $$$i$$$ that haveUnable to parse markup [type=CF_MATHJAX]
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
Unable to parse markup [type=CF_MATHJAX]