辗转相除法求公约数.ppt

文档介绍：定理:设有不全为0的正整数m、n和r,且
m = n × q + r (0≤r<n, q是个整数)
那么,m与n的最大公因子等于n和r的最大公因子。
证明:设x = m与n的最大公因子, y = n与r的最大公因子

1. x是m的因子,同时,x既是n的因子,x也是r的因子, 因此x≤y
2. y是r的因子,同时, y既是n的因子,y也是m的因子,因此y≤x
综上,x=y
定理:设有不全为0的正整数m、n和r,且
m = n × q + r (0≤r<n, q是个整数)
那么,m与n的最大公因子等于n和r的最大公因子。
设有正整数m和n,且m>n(若不然,交换二者的值),则
m = n × q0 + r0 (0≤r0<n, q0是个整数,若r0为0,则n能整除m)
n = r0 × q1 + r1 (0≤r1< r0,q1是个整数)
r0 = r1 × q2 + r2 (0≤r2< r1,q2是个整数)
…
rk-2 = rk-1 × qk + rk (0≤rk< rk-1 , qk是个整数)
rk-1 = rk × qk+1 + rk+1 (0≤rk+1< rk, qk+1是个整数)
rk = rk+1 × qk+2 + rk+2 (rk+2= 0, qk+2是个整数)
rk+1是rk的因子, rk+1是rk+1与rk的最大公因子。