贝祖定理

合并图册(2)

定义整数a,b的一个线性组合是指形如的整数，其中x,y是整数。那么贝祖定理是说对整数a,b（如果我们定义时，），是a,b的一个线性组合（其中是a,b的最大公因数，简记为）。

若，则.结论显然.

不妨设.考虑由所有的线性组合组成的集合

分别取和：.由于正实数集对所有实数有三分法成立，故中必定有一个为正（已令）.设，则.

由最小数原理知，中有最小正整数，不妨设为.

因为，所以是的一个线性组合：,

由带余除法可知：使得其中.假设，则：

这与是的最小元矛盾.故，即是的因子.类似地，可证是的因子.故是和的公因子.

若是和的任意一个公因子，则设.因为，所以整除，所以.故.

1. 若a |bc，且（a，b）=1，则a |c证明：∵(a，b)=1，由贝祖定理，存在x，y∈Z，使得 ax+by=1∴ (ax+by)c = c∴acx+bcy = c∵ a | ac，a | bc∴ a | acx+bcy∴a | c命题得证

2.若a |c，b |c，且（a，b）=1，则ab |c

3.设m为正整数，则（ma，mb）=m（a，b），[ma，mb]=m[a，b]

4.设a，b都为正整数，则（a，b）·[a，b]=ab^[1]