跳到主要内容

素数和模运算

素数​

素数的定义: 除了1和它本身以外不再有其他因数的自然数。亦即,除了1和nn以外,并无其他正整数整除nn的正整数。 1既不是素数,也不是合数。 nn为合数,则有n=abn=ab;n>a>1n>a>1,n>b>1n>b>1。

我们可以视正整数为3类数。1为单独一类数,其二素数,其三合数。

素数(prime number)的表示常用字母pp。

引理2-1​

任何大于1的整数必有素因子。

证明使用反证法。插播一句,带有“必有”字样的定理都可尝试反证法,正难则反。

我们设集合SS包含所有大于1且没有素因子的整数,只需证明SS为空集即可。假设SS不为空集,m∈Sm\in S是SS中最小的整数(m>1m>1且没有素因子)。 情况分为2种:

  1. mm不可能为素数,因为任何素数都有素因子(它本身);
  2. mm若为合数,则有m=abm=ab(合数定义),则1\<a\<m1\<a\<m,1\<b\<m1\<b\<m; 既然a\<ma\<m,必有a∉Sa\notin S。aa必有素因子,设为pp,因为p∣ap|a,且a∣ma|m,也即mm必有素因子pp,与m∈Sm\in S矛盾,得证。

定理2-1​

任何合数都至少有一个不超过n∗1/2n*1/2的素因子。(n>1n>1是合数,则存在素数pp,使得p≤n∗1/2p\le n*1/2)

证明:

设任一合数nn,根据定义有n=abn=ab;

假设a>n∗1/2a>n*1/2,b>n∗1/2b>n*1/2,易证这种情况不存在,因为ab>n∗1/2∗n∗1/2ab>n*1/2 * n*1/2,矛盾于n=abn=ab。同理,亦不可能有a,b\<n∗1/2a,b\<n*1/2。那么先得出结论,a,ba,b其一必定不超过n∗1/2n*1/2。

假设此其一为aa,根据引理2-1得出aa必有素因子pp,p∣ap|a。而a∣na|n,所以p∣np|n,满足p≤n∗1/2p\le n*1/2。

判断nn为素数的方法:如果所有素数p≤n∗1/2p\le n*1/2,都不能整除nn,则nn是素数。

定理2-2(算术基本定理)​

任何非零整数nn可以表示出如下乘积形式:n=±p1e1…prern=\pm p_1^{e_1}\ldots p_r^{e_r}。其中,p1…prp_1\ldots p_r是互不相同的素数,e1…ere_1\ldots e_r是正整数。

  1. 该表示形式是唯一的(不计顺序)
  2. 认为±1\pm 1可以表示成零个素数相乘的结果作为1。

接下来的文章中会证明该定理,此处暂时超纲。

欧几里得定理​

素数有无穷多个。

其实它最好叫做欧几里得素数定理。

证明会使用算术基本定理。

假设素数仅有限个,设其为p1,…,pkp_1,\ldots,p_k;设MM为这kk个数的乘积,表示为M=p1…pkM=p_1\ldots p_k,设N=M+1N=M+1。

显然,N≥2N\ge 2。

那么NN也可以表示为一系列素数乘积的形式,则存在一个素数pp,满足p∣Np|N。

且有p≠p1…pkp\neq p_1\ldots p_k(否则p∣Mp|M,导致p∣(N−M)p|(N-M),有p∣1p|1,不可能)

所以,pp不在p1…pkp_1\ldots p_k之中,这与假设相矛盾。

模运算​

a mod ba \bmod b:设a,b∈Za,b\in\mathbb{Z}且b>0b>0,如果q,r∈Zq,r\in\mathbb{Z}满足a=qb+ra=qb+r,且0≤r\<b0\le r\<b,则定义:a mod b:=ra \bmod b := r。

在C,C++语言中mod表示为%。

对于负整数的模运算,则与正整数正好相反, 设a\<0,b 0a\<0,b\>0。a mod ba \bmod b可理解为aa不断地加上bb直至得数d>0d>0(d\<bd\<b)。 但事实上,还存在这种争议结果:求出的dd只需满足0\<∣d∣\<∣b∣0\<|d|\<|b|,也就是说假设−5 mod 3-5 \bmod 3,得数可以是11,也可以是−2-2。

现如今大多数人认可的是这个模运算定义:

若a,ba,b为整数,c≠0c\neq 0,那么余数dd满足a=kb+ca=kb+c(k∈Zk\in\mathbb{Z})。 且,0≤∣r∣≤∣d∣0\le |r|\le |d|。

在MSVC2021和Python 3.8中,对于-5 mod 3,前者输出了-2,后者输出了1。这表示不同的语言、编译器都会有不同的理解。

(重要)模运算的性质​

  1. b∣ab|a即a mod b=0a \bmod b = 0
  2. (a+b) mod n=(a mod n+b mod n) mod n(a+b) \bmod n = (a \bmod n + b \bmod n) \bmod n
  3. (a−b) mod n=(a mod n−b mod n) mod n(a-b) \bmod n = (a \bmod n - b \bmod n) \bmod n
  4. (a×b) mod n=(a mod n×b mod n) mod n(a\times b) \bmod n = (a \bmod n \times b \bmod n) \bmod n

模运算的性质第一条显而易见,除此之外模运算没有类似的除法性质(本身就包含了一重除法)。

为什么说重要呢?因为运用该性质C++不容易发生算术溢出。预先设置一个模数,对每个因数取模再总体取模,这样不容易发生long long悲剧。