网站建设doc,北京网站建设课程培训班,seo发布专员招聘,东莞建设网东莞市住房和城乡建设文章目录 欧几里得算法介绍欧几里得算法的证明证明1#xff1a;b和a%b的最大公约数#xff0c;也是a和b的公约数证明2#xff1a;b和a%b的最大公约数#xff0c;也是a和b的最大公约数 欧几里得算法介绍
小学或初中时学过辗转相除法#xff0c;用于求两个数的最大公约数。… 文章目录 欧几里得算法介绍欧几里得算法的证明证明1b和a%b的最大公约数也是a和b的公约数证明2b和a%b的最大公约数也是a和b的最大公约数 欧几里得算法介绍
小学或初中时学过辗转相除法用于求两个数的最大公约数。
欧几里得算法就是利用辗转相除法求最大公约数。
整数 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的公约数
证明2b和a%b的最大公约数也是a和b的最大公约数
以下分别介绍
证明1b和a%b的最大公约数也是a和b的公约数
设b和a%b的最大公约数为c, 则有 b k 1 ∗ c \begin{align} b k_1 * c \end{align} bk1∗c a % b k 2 ∗ c \begin{align} a \% b k_2 * c \end{align} a%bk2∗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%ba−k∗bk2∗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} ak∗bk2∗ck∗k1∗ck2∗c
所以无论是a的表达式还是b的表达式中都有c这个数所以c也是a和b的公约数。
证毕。
证明2b和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∗k1k2)∗c b k 1 ∗ c \begin{align} b k_1 * c\end{align} bk1∗c
现在需要证明 两个因数 k ∗ k 1 k 2 k*k_1k_2 k∗k1k2 和 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∗k1k2,k1)d,d1 , 那么就有 k ∗ k 1 k 2 m ∗ d \begin{align}k * k_1 k_2 m*d\end{align} k∗k1k2m∗d k 1 n ∗ d \begin{align}k_1 n * d\end{align} k1n∗d 由以上两个式子可以表示出 k 2 k2 k2: k 2 m ∗ d − k ∗ k 1 \begin{align}k_2 m*d - k * k_1\end{align} k2m∗d−k∗k1
带入(1)式和(2)式 b k 1 ∗ c n ∗ d ∗ c \begin{align}b k_1 * c \\ n * d * c\end{align} bk1∗cn∗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%bk2∗c(m∗d−k∗k1)∗c(m∗d−k∗n∗d)∗cd∗c∗(m−k∗n) 因此就找到了 b b b 和 a % b a \% b a%b 的一个公约数 d ∗ c c d * c c d∗cc, 这和c是二者的最大公约数矛盾。
因此反证法的假设不成立 g c d ( k ∗ k 1 k 2 , k 1 ) 1 gcd(k*k_1 k_2, k_1) 1 gcd(k∗k1k2,k1)1, 即 c也是a和b的最大公约数。
证毕。
