gcd x 0 x gcd 0 y y gcd s x s y if < x y gcd s x - y x gcd - x y s y 2.2 gcd s x s y gcd - x y s y gcd s x s y gcd s x - y x true gcd s x s y gcd s x - y x false gcd s x s y gcd - x y s y false NaTT certifiable-1.6