离散数学课件 8.2素数

素数算数基本定理8.2素数第8章数论

素数定义8.6一个大于1的整数，若它的正约数仅有1和它本身，则称其为素数（Prime）或质数；否则称为合数（Compositenumber）。如7、11是素数，而8、15是合数。1既不是素数，也不是合数。2是唯一的偶素数。定理8.8若a是大于1的正整数，p是素数且p|a，则a=p。定理8.9设a,b是正整数，p是素数且p|ab，则必有p|a或p|b。一般地，设p是素数，且p|(a₁a₂⋯aₖ)，则必存在1≤i≤k，使p|aᵢ。

定理8.10设a是任意大于1的整数，则a除1外的最小正因数q一定是素数，并且，当a是合数时，q≤√a。证明假定q不是素数，由定义8.6，q有除1外的最小正约数q₁，即1<q₁<q，有q₁|q，但q|a，所以q₁|a，这与q是a的正因数矛盾，故q是素数。当a是合数时，则存在q，使得a=a₁q，且a₁>1。由于q是a的不等于1的最小正因数，所以q≤a₁，q²≤qq₁，即q≤√a。推论若a是合数，则a必有一个小于等于√a的素因子。素数

素数例8.7验证157是素数。解：因为√157小于13，而13以内的素因子有2,3,5,7,11，而这些数都不能整除157，所以157是素数。一般地，对任意给定的一个正整数N，我们可求出一切不超过N的素数，称为爱氏筛法：（1）把不超过N的一切整数按从小到大的顺序列成数表。（2）在表中先划去1，然后顺序地划去一切不超过√N的素数的所有倍数，这时，剩下的数即为所求素数。

素数例8.8作60以内的素数表。解：先按从小到大的顺序写出1到60的所有整数。因为√60<8，故只需划去2,3,5,7的所有倍数和1即可，所剩下的数即是60以内的所有素数。所以小于60的所有素数有2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59。

素数定理8.11素数有无穷多个。证明：设p是任一素数，作整数a=p!+1。若a为素数，由于a>p，于是存在大于p的素数a。若a为合数，设q是a的最小真约数，则q是素数，但q不能整除p!，故q>p，可见仍有大于p的素数存在，因而素数有无穷多个。

算数基本原理定理8.12任意大于1的正整数，除因数的顺序外，可唯一地分解为素因数的乘积，即a=p₁p₂⋯pᵣ，pᵢ是素数，i=1,⋯,r如果a=q₁q₂⋯qₛ，qⱼ是素数，j=1,⋯,s则有{p₁,p₂,⋯,pᵣ}={q₁,q₂,⋯,qₛ}。

算数基本原理证明如果a是素数，则令a=p₁，结论成立。如果a是合数，则令p₁是a的最小素因数，于是有a=p₁a₁，1<a₁<a。如果a₁是素数，则令a₁=p₂，结论成立。如果a₁是合数，则令p₂是a₁的最小素因数，于是有a₁=p₂a₂，从而有a=p₁p₂a₂，如此进行下去，由于a>a₁>a₂>⋯，所以，经过有限次后，必有a=p₁p₂⋯pᵣ，pᵢ是素数，i=1,2,…,r。

算数基本原理下面证明其唯一性。当r=1时，如a=q₁q₂⋯qₛ，因p₁是素数，所以有s=1，所以{p₁}={q₁}。假设r-1时成立。因为a=p₁p₂⋯pᵣ=q₁q₂⋯qₛ，所以p₁|q₁q₂⋯qₛ，由定理8.9知，p₁整除a=q₁q₂⋯qₛ中的某一数，不妨设p₁|q₁，从而有p₂⋯pᵣ=q₂⋯qₛ

算数基本原理由归纳假设有{p₂,⋯,pᵣ}={q₂,⋯,qₛ}，又因p₁=q₁，所以有{p₁,p₂,⋯,pᵣ}={q₁,q₂,⋯,qₛ}证毕。

算数基本原理此定理说明素数是构成整数的“基本元素”。如果将a的素因数中相同的素数归在一起，则有其中，p₁,⋯,pᵣ是互异素数。式（7.2）称为a的标准分解式，也称为整数a的素因子分解。

例如：26=2×131320=2²×3×115775=3×5²×7×1199099=3²×7×11²×13利用整数的素因子分解可求最大公约数和最小公倍数。算数基本原理

算数基本原理

定理8.13

设整数a,b的素因子分解式分别为其中，p₁,⋯,pₖ是互不相同的素数，a₁,⋯,aₖ,b₁,⋯,bₖ是非负数。则

算数基本原理

例8.9求132和240的最大公约数与最小公倍数。解因子分解132和240为132=