algorithms - Find gcd($a,c$) with gcd($a,b$) and gcd($b,c$) is given?

Suppose gcd($a,b$) and gcd($b,c$) are given. How can we find gcd($a,c$)? (gcd($x,y$) is the greatest common divisor of $x$ and $y$). Any help is appreciated.

Answer

GCD as such has no transitive properties at all.

For example, you can take an extreme case : Let $a = p$, let $b=1$ and let $c = p$. Then, while $\gcd(a,b) = \gcd(b,c) = 1$, it so happens that $\gcd(a,c) = p$. Taking $p$ as large enough as you want, you can see that there is no relationship at all between the suggested quantities.