minus X s Y pred minus X Y minus X 0 X pred s X X le s X s Y le X Y le s X 0 false le 0 Y true gcd 0 Y 0 gcd s X 0 s X gcd s X s Y if le Y X s X s Y if true s X s Y gcd minus X Y s Y if false s X s Y gcd minus Y X s X 2.2 gcd s X s Y le Y X if true s X s Y minus X Y le s X s Y le X Y minus X s Y pred minus X Y if true s X s Y gcd minus X Y s Y if false s X s Y gcd minus Y X s X gcd s X s Y if le Y X s X s Y minus X s Y minus X Y if false s X s Y minus Y X true gcd s X s Y if le Y X s X s Y if false s X s Y gcd minus Y X s X if true s X s Y gcd minus X Y s Y true le 2 1 s 1 1 3 le 2 0 minus 2 1 1 gcd 2 0 false 0 2 true 0 2 pred 1 1 0 0 0 2 if 3 0 minus 2 0 pred 1 0 if 3 2 3 0 gcd 2 1 2 1 minus X s Y pred minus X Y pred s X X minus X 0 X if false s X s Y minus Y X false if true s X s Y minus X Y false minus X s Y minus X Y true le 2 1 s 1 1 3 le 2 0 minus 2 1 1 gcd 2 0 false 0 2 true 0 2 pred 1 1 0 0 0 1 if 3 0 minus 2 2 0 pred 1 0 if 3 0 gcd 2 1 1 minus X s Y pred minus X Y pred s X X minus X 0 X minus X s Y pred minus X Y false gcd s X s Y le Y X false le s X s Y le X Y true le 2 1 s 1 1 3 le 2 1 0 minus 2 1 1 gcd 2 0 false 0 2 true 0 2 pred 1 1 0 0 0 1 if 3 0 minus 2 0 pred 1 0 if 3 0 gcd 2 1 1 minus X s Y pred minus X Y pred s X X minus X 0 X NaTT certifiable-1.6