欧几里得算法【Euclid Algorithm】

作者: 摇摆苏丹 | 来源:发表于2021-01-17 14:08 被阅读0次

欧几里得算法【Euclid Algorithm】
扩展欧几里德算法
扩展欧几里得算法
GCD欧几里得算法 & EXGCD扩展欧几里得算法
辗转相除法（又叫欧几里得算法）是什么鬼？
Euclid’s Algorithm （最大公约数）
扩展欧几里得算法
Euclid除法
算法学习(2)----丢番图方程
组合数求解

引言

欧几里得算法用于求两整数的最大公约数，是一个简单却经典的算法，很多算法或者数论领域的入门书都将它作为引子。

描述

已知整数 $a,b$ ，令 $r_{-1}=a, r_0=b$ ，然后由下式
$r_{i-1}=q_{i+1}*r_{i}+r_{i+1}, i \in \mathbb{N+}$
依次计算 $r_{i+1}$ ，直到某余数 $r_{n+1}=0$ ，此时最后的非零余数 $r_{n}$ 就是 $gcd(a,b)$ 。

证明

将欧几里得算法的递归式展开，如下：
$\begin{split} \begin{array}{c} a = q_1 * b + r_1 \\ b = q_2 * r_1 + r_2\\ r_1 = q_3*r_2 + r_3 \\ r_2 = q_4*r_3 + r_4 \\ \vdots\\ r_{n-3} = q_{n-1}*r_{n-2} + r_{n-1}\\ r_{n-2} = q_{n}*r_{n-1} + r_{n}\\ r_{n-1} = q_{n+1} * r_{n} + 0 \end{array} \end{split}$
首先证明 $r_n$ 是 $a,b$ 的公因数。从展开的方程组从下向上分析，最后一行表明 $r_n|r_{n-1}$ 。倒数第二行表明 $r_n|r_{n-2}$ 。依此类推，可得 $r_n|r_2,r_1,b,a$ 。
然后证明 $r_n$ 是 $a,b$ 的最大公因数。设 $m$ 是 $a,b$ 的任意公约数。从展开的方程组从上向下分析，第一行等价于 $r_1=a-q_1*b$ ，由 $m|a,b$ ，得 $m|r_1$ 。第二行等价于 $r_2=b-q_2*r_1$ ，由 $m|r_1,b$ ，得 $m|r_2$ 。依此类推直到倒数第二行，可得 $m|r_n$ 。 $m|r_n \to m \leq r_n$ ，故 $r_n$ 就是 $m$ 的最大值，因此 $m=gcd(a,b)$ ，欧几里得算法得证。
欧几里得算法的收敛性是不证自明的，显然 $r_2,r_2,r_3$ 等余数组成的数列单调递减，该数列的最小值是 $0$ 。

欧几里得算法【Euclid Algorithm】
引言欧几里得算法用于求两整数的最大公约数，是一个简单却经典的算法，很多算法或者数论领域的入门书都将它作为引子。 ...
扩展欧几里德算法
扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）...
扩展欧几里得算法
扩展欧几里得算法（Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展...
GCD欧几里得算法 & EXGCD扩展欧几里得算法
欧几里得算法欧几里得算法 (Euclidean algorithm) 是用来解决最大公约数问题的，通常采用辗转相除...
辗转相除法（又叫欧几里得算法）是什么鬼？
辗转相除法，又名欧几里得算法（Euclidean algorithm），目的是求出两个正整数的最大公约数。这条...
Euclid’s Algorithm （最大公约数）
1.问题描述两个正数 m 和 n 的最大公约数 2. 伪代码实例展示表格中每一行的结果是运行一次while...
扩展欧几里得算法
资料欧几里得算法扩展欧几里得算法扩展欧几里得算法应用欧几里得算法欧几里得算法用于求两个数的最大公约数证...
Euclid除法
例题1: 设a=46480,b=39423,计算(a,b)利用广义欧几里得除法. 方法一:最小非负整数46480=...
算法学习(2)----丢番图方程
之前一篇随笔"算法学习(1)----扩展欧几里得算法"记录了对朴素欧几里得算法和扩展欧几里得算法的学习和认识...
组合数求解
扩展欧几里得算法原理求解逆元的方法（本文采用扩展欧几里得算法进行求解）求组合数的两种方法Lucas定理