（a,b）代表最大公因数，则设a,b是不全为零的整数，则存在整数x,y，使得ax+by=（a，b） 证明记d=（a,b），u(k)，k为角标，则由欧几里得算法得，u0 =a，u1=b（这里不妨设b≠0），则由整除的性质，可知d | u(2),d | u(3)……，d | u (k+1)，所以d≤u（k+1） 反过来，再由整除的性质，可由u（k+1） |u（k），u（k+1） | u（k-1），......，u（k+1） | u（1），u（k+1） | u(0),即u（k+1）为a与b的一个公因数，因此，u（k+1）≤d