荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: hbo (H.B.), 信区: Hacker
标 题: 计算机密码学之四(转寄)
发信站: 深大荔园晨风站 (Thu Mar 12 09:55:08 1998), 转信
发信人: chan (为打败拉车仔而战), 信区: Hacker
标 题: 计算机密码学之四
发信站: 华南网木棉站 (Fri Mar 6 12:48:40 1998), 站内信件
个是１，另一个是这个数本身。只能被１和该数自身除尽的数称
为素数。
不是１且非素数的正整数称为合数。ａ除尽ｂ表示为a┃b。
以后不特别说明英文字母a、b、c等都是表示正整数。若a┃b，
且a┃c，就说a是b和c的公因子。若a是b和c的公因子，且
b和c的每一个公因子都除尽a，则称a是b和c的最大公因
子，用gcd{b,c}或(b,c)表示它，即
a=gcd{b,c}, 或a=(b,c)
例如，12=gcd{12,60}。
若a┃c, 则称c是a 的倍数；若a┃c, b┃c, 则称c 是a
和b的公倍数；如果a和b的公倍数c除尽a和b的任一个公倍数，
则称c是a和b的最小公倍数，表示为
c=lcm{a,b}, 或c=[a,b]
例如，60=lcm{15,20,30}。
定理１ 若a=b*q+r, 则
gcd{a,b}=±gcd{b,r}
证明：设d=(a,b),d'=(b,r), 则
d┃(a-b*q), 即d┃r
所以d是b和r的公因数，即d┃d'。类似地，由d'┃(b*q+r)可
得d'┃a, 所以d'┃d。
由d┃d', 可令d'=h*d；同理由d'┃d, 可令d=k*d'。即d'
=h*k*d',因此有
h*k=1
h=k=±1, d=±d'
定理２ 每一双不全为零的整数，必有一个正的最大公因
数。
证明：不失一般性，设a和b是正整数，且a>b。令a=b*q
+r, 0<=r<b。由定理１，可得
(a,b)=(b,r)
----Page 4 Typed by Chan.
--
※ 来源:．深大荔园晨风站 bbs.szu.edu.cn．[FROM: 202.192.140.143]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店