（3）素数和最大因子

2019-07-13 本文已影响0人古剑诛仙

1.素数

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

定理1：存在无穷多素数

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

image.png

定义：函数 $\pi(x)$ 表示不超过正数 $x$ 的素数的个数

等差数列中的素数：假设 $a,b$ 是互素的正整数，那么等差数列 $an+b,n为正整数$ 包含了无穷多的素数

梅森素数：形如 $2^{p}-1$ 形式的素数称为梅森素数，几百年间人们发现的最大素数一直是梅森素数

image.png

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

素数的证明

image.png

2.素数的分布

素数定理：随着 $x$ 的无限增长， $\pi(x)$ 和 $x/log\ x$ 的比值趋近于1，即(证明及其复杂，略过)
${\lim_{x \to +\infty}}\frac{\pi(x)}{x/log\ x}=1$
用符号~表示渐进，记作 $\pi(x)$ ~ $x/log\ x$
同时对于 $\pi(x)，Li(x)=\int_{2}^{x}\frac{dt}{log\ t }$ 是一个更好的近似

image.png

第 $n$ 个素数的值大概是多少呢？由素数定理 $n=\pi(p_{n})$ ~ $\frac{p_{n}}{log\ p_{n}}$ ，对两边取对数有
$log\ n$ ~ $log(\frac{p_{n}}{ln\ p_{n}})=log\ p_{n}-log\ log\ pn$ ~ $log\ p_{n}$ ，
因此 $p_{n}$ ~ $nlog\ p_{n}$ ~ $nlog\ n$

推论：令 $p_{n}$ 是第 $n$ 个素数，其中 $n$ 是正整数，则 $p_{n}$ ~ $nlog\ n$

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

素数的猜想

image.png

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

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

image.png

$n^{2}+1$ 猜想：存在无穷多个形如 $n^{2}+1$ 的素数， $n$ 为正整数

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

3. 最大公因子及其性质

对于整数 $a,b$ 约定 $(a,b)$ 为其最大公因子
定理1： $a,b$ 是整数，且 $(a,b)=d$ ，那么 $(a/d,b/d)=1$
定理1有一个变形： $a,b$ 是整数，且 $b\neq 0$ ，则 $a/b=p/q$ ，其中 $p,q$ 为互素的整数

定理2： $a,b,c$ 是整数，则有 $(a+cb,b)=(a,b)$
根据本定理能推导出欧几里得算法的基础：

image.png

定义： $a,b$ 是整数，那么它们的线性组合具有形式 $ma+nb$ ，其中 $m,n$ 为整数（可以为负数）

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

image.png

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

image.png

定理4： $a,b$ 是整数，对所有 $a,b$ 的线性组合构成的集合与所有 $(a,b)$ 的倍数构成的集合相同

image.png

定理5： $a,b$ 是整数，其最大公因子 $d$ 有如下性质：

$d|a,且d|b$
整数 $c如果满足c|a,c|b，则有c|d$

推论：如果 $a_{1},a_{2},...,a_{n}$ 是不全为0的整数，那么 $(a_{1},a_{2},...,a_{n})=(a_{1},a_{2},...,a_{n-2},(a_{n-1},a_{n}))$

4. 欧几里得算法

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

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

扩展欧几里得算法：

根据贝祖定理， $(a,b)$ 可以表示为 $ma+nb$ 的形式，有时我们需要找出 $m,n$ 确定的值，这时就需要引入以下定理：

image.png

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

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

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

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

观察 $ax_{0}+by_{0}=gcd(a,b);bx_{1}+(a\%b)y_{1}=gcd(a,b)$ ，显然第二个式子是欧几里得算法对第一个式子进行一次运算后的结果。我们可以试着去寻找这两个相邻状态的关系：

首先我们知道： $a\%b=a-(a/b)*b；$ 代入第二个式子：

$b*x_{1} + (a-(a/b)*b)*y_{1}$

$= b*x_{1} + a*y_{1} – (a/b)*b*y_{1}$

$= a*y_{1} + b*(x_{1} – a/b*y_{1}) = gcd$

可以发现 $x_{0} = y_{1} , y_{0} = x_{1} – a/b*y_{1}$

这样我们就得到了每两个相邻状态的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;）
理解了这样的思想后，可以很方便地用来解决一些问题

（3）素数和最大因子

1.素数

2.素数的分布

3. 最大公因子及其性质

4. 欧几里得算法

猜你喜欢

热点阅读