Ex_1_1_25.md

title	date	draft	tags	categories
算法4 Java解答 1.1.25	2019-03-02 19:38:48 +0800	false	JAVA	技术 归档

1.1.25

问题：

Use mathematical induction to prove that Euclid’s algorithm computes the greatest common divisor of any pair of nonnegative integers p and q.

分析：

mathematical induction 数学归纳法

两个非负整数a,b的最大公约数：能够同时整除a，b的自然数中最大的一个。

$$ \begin{align*} r_k = r_{k-2}\bmod r_{k-1} \end{align*} $$

$$ r_{N-1} = ...\\ r_N = 0\\ $$

1. $r_{N-1}\ne0$ 为 a,b的最大公约数。

2. 假设a,b的最大公约数为g。$r_{N-1}\le g$ 。

3. $a=mg, b= ng , g​$可以整除$r_{N-1}​$, 所以 $g\ge r_{N-1}​$。

4. 综上 $r_{N-1} = g​$ 为a和b的最大公约数

5. 详见参考链接

参考：

Euclid’s algorithm

辗转相除法