素数和模运算

素数

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

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

素数（prime number）的表示常用字母$p$。

引理2-1

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

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

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

1. $m$不可能为素数，因为任何素数都有素因子（它本身）；
2. $m$若为合数，则有$m=ab$（合数定义），则$1\<a\<m$，$1\<b\<m$； 既然$a\<m$，必有$a\notin S$。$a$必有素因子，设为$p$，因为$p|a$，且$a|m$，也即$m$必有素因子$p$，与$m\in S$矛盾，得证。

定理2-1

任何合数都至少有一个不超过$n*1/2$的素因子。（$n>1$是合数，则存在素数$p$，使得$p\le n*1/2$）

证明：

设任一合数$n$，根据定义有$n=ab$；

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

假设此其一为$a$，根据引理2-1得出$a$必有素因子$p$，$p|a$。而$a|n$，所以$p|n$，满足$p\le n*1/2$。

判断$n$为素数的方法：如果所有素数$p\le n*1/2$，都不能整除$n$，则$n$是素数。

定理2-2（算术基本定理）

任何非零整数$n$可以表示出如下乘积形式：$n=\pm p_1^{e_1}\ldots p_r^{e_r}$。其中，$p_1\ldots p_r$是互不相同的素数，$e_1\ldots e_r$是正整数。

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

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

欧几里得定理

素数有无穷多个。

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

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

假设素数仅有限个，设其为$p_1,\ldots,p_k$；设$M$为这$k$个数的乘积，表示为$M=p_1\ldots p_k$，设$N=M+1$。

显然，$N\ge 2$。

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

且有$p\neq p_1\ldots p_k$（否则$p|M$，导致$p|(N-M)$，有$p|1$，不可能）

所以，$p$不在$p_1\ldots p_k$之中，这与假设相矛盾。

模运算

$a \bmod b$：设$a,b\in\mathbb{Z}$且$b>0$，如果$q,r\in\mathbb{Z}$满足$a=qb+r$，且$0\le r\<b$，则定义：$a \bmod b := r$。

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

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

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

若$a,b$为整数，$c\neq 0$，那么余数$d$满足$a=kb+c$($k\in\mathbb{Z}$)。 且，$0\le |r|\le |d|$。

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

(重要)模运算的性质

1. $b|a$即$a \bmod b = 0$
2. $(a+b) \bmod n = (a \bmod n + b \bmod n) \bmod n$
3. $(a-b) \bmod n = (a \bmod n - b \bmod n) \bmod n$
4. $(a\times b) \bmod n = (a \bmod n \times b \bmod n) \bmod n$

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

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