文档介绍：精品范文模板 可修改删除
免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
撰写人：___________日 期：___________
如果用0表示[0]n，用1表示[1]n。等等，每一类均用其最小的非负元素来表示，则上述两个定义(3)和(4)是等价的。但是，我们必须记住相应的等价类。例如，提到Zn的元素-1就是指[n-1]n，因为-1 = n-1 (mod n)。
公约数与最大公约数
如果d是a的约数并且也是b的约数，则d是a与b的公约数。例如，24与30的公约数为1,2,3和6。注意，1是任意两个整数的公约数。
公约数的一条重要性质为:
(5)
更一般地，对任意整数x和y，我们有
(6)
同样，如果a|b，则或者|a|≤|b|，或者b=O，这说明：
(7)
两个不同时为0的整数a与b的最大公约数表示成gcd(a,b)。例如，gcd(24,30)=6，gcd(5,7)=1，gcd(0,9)=9。如果a与b不同时为0，则 gcd(a,b)是一个在1与min(|a|,|b|)之间的整数。我们定义gcd(O,0)=0，这个定义对于使gcd函数的一般性质(如下面的式 (11))普遍正确是必不可少的。
下列性质就是gcd函数的基本性质：
(8)
(9)
(10)
(11)
(12)
定理 3
如果a和b是不都为0的任意整数，则gcd(a,b)是a与b的线性组合集合{ ax + by : x,y ∈Z}中的最小正元素。
证明：
精品范文模板 可修改删除
免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
设s是a与b的线性组合集中的最小正元素，并且对某个x,y ∈Z，有s = ax + by，设q = ?a/s? ，则式(2)说明
因此，a mod s也是a与b的一种线性组合。但由于a mod s < s，所以我们有a mod s = O，因为s是满足这样的线性组合的最小正数。因此有s|a，并且类似可推得s|b。因此，s是a与b的公约数，所以gcd(a，b)≥ s。因为gcd(a，b)能同时被a与b整除并且s是a与b的一个线性组合，所以由式(6)可知gcd(a,b)| s 。但由gcd(a,b)|s 和s > O，可知 gcd(a,b)≤s。而上面已证明gcd(a,b)≥s，所以得到gcd(a,b) = s，我们因此可得到s是a与b的最大公约数。
推论 4
对任意整数a与b，如果d|a并且d|b，则d|gcd(a,b)。
证明：
根据定理3，gcd(a，b)是a与b的一个线性组合，所以从式(6)可推得该推论成立。
推论 5
对所有整数a 和b以及任意非负整数n，gcd(an ,bn)=n gcd(a,b)。
证明：
如果n = 0，该推论显然成立。如果n ≠ 0，则gcd(an,bn)是集合{anx + bny}中的最小正元素，即为集