gcd表示最大公约数
1) 首先证明c*gcd(a,b)是ac、bc的一个公约数
因为c | c,gcd(a,b) | a,所以c*gcd(a,b) | ac
因为c | c,gcd(a,b) | b,所以c*gcd(a,b) | bc
于是c*gcd(a,b)是ac、bc的一个公约数
2) 其次证明c*gcd(a,b)是ac、bc的最大公约数
最大公约数的性质是,两个数的最大公约数可以整除这两个数的其他公约数
于是c*gcd(a,b) | gcd(ac,bc),假设gcd(ac,bc)=k*c*gcd(a,b),k>=1
因为k*c*gcd(a,b) | ac,所以k*gcd(a,b) | a
因为k*c*gcd(a,b) | bc,所以k*gcd(a,b) | b
于是k*gcd(a,b)是a、b的一个公约数,根据最大公约的性质,k*gcd(a,b) | gcd(a,b),于是k=1
从而gcd(ac,bc)=c*gcd(a,b)
