(之前那个格式太丑，重新发一个)
已知:现在有两个正整数\(a , b\),同时它们都不是彼此的倍数,而且\(a>b\)
求证: \(a和b\)的最大公因数等于\(b\)和 \(a\) \(mod\) \(b\)的最大公因数.
证明: 假设\(a与b的最大公因数为d\)
设 \(a = n * d\) , \(b = m * d\)( \(显然n 一定与 m 互质,这个很重要,而且 n与m一定是正整数\) )
对于 \(a\) \(mod\) \(b\)进行变形:
变形1: \(a\) \(mod\) \(b\) = \((n * d)\) \(mod\) \((m * d)\)
变形2: \((n * d)\) \(mod\) \((m * d)\) = \(d\)*( \(n\) \(mod\) \(m\) )
现在原问题就转化为了求证 gcd(\(n * d\), \(m * d\)) = gcd( \(m * d\) ,\(d\)*( \(n\) \(mod\) \(m\) ) );
显然\(m * d\)和 \(d\)*( \(n\) \(mod\) \(m\) )的公因数 已经含有一个 \(d\) ,倘若要使得它们两个的最大公因数也等于\(d\),那么显然m与n%m要互质
问题进一步转化为:
已知:n 与 m 互质(不考虑n%m等于1的情况,但是此情况实际上也是互质的)
证明: \(m\) 与 \(n\) \(mod\) \(m\)互质
首先:\(n\)一定能表示为\(k * m + c\)的形式(\(k\)是一个自然数,\(c\)也是一个自然数并且\(c<m\))
那么\(n\) \(mod\) \(m\)定然会等于 \(c\)
假如\(c与m有一个不为1的公因数,那么很显然对于c 与 m都能被这个数整除\),那么 \(k*m+c\)也一定能被这个数整除
\(则就会是这种情况:m与n也会有一个不为1的公因数\),这显然与我们事先的声明:"\(m\)与\(n\)互质"矛盾.
所以假设不成立,所以\(m\)与\(n\) \(mod\) \(m\)一定互质.
证毕.
所以 \(a\)和\(b\)的最大公因数等于\(b\)和 \(a\) \(mod\) \(b\)的最大公因数.