从各个方程本身来看是存在解的.对于第一个方程,gcd(1,-2,1)=1能够整除0,而对于第二个方程,gcd(3,2,1)=1能够整除5.但是,如果我们求解第一个方程得到z=2y-x,并以此替代第二个方程中的z,我们得到2x+4y=5.因为gcd(2,4)=2不能整除5,所以这个丢番图方程无解.
欧几里德算法
欧几里德算法按照下面的方法找出gcd(a,b)的值.首先,假设a和b为正整数,且a≥b.请注意,多个负数的GCD,或一个负数与一个正数的GCD等于它们的绝对值的GCD,因此可以假设所有的整数都是正的.
如果a=b,那么gcd(a,b)=a.如果a>b,令c为a/b的余数.如果c=0,那么b整除a,因此gcd(a