标签归档数学

欧几里德法求最大公约数的证明

Chris Yue No Comments

最近回顾之前写的 RSA 算法相关的文章时,因为 RSA 跟质数有关,突然联想到欧几里德求任意两个自然数最大公约数的方法(又叫辗转相除法):拿 较小数 n 去除 较大数 m,如果 m 正好被整除,则 n 理所当然是最大公约数;而如果不能被整除,则得到一个 余数 r,这个时候则把 r 当成较小数,n 当成较大数,再走一次上面的流程……总之,到最后一定会得到一个 余数 或者说 较小数 r’ 能整除较大数,较小数 r’ 就是一开始 m 和 n 两个数的最大公约数。