算法设计与分析基础课后习题答案.docx

Program 算法设计与分析基础中文版答案 习题 5. 证明等式 gcd(m,n)=gcd(n,m mod n) 对每一对正整数 m,n都成立 . Hint: 根据除法的定义不难证明 : 如果 d整除 u和 v, 那么 d 一定能整除 uv; 如果 d整除 u, 那么 d 也能够整除 u 的任何整数倍 ku. 对于任意一对正整数 m,n, 若 d 能整除 m和 n, 那么 d 一定能整除 n 和