le 0 y true le s x 0 false le s x s y le x y minus x 0 x minus s x s y minus x y gcd 0 y y gcd s x 0 s x gcd s x s y if_gcd le y x s x s y if_gcd true s x s y gcd minus x y s y if_gcd false s x s y gcd minus y x s x gcd 2.2 gcd x y gcd y x gcd x y gcd y x if_gcd true s x s y minus x y minus s x s y minus x y gcd s x s y le y x le s x s y le x y if_gcd false s x s y minus y x if_gcd true s x s y gcd minus x y s y gcd s x s y if_gcd le y x s x s y if_gcd false s x s y gcd minus y x s x if_gcd false s x s y gcd minus y x s x gcd s x s y if_gcd le y x s x s y if_gcd true s x s y gcd minus x y s y gcd x y gcd y x true le 2 1 2 1 s 1 1 2 le 2 0 minus 2 1 0 gcd 2 0 false 0 5 true 0 3 0 0 1 minus 2 0 if_gcd 3 0 if_gcd 3 2 3 0 gcd 2 1 2 1 if_gcd true s x s y gcd minus x y s y gcd s x s y if_gcd le y x s x s y if_gcd false s x s y gcd minus y x s x minus x 0 x minus s x s y minus x y gcd x y gcd y x true gcd s x s y le y x false if_gcd false s x s y minus y x false le s x s y le x y true le 2 1 2 1 s 1 1 1 le 2 1 2 0 minus 2 1 0 gcd 2 0 false 0 5 true 0 3 0 0 1 minus 2 0 if_gcd 3 0 if_gcd 3 0 gcd 2 1 2 1 le s x s y le x y minus x 0 x minus s x s y minus x y if_gcd true s x s y minus x y false minus s x s y minus x y true le 2 1 2 1 s 1 1 1 le 2 0 minus 2 1 0 gcd 2 0 false 0 5 true 0 3 0 0 1 minus 2 1 2 0 if_gcd 3 0 if_gcd 3 0 gcd 2 1 2 1 minus s x s y minus x y minus x 0 x minus s x s y minus x y NaTT certifiable-1.6