欧几里得算法
欧几里得算法介绍
小学或初中时学过辗转相除法，用于求两个数的最大公约数。
欧几里得算法就是利用辗转相除法求最大公约数。
整数 a, b 的最大公约数一般表示为 gcd(a, b)。其中a > b。
欧几里得算法： gcd(a, b) = gcd(b, a%b)。
欧几里得算法实质上式将较大规模的问题转化为较小规模的问题 （因为a%b < b < a）。
利用欧几里得算法递归调用，最终问题变得越来越简单，直到gcd(b, a%b) 中的 a%b == 0, 此时最大公约数即为b。
欧几里得算法的证明
证明过程我们分两步：
证明1： b和a%b的最大公约数，也是a和b的公约数
证明2：b和a%b的最大公约数，也是a和b的最大公约数
以下分别介绍：
证明1：b和a%b的最大公约数，也是a和b的公约数
设b和a%b的最大公约数为c, 则有：
b
=
k
1
?
c
\begin{align} b = k_1 * c \end{align}
b=k1??c??
a
%
b
=
k
2
?
c
\begin{align} a \% b = k_2 * c \end{align}
a%b=k2??c??
考虑
a
%
b
a\%b
a%b的含义，实际上可以写成a减去若干个b, 即
a % b = a ? k ? b = k 2 ? c \begin{align} a \% b &= a - k*b \\&= k_2 * c \end{align} a%b?=a?k?b=k2??c??
所以
a
=
k
?
b
+
k
2
?
c
=
k
?
k
1
?
c
+
k
2
?
c
\begin{align} a &= k*b + k_2 * c \\ &= k * k_1 * c + k_2 * c \end{align}
a?=k?b+k2??c=k?k1??c+k2??c??
所以无论是a的表达式还是b的表达式中，都有c这个数，所以c也是a和b的公约数。
证毕。
证明2：b和a%b的最大公约数，也是a和b的最大公约数
由证明1的结论可知，若c为b和a%b的最大公约数, 那么a和b可以分别表示为：
a
=
(
k
?
k
1
+
k
2
)
?
c
\begin{align} a = (k * k_1 + k_2) * c\end{align}
a=(k?k1?+k2?)?c??
b
=
k
1
?
c
\begin{align} b = k_1 * c\end{align}
b=k1??c??
现在需要证明 两个因数 k ? k 1 + k 2 k*k_1+k_2 k?k1?+k2? 和 k 1 k1 k1 的最大公约数为1 (证明2的等价条件).
我们可以用反证法来证明。
假设 g c d ( k ? k 1 + k 2 , k 1 ) = d , d > 1 gcd(k*k_1 + k_2, k_1) = d, d > 1 gcd(k?k1?+k2?,k1?)=d,d>1 , 那么就有
k
?
k
1
+
k
2
=
m
?
d
\begin{align}k * k_1 +k_2= m*d\end{align}
k?k1?+k2?=m?d??
k
1
=
n
?
d
\begin{align}k_1 = n * d\end{align}
k1?=n?d??
由以上两个式子可以表示出
k
2
k2
k2:
k
2
=
m
?
d
?
k
?
k
1
\begin{align}k_2 = m*d - k * k_1\end{align}
k2?=m?d?k?k1???
带入(1)式和(2)式：
b
=
k
1
?
c
=
n
?
d
?
c
\begin{align}b &= k_1 * c \\&= n * d * c\end{align}
b?=k1??c=n?d?c??
a
%
b
=
k
2
?
c
=
(
m
?
d
?
k
?
k
1
)
?
c
=
(
m
?
d
?
k
?
n
?
d
)
?
c
=
d
?
c
?
(
m
?
k
?
n
)
\begin{align}a \% b &= k_2 * c \\&= (m * d - k * k_1) * c \\&= (m * d - k * n * d) * c \\&= d * c * (m - k * n)\end{align}
a%b?=k2??c=(m?d?k?k1?)?c=(m?d?k?n?d)?c=d?c?(m?k?n)??
因此就找到了
b
b
b 和
a
%
b
a \% b
a%b 的一个公约数
d
?
c
>
c
d * c > c
d?c>c, 这和c是二者的最大公约数矛盾。
因此反证法的假设不成立， g c d ( k ? k 1 + k 2 , k 1 ) = 1 gcd(k*k_1 + k_2, k_1) = 1 gcd(k?k1?+k2?,k1?)=1, 即 c也是a和b的最大公约数。
证毕。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！