附件简介
算法设计与分析基础课后习题答案(中文版)
证明等式gcd(m,n)=gcd(n,mmodn)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v,那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=mmodn=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)对于第一个......
查看原帖
