算法设计与分析基础习题参考答案.docx

习题 1.1 5.证明等式 gcd(m,n)=gcd(n,m mod n) 对每一对正整数 m,n 都成立 . Hint: 根据除法的定义不难证明 : 如果 d 整除 u 和 v, 那么 d 一定能整除 u v; 如果 d 整除 u,那么 d 也能够整除 u 的任何整数倍 ku. 对于任意一对正整数 m,n,若 d 能整除 m 和 n,那么 d 一定能整除 n 和 r=m mod n=m-qn