辗转相除法
证明有限性
每次\(r=n\;mod\;m,n=m,n=r\).
因为\(r<m,r\)是正整数,最小为\(1\),所以这个算法是有限的.
证明正确性
求证:\((n,m)=(m,n\;mod\;m)\).
证明:设\((n,m)=k,n=kx,m=ky\),则\((x,y)=1\).
\(n\;mod\;m=n-m\lfloor\frac{n}{m}\rfloor=k(x-y\lfloor\frac{x}{y}\rfloor)\)
所以\(k|(m,n\;mod\;m)\)
\(\\\)
设\(x=ya+b(0\leq{b}<y)\),则\(a=\lfloor\frac{x}{y}\rfloor\).
假设\((y,x-ya)=c(c>1)\).
设\(y=cp,x-ya=cq\),则\((p,q)=1,x=cq+ya=c(q+pa)\).
此时\(c|(x,y)\),与\("(x,y)=1"\)相矛盾.
所以\((y,x-ya)=1\),即\((y,x-y\lfloor\frac{x}{y}\rfloor)=1\).
所以\((m,n\;mod\;m)=k\)
更相减损术
证明有限性
每次\(a'=min(a,b),b'=|a-b|,a=a',b=b'\).
因为\(b'<min(a,b),b'\)是正整数,最小为\(1\),所以这个算法是有限的.
证明正确性
求证:\((n,m)=(m,n-m)\).
证明:设\((n,m)=k,n=kx,m=ky\),则\((x,y)=1\).
\(n-m=k(x-y)\)
所以\(k|(m,n-m)\)
\(\\\)
假设\((y,x-y)=c(c>1)\).
设\(y=cp,x-y=cq\),则\((p,q)=1,x=c(p+q)\).
此时\(c|(x,y)\),与\("(x,y)=1"\)相矛盾.
所以\((y,x-y)=1\).
所以\((m,n-m)=k\)
2017-02-28 22:41:39