How to compute the value of $$[\gcd(1,x)+\gcd(2,x)+\gcd(3,x)+....+\gcd(x,x)]$$ efficiently?
When x can be as large as million.



Calculating greatest common divisor series: $\gcd(1,x)+\gcd(2,x)+\gcd(3,x)+....+\gcd(x,x)$
It seems the most efficient way to compute it is though the prime number decomposition of $x$. if $x$ is only "as large as million" it is still relatively effective.


Assume first that $x = a b $ with $a$ and $b$ prime between them. Then:


$$  \sum\_{i=1} ^ x \gcd(x,i) = \sum\_{i \in (\mathbb{Z}/x \mathbb{Z})} \gcd(i,a) \gcd(i,b) = \sum\_{i \in \mathbb{Z}/a\mathbb{Z}} \gcd(i,a) \sum\_{j \in \mathbb{Z}/b\mathbb{Z}} \gcd(j,b) $$


Hence the value of your sum for $x$ is the product of its value for $a$ and for $b$, hence if one factor $x$ as a product of prime power $x= \prod\_k p\_k ^{a\_k}$ it is enough to compute the sum for a prime power.


The case of $p^k$ is relatively easy to compute explicitly, and one obtain (if I'm correct) that:


$$ \gcd(x,1)+ \gcd(x,2)+ ... +\gcd(x,x) = x \prod\_{k} \left[ a\_k \left(1- \frac{1}{p\_k}\right) +1 \right] $$


Conversely, knowing the value of this sum precisely will give you very precise information on the property of the prime decomposition of $x$ (for example, $x$ is prime if and only if the sum is $2x-1$) so it is very unlikely that you can get the value without factoring $x$ first.


