试证明：如果a,b是正整数,那么数列a,2a,3a…ba中能被b整除的项的个数等于a与b的最大公约数

Question

试证明：
如果a,b是正整数,那么数列a,2a,3a…ba中能被b整除的项的个数等于a与b的最大公约数

Answer 1

设a和b的最大公约数是d,则a=a1*d,b=b1*d,且a1和b1是互质的.
a,2a,3a,...,ba即a1*d,2a1*d,...,b1*a1*d*d.(@)
被b整除即包含d因子且包含b1因子
观察(@)行,中除去一个d因子外,为a1,2a1,..,b1*a1*d.
含b1的为b1*a1*1,b1*a1*2 ,...,b1*a1*d,恰为d个.