（3）素数和最大因子

1.素数

定义：素数是大于1的正整数，且除了1和它本身不会被其他正整数整除。非素数的正整数叫做合数。

定理1：存在无穷多素数

定理2：如果是一个合数，那么一定有一个不超过的素因子

image.png

定义：函数表示不超过正数的素数的个数

等差数列中的素数：假设是互素的正整数，那么等差数列包含了无穷多的素数

梅森素数：形如形式的素数称为梅森素数，几百年间人们发现的最大素数一直是梅森素数

image.png

在后续章节会采用概率素性检验法生成大素数

素数的证明

image.png
image.png

2.素数的分布

素数定理：随着的无限增长，和的比值趋近于1，即(证明及其复杂，略过)

用符号~表示渐进，记作 ~
同时对于是一个更好的近似

image.png

第个素数的值大概是多少呢？由素数定理 ~ ，对两边取对数有
~ ~ ，
因此 ~ ~

推论：令是第个素数，其中是正整数，则 ~

素数的间隔有如下结论：对于任意的正整数，存在至少个连续的合数

素数的猜想

image.png image.png

素数等差数列的厄尔多斯猜想：对任意的正整数，都有一个由素数组成的长度为的等差数列

2006年Ben Green和陶哲轩使用非构造性证明的方式证明了此猜想。

image.png image.png

猜想：存在无穷多个形如的素数，为正整数

勒让德猜想：每两个连续的整数平方之间必然有至少一个素数

3. 最大公因子及其性质

对于整数约定为其最大公因子
定理1：是整数，且，那么
定理1有一个变形：是整数，且，则，其中为互素的整数

定理2：是整数，则有
根据本定理能推导出欧几里得算法的基础：

image.png

定义：是整数，那么它们的线性组合具有形式，其中为整数（可以为负数）

定理3（贝祖定理）：两个不全为0的整数的最大公因子是的线性组合中最小的正整数

image.png

应用到素数上有如下推论：

image.png

定理4：是整数，对所有的线性组合构成的集合与所有的倍数构成的集合相同

image.png

定理5：是整数，其最大公因子有如下性质：

1. 
2. 整数

推论：如果是不全为0的整数，那么

4. 欧几里得算法

最小公倍数和最大公约数的另一种定义

image.png
image.png
由以上定义可得
image.png
欧几里得算法 image.png
image.png
image.png
image.png

上文的伪代码是非递归的，这里把递归与非递归的java代码都贴上（其实区别不大）

递归：
int gcd(int a, int b)
{
    return (b == 0) ? a : gcd(b, a % b);
}

非递归：
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    int r = a % b;
    while (r>0) {
        a = b; 
        b = r;
        r = a % b;
    }
    return b;
}

欧几里得算法的复杂度：

image.png
image.png
image.png

扩展欧几里得算法：

根据贝祖定理，可以表示为的形式，有时我们需要找出确定的值，这时就需要引入以下定理：

image.png
image.png
image.png
image.png

算法实现上，我们要计算：a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)，成立时x,y的值
回到欧几里得算法实现部分，观察

 return (b == 0) ? a : gcd(b, a % b);

当到达递归边界的时候， 这时可以观察出来这个式子的一个解：注意这时的a和b已经不是最开始的那个a和b了，所以我们如果想要求出解x和y，就要回到最开始的模样。

初步想法：由于是递归的算法，如果我们知道了这一层和上一层的关系，一层一层推下去，就可以推到最开始的，类似数学上的数学归纳法。

观察，显然第二个式子是欧几里得算法对第一个式子进行一次运算后的结果。我们可以试着去寻找这两个相邻状态的关系：

首先我们知道：代入第二个式子：

可以发现

这样我们就得到了每两个相邻状态的x和y的转化，就可以在求gcd的同时对x和y进行求值了

代码实现

// java中没有指针，选择用static变量存储x,y的值
public class extragcd {
    static int x,y;
    public static int exgcd(int a,int b){
        if(b==0){
            x=1;y=0;
            return a;
        }
        int temp,gcd;
        gcd=exgcd(b,a%b);
        temp=x;
        x=y;
        y=temp-a/b*y;
        return gcd;
    }


    public static void main(String[] args) {
        int value=exgcd(150,60);
        System.out.println(x+","+y+","+value);
    }
}

对照递归形式的欧几里得算法

int gcd(int a, int b)
{
    return (b == 0) ? a : gcd(b, a % b);
}

其实无非就多了三行

temp=x;
x=y;
y=temp-a/b*y;

相当于在每次递归中，末尾还要递归的计算出x,y的值（初始 x=1;y=0;）
理解了这样的思想后，可以很方便地用来解决一些问题