最大公因数的求法zuida gongyinshu de qiufa

❶分解素因数法.设a,b都是大于1的整数，a=p₁^α₁p₂^α₂…P_k^α_k,d_i≥0(i=1,2，…，k),b=p₁^β₁P₂^β₂…p_k^β_k,β_i≥0(i=1,2，…，k)，则(a,b) =p₁^r₁p₂^r₂…p_k^r_k，其中r_i＝min (α_i,β_i) (i=1,2，…，k)，这里min (α_i,β_i)表示α_i,β_i中较小的数.例如，求(1 008,1 260,1134).因为1 008=2⁴×3²×7,1 260=2²×3²×5×7,1134=2×3⁴×7，所以(1 008,1 260,1 134)=2×3²×7=126.

❷辗转相除法.一般步骤参见“辗转相除法”.例：求(1 859.1 573).因为1 859=1×1 573+286,1 573=5×286+143,286=2×143+0，并且最后一个不为零的余数是143，故(1 859,1 573)=143.利用辗转相除法求两个以上正整数的最大公因数的具体做法：设a₁,a₂，…，a_n是n个正整数(n≥3).用辗转相除法分别求出(a₁,a₂)=d₂,(d₂,a₃)=d₃，…，(d_n-1,an)=d_n，则(a₁,a₂，…，a_n)=d_n.
由于素因数分解法要首先通过试除求出整数的素因数分解式，因此当它的素因数较大时就不容易分解了，而辗转相除法就避免了这个麻烦.因此辗转相除法是求最大公因数的基本方法.