数论基础

数学

//本篇为学习记录，会一直更新

常见符号：

整除符号：(x) (|) (y)， (x)整除(y)
取模符号：(x) (mod) (y)， (x)除以(y) 的余数
互质符号： (x) (ot) (y)， (x)除以(y) 的余数
最大公约数：(gcd(x,y))，简写为((x,y))
最小公倍数：(lcm(x,y))，简写为(left[x,y ight])
求和符号：(sum)
求积符号：(prod)

数论基础：

1）素数判定：

如果存在一个整数(k)，使得(a=kd)，则称(d)整除(a)，记作(d) (|) (a)，即(a)是(d)的倍数，(k)叫做他们的约数

那么如果除了(1)和它本身外，不存在任意的(k)，使得(d) (|) (a)，那么就叫这个(a)为素数（质数）

(1)既不是质数也不是合数

素数的判定方法：

1. (O(n))

bool is_prime(int n)
{
    int flag=0;
    for(int i=2;i<n;i++)
    {
        if(n%i==0) 
        {
            flag=1;
            break;
        }
    }
    if(flag) return 0;
    else return 1;
}

2.(O(sqrt(n)))

因为质数的分布是以(sqrt(n))为界限对称分布的，所以只去遍历((2-sqrt(n)))就可以得到所有的约数

bool is_prime(int n)
{
    int flag=0;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0) 
        {
            flag=1;
            break;
        }
    }
    if(flag) return 0;
    else return 1;
}

2) 素数筛

假设(n=1000000)，如果我们想要知道(1-n)之间有多少个素数，分别是多少，很明显，直接对每一个数去判断他是否是质数的时间复杂度是(o(n*sqrt(n)))

对于(1000000)的数据规模预处理也是有可能 tle 的，所以我们并不考虑这样的预处理方式

对于(iin[1,n])的每一个数(i)，如果(i)是一个合数的话，只让他被最小的质因子筛一次，时间复杂度(O(n))

每次我们遍历([2,n]) 的每一个数，如果遍历到了(i) 那就证明他已经被比他小的数筛过了，如果没有被标记，那就证明他是一个质数，然后我们遍历已经被筛过的质数，把他的倍数全都标记上，如果(i\%prime[j]==0)，那(i=prime[j]*x) ,下一次循环的(i*prime[j+1]=prime[j]*x*prime[j+1]) ，但(prime[j])一定比(prime[j+1])小，所以就不用再筛下去了，(i*prime[j+1])一定被筛过了

int vis[maxn],prime[maxn],cnt=0;
void init(int n)
{
    vis[0]=1;
    vis[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
// 质数的vis=0，prime下标从0开始

3) 同余式

如果两个数(a,b)在模(n)意义下的答案相等，那么我们就说(a)和(b)对模(n)同余，记作(a equiv b)

4) Wilson定理（威尔逊定理）

当且仅当(p)为素数时 ((p-1)!equiv-1(mod p))

5) Fermat小定理（费马小定理）

如果(p)是一个素数，且((0<a<p)) 那么存在(a^{p-1}equiv1(mod p))

证明：

(1*a\%p=a_{1})

(2*a\%p=a_{2})

(dots)

((p-1)*a\%p=a_{p-1})

进行累乘

((p-1)!*a^{p-1}\%p=(p-1)!)

同除((p-1)!) 得(a^{p-1}equiv1(mod p))

[关于为什么(a_1*a_2* dots *a_{p-1}=(p-1)!)的解释] ：

对于$iin [1,p-1] $ 有(a*i\%pequiv b)

((a*i\%p-b+p)\%pequiv 0)

((a*i-b) | p)

如果想找到另一个(i')使得(a*i'\%pequiv b) 那么只有(i'=i+p)，但(i+p>p-1) 所以不存在这样的(i')

所以对于$iin [1,p-1] $ 集合(left {a_1,a_2, dots,a_{p-1} ight })等同于集合(left {1,2,dots,p-1 ight })

则(a_1*a_2* dots *a_{p-1}=(p-1)!)

5) Euler定理（欧拉定理）

欧拉定理也是费马小定理的一个推广

我们定义(varphi (n))是(iin [1,n])中有多少(i)使(gcd(n,i)=1)

如果(gcd(a,p)=1) 那么(a^{varphi(p)} equiv 1(mod p))

(当(p)是素数时，很明显(varphi(p)=p-1)，就可以得到费马小定理了)

定理的证明和Fermat小定理几乎相同，只是要考虑的式子变成了所有与m互素的数的乘积

5) Fermat素数测试

Fermat素数测试属于一种随机算法

对于费马小定理来说，人们发现他的逆命题并不成立，比如(2^{560}\%561equiv1)但(561)并不是个素数，(561=11*51)

人们把这样的数(n)叫做伪素数，即(2^{(n-1)}-1 | n)

对他进行推广，把(2)替换为任意的素数(a)，满足(a^{(n-1)}\%n=1)的合数(n)叫做以 (a) 为底的伪素数。

不满足(a^{(n-1)}\%n=1) 的(n)一定不是素数，我们一般是随机选取有限个数的底数 a ，对 n 进行素性测试。若全部满足，则认为数字 n 是质数，若有一个不满足，则认为数字 n 不是质数

这样的判断在一定程度上已经足够准确了

但，对于所有小于 (n) 的底数 (a)，都满足(a^{(n-1)}\%n=1) 的数。（前(10)亿个数中，仅有(600)多个这样的数存在）这样的数叫做Carmichael数

利用二次探测定理可以对上面的素数判定算法作进一步改进,以避免将Carmichael数当作素数，而用这种方式优化过的素数测试算法叫做Miller_Rabin素数测试算法