辗转相除法求最大公因数的原理（辗转相除法求最大公因数方法讲解）

设两个数为a和b且a大于b，设最大公因数为z，(两数至少肯定有公因数1)，如果a不能整除b，则有个余数，即a÷b=n余C，因此a和nb必定能被z整除，再用b÷C=能整除的话，C就是α和b的最大公因数(即z)。