GCD binary representation time complexity
Assuming x &lt;= y and no particularly clever division, it's O (x log x log x), if you don't divide y by I if x is already not divisible by I. 

If z divides x and y then you just need to check if gcd (x/z, y/z) = 1. And only test 2 &lt;= I &lt;= sqrt (x) and x itself.