离散数学与课件 初等数论 .ppt

初等数论 主要内容 素数 最大公约数与最小公倍数 同余 在计算机科学中的应用 19.1 素数 19.1 素数 2. 素数 定义2：大于 1 且只能被 1 和自身整除的正整数称为素数（质数）。大于 1 又不是素数的正整数称为合数。 19.1 素数 19.1 素数 定理 3：有无穷多个素数。 19.2 最大公约数和最小公倍数 d是a与b的公因子(公约数): d |a且d |b m是a与b的公倍数: a | m且b | m 定义3：设a和b是两个不全为0的整数, 称a与b的公因子中 最大的为a与b的最大公因子, 或最大公约数, 记作gcd(a,b). 设a和b是两个非零整数, 称a与b最小的正公倍数为a与b的 最小公倍数, 记作lcm(a,b). 例3 gcd(12,18)=6, lcm(12,18)=36. 对任意的正整数a, gcd(0,a)=a, gcd(1,a)=1, lcm(1,a)=a. 19.2 最大公约数和最小公倍数 定理4： (1) 若a | m, b | m, 则 lcm(a,b)| m. (2) 若d |a, d |b, 则d | gcd(a,b). 证 (1) 记M=lcm(a,b), 设m=qM+r, 0≤rM. 由a | m, a | M, 及r=m?qM, 可推出a | r. 同理, 有b | r. 即, r是a 和b的公倍数. 根据最小公倍数的定义, 必有r=0. 得证M | m. (2) 记D=gcd(a,b), 令m=lcm(d,D). 若m=D, 自然有d |D, 结 论成立. 否则mD, 注意到d |a, D|a, 由(1), 得m |a. 同理, m |b. 即, m是a和b的公因子, 与D是a和b的最大公约数矛盾. 19.2 最大公约数和最小公倍数 欧几里得算法-辗转相除法 定理5： 设a=qb+r, 其中a, b, q, r 都是整数, 则 gcd(a,b) = gcd(b,r). 证明：只需证a与b和b与r有相同的公因子. 设d是a与b的公因 子, 即d |a且d |b. 注意到, r=a?qb, 由性质可得d |r. 从而, d |b且d |r, 即d也是b与r的公因子. 反之一样, 设d是b与r的公 因子, 即d |b且d |r. 注意到, a=qb+r, 故有d |a. 从而, d |a且d |b, 即d也是a与b的公因子. 欧几里得算法-辗转相除法 欧几里得算法-辗转相除法 19-3 同余 19-3 同余 性质：同余关系是等价关系。 19-3 同余 例7： 3455的个位数是多少? 19-3 同余 扩展的Euclid算法 求乘法逆元： 先用Euclid算法求得gcd(a, n) = 1 从1开始逆推，直到得到1 = ax – kn 则x为a关于模n的乘法逆元 例8：求5关于模14的乘法逆元 辗转相除：14 = 5 ? 2 + 4 5 = 4 + 1 逆推：1 = 5 - 4 = 5 - (14 - 5 ? 2) = 5 ? 3 - 14 因此，5关于模14的乘法逆元为3。 扩展的Euclid算法 例9：求10关于模17的乘法逆元 17 = 10 + 7 10 = 7 + 3 7 = 3 ? 2 + 1 1 = 7 - 3 ? 2 = 7 - (10 – 7) ? 2 = 7 ? 3 - 10 ? 2 = (17 – 10) ? 3 - 10 ? 2 = 17 ? 3 - 10 ? 5 = 17 ? 3 - 17 ? 10 + 17 ? 10 - 10 ? 5 = 10 ? 12 - 17 ? 7 所以10关于模17的乘法逆元为12 19-4 应用 伪随机数产生 随机数：随机变量的观察值 伪随机数 (0,1)上的均匀分布U(0,1): ?a(0a1), P{0X≤a}=a 线性同余法 选择4个非负整数: 模数m, 乘数a, 常数c和种子数x0, 其中2≤am, 0≤cm, 0≤x0m, 用递推公式产生伪随机数序列: xn=(axn?1+c) mod m, n=1,2,… 取 un=xn/m, n=1,2,… 作为U(0,1)伪随机数. 19-4 应用 线性同余法产生的序列的质量取决于m, a和c. 例如 m=8, a=3, c=1, x0=2, 得到7,6,3,2,7,6,…,周期为4