Math 版 (精华区)

发信人: flytigger (Ostrich), 信区: Math
标  题: 计算机密码学之四
发信站: 哈工大紫丁香 (Sun Sep 26 16:56:26 1999), 转信

个是１，另一个是这个数本身。只能被１和该数自身除尽的数称
为素数。
    不是１且非素数的正整数称为合数。ａ除尽ｂ表示为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.

--
        ★来棋牌乐揍揍热闹吧……
        ★http://www.nease.net/~chan (一个住的小屋）
        ★只有天马行空的想象，世界才会变得更理想……

※ 修改:．himen 于 Sep 26 17:00:12 修改本文．[FROM: 159.226.41.166]
※ 来源:．华南网木棉站 bbs.gznet.edu.cn．[FROM: 202.38.201.104]
--
※ 转寄:．华南网木棉站 bbs.gznet.edu.cn．[FROM: 159.226.41.166]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: himen.bbs@melon.gzne]