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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered May 23, 2016 at 16:54
-
1$\begingroup$ Concerning the last point: in the cryptographically interesting situation where $x=pq$ is a product of two distinct primes, the result is $4x+1-2(p+q)$, from which one can easily compute the factors $p$ and $q$. $\endgroup$ Commented May 23, 2016 at 17:15