Calculating greatest common divisor series: $\gcd(1,x)+\gcd(2,x)+\gcd(3,x)+....+\gcd(x,x)$ 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.
 A: 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.
