mathmathematical-optimizationeuclidean-algorithm

How we can find GCD(k + a, k + b) if we already know the GCD(a, b)?

I was wondering if its possible in constant time to calculate the above mentioned goal. I need it to solve a problem on codechef.

Solution

  • It is impossible to compute gcd(a+k,b+k) in constant time knowing only gcd(a,b).

    Suppose that c,d are any two natural numbers with d < c.

    Let

    a = d - d = 0
b = c - d
k = d

    Then we know in O(1) time that

    gcd(a,b) = gcd(0, c - d) = c - d

    If we could compute gcd(a+k,b+k) = gcd(c,d) in O(1) additional time, then we could compute all gcds in O(1) time, which is impossible.

    Having said all that, it is of course possible that in some cases of interest, knowledge of gcd(a,b) could lead to faster computation of gcd(a+k,b+k) than would otherwise be possible.