质数:一个大于1的自然数,除了1和它本身之外、不能被其他自然数整除。
如: 2 、3、11、13、17、19等,2 是最小的质数,也是唯一的偶数质数。
合数:就是一个正整数,它除了1与本身整除以外还有其他的约数(0除外)。与之相对的是质数。
如:数字9,除了1和它本身,还能被3整除,所以9是合数。
互质数:公因数只有1的两个非零自然数。互质的两个数不一定都是质数,
如:9和10 都是合数
9的因数有:1、3、9
10的因数有:1、2、5、10
所以,9和10只有一个公因数,因此,9和10是互质数。
谢谢关注。
能够被一和它本身整除的正整数叫做质数。不能被对方整除的两个质数叫做互质数。质数概念是中学数学的重要内容。
质数,在《数论》上习惯称为素数(也叫做,不可约数),是一类特殊的整数。
素数被定义为:
只能被 1 和 自身整除的 正整数,但 1 除外。
(由于整数关于 0 对称,于是只要将正整数部分的研究清楚了,负整数也就清楚了,因此一般不讲负素数。)
数学家发现,任何一个正整数(1 除外),都可以唯一的表示为有限个素数的乘积,每个素数称为该整数的素因子,整个乘积称为该整数的素因子分解。例如:
6 = 2×3
当然,素因子可以重复,例如:
12 = 2 × 2 × 3
因为 如果 1 也是素数,则:
6 = 2×3 = 1×2×3 = 1 × 1 ×2×3 = ...
于是,为了,素因子分解结果唯一,我们不得不让 1 排除在 素数 之外。
素数可以理解为:乘法运算中不可再分解的数,而加法中不可再分解的数只有1。我们可以通过1不断相加得到所有正整数,同样我们可以通过素数相互不断相乘得到所有正整数(1除外)。
从正整数中找到素数是首要的问题!可以直接根据定义,一个个数判断,但这样太慢,数学家一般使用从正整数中排除不是素数的数(称为合数,1除外)的办法,称为筛选法。
如果,正整数 a 》 1 的 素因子分解 为:
a = p₁ × p₂ × ... × pᵣ
则,一定存在一个素因子 p ∈ {p₁, p₂, ... pᵣ } 使得 p ≤ ʳ√a。
这个很显然!如果,每个pᵢ 》 ʳ√a,则 p₁ × p₂ × ... × pᵣ 》( ʳ√a)ʳ = a,矛盾。而我们知道,素数在做素因子分解时,只有一个因子,即它自己,例如:
3 = 3
而合数 最少 两个,例如:
6 = 2×3
于是 合数 a 必然存在 素因子 p ≤ √a。
于是,我们需要找出 N 内的 素数,只需要 找到 √N 内的素数,然后 用这些 素数 去判断 √N 到 N 之间的 正整数 是否是 合数,将是合数的删掉,剩下的就是 素数。这称为 Eratoschenes(埃拉托斯特尼) 筛选法。实例如下:
我们先找到 10 以内的 素数:2,3,5,7;然后 对 10 到 10² = 100 进行筛选:
用 2 筛掉:11, 12, ... , 99, 100;
用 3 筛掉:11, 13, 15, 17, ... , 97, 99;
用 5 筛掉:11, 13, 17, 19, 23, 25, 29, 35, ..., 95, 97;
用 7 筛掉:11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, ..., 91, 97;
于是得到:11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97;有了 100 以内 的素数,然后,对 100 到 100² = 10000 进行筛选 ...
(其实,在具体用 p 进行筛选时,只需要从 p² 开始筛选就可以了,因为 小于 p² 的数,如果具有 p 因子,则 一定具有 小于 p 的素因子,这已经被之前的小于 p 的素因子筛掉了。)
(头条里多位老师也给出了自己的筛选法,大家可以参考借鉴!)
那么,我们使用 筛选法是否可以将 素数 筛完呢?答案是不可能,因为:
素数有无穷多个。
这是一个著名定理,证明如下:
假设,素数有限,记为 p₁, p₂, ..., pᵣ 。现在,令 a = p₁ × p₂ × ... × pᵣ + 1,显然 a 不是任意 一个 素数,且 大于 2, 于是 a 必然是合数,于是存在 素数 pᵢ | a (| 表示 整除)。而 pᵢ 是 p₁, p₂, ..., pᵣ 中的一员,于是 pᵢ | p₁ × p₂ × ... × pᵣ,进而 pᵢ | (a - p₁ × p₂ × ... × pᵣ) ,即 pᵢ | 1,于是 pᵢ = 1,而 pᵢ 是素数 必然 pᵢ 》 1,矛盾。将素数从 小到大排列,记为,
p₁ = 2, p₂ = 3, p₃ = 5, ...
数学家发现:
pᵣ ≤ 2^{2ʳ⁻¹}
因为:
上面那个定理的证明过程,还说明,在 pᵣ 到 a = p₁ × p₂ × ... × pᵣ + 1 之间必然有 一个 素数 pᵣ₊₁,即,如果,将不超过 x 的 素数个数,记为 π(x),则上面的命题等价于:
π(x) 》 log₂(log₂x)
因为:
对于任意 x ≥ 2 ,显然有 唯一正整数 r 使得:素数的定义虽然很简单,但是确意想不到的麻烦!数学家至今依然没有找到素数在正整数中的准确分布规律。
(杨老师《@杨式素数》,在这方面很有研究,大家有兴趣可以去他那里请教。)
(黎曼猜想有助于解决素数分布问题!)
(退而求其次,数学家还发明的 伪素数的概念:
如果 n | 2ⁿ - 2,称 n 为 伪素数,如果 对于任意 整数 a 都有 n | aⁿ - a 称 n 为 绝对伪素数。
关于,伪素数分布 也是一个研究方向。)<