NumberTheory2

huangx607087 学习数论的笔记2

1.素数及其计数(数论概论$12,13$章)

定理1.$2$是唯一的偶素数

定理2.素数有无穷多个，若$a,m$为任意整数，满足$\gcd(a,m)=1$,那么有无穷多个素数$p$满足$p\equiv a \mod m$.

定理3.区间$[x,2x]$内必有一个素数

定理4.设$\pi(x)$为不超过$x$的素数个数，那么$\pi(x)$接近于$\frac{x}{\ln x}$，也就是$\lim_{x \to +\infty} \frac{\pi(x) \ln(x)}{x}=1$

哥德巴赫猜想：每一个大于等于$4$的偶数都可以表示为$2$个素数之和。

孪生素数：$p,p+2$均为素数，那么$(p,p+2)$构成一对孪生素数，猜想有无限多个这样的素数组。

素数猜想3：可能存在无穷多个$n^2+1$类型的素数

2.梅森素数(形如$2^p-1$的素数)(数论概论$14,15$章)

若$a^n-1$是素数，那么$a=2$

性质1：若$n$被$m$整除，那么$2^n-1$被$2^m-1$整除。所以我们有推论：若$2^p-1$是个素数，则$p$一定是个素数。

性质2：如果$2^p-1$是素数，那么$2^{p-1}(2^p-1)$是个完全数（完全数是指除了它的本身之外，这个数的所有因子之和等于它本身，比如$6,28$）

性质3：所有大于$6$的完全数在$6$进制中均以$44$结尾

设$\sigma(x)$为$x$的所有因子之和（包括$1,x$两个数），例如：$\sigma(3)=4,\sigma(15)=24$

性质4:若$\gcd(m,n)=1$,则$\sigma(m)\sigma(n)=\sigma(mn)$。

性质5:若$p$为素数，则$\sigma(p^n)=\sum_{i=0}^{n}p^i$。也就是对于任何素数$p$，均有$\sigma(p)=p+1$。

以下为求$\sigma(a^b)$结果的后8位十进制数的代码，也就是$\sigma(a^b)$对一亿取模的值，其中用到了二分快速加，可以推导一下（等比数列里千万不不要用除法！！！！）

#include <bits/stdc++.h>
using namespace std;
int n,m,T,mod=100000000;
int p[4000],c[4000],num;
void dividing(int x)
{
	int i;
	for(i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			p[++num]=i;
			c[num]=0;
			while(!(x%i)) x/=i,++c[num];
		}
	}
	if(x>1) p[++num]=x,c[num]=1;
}
long long pw(int x,int y)
{
	if(y==0) return 1;
	if(y==1) return x;
	if(x==0) return 0;
	long long S=pw(x,y/2)%mod;
	if(y%2) return S*S*x%mod;
	else return S*S%mod;
} 
long long ad(int q,int k)//求以1为首项，公比为q，最高项次数为k的等比数列 之和 
{
	if(k==0) return 1;
	if(k==1) return q+1;
	long long S=ad(q,(k-1)/2);
	if(k%2) return S+pw(q,(k+1)/2)*S%mod;
	else return S+pw(q,k/2)*S+pw(q,k)%mod;
}
int main()
{
	int i,j;
	scanf("%d",&T);
	while(T--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		dividing(a);
		long long S=1;
		for(i=1;i<=num;i++)
		{
			S*=ad(p[i],c[i]);
			S%=mod;
		}
		printf("%lld\n",S);
	}
	return 0;
}

3.二分快速幂 (数论概论第$16$章)

二分快速幂的C++代码 (Python中直接用pow(x,y,z)函数，很方便)。

long long pw(int x,int y)
{
	if(y==0) return 1;
	if(y==1) return x;
	if(x==0) return 0;
	long long S=pw(x,y/2)%mod;
	if(y%2) return S*S*x%mod;
	else return S*S%mod;
} 

4.解方程$x^e \equiv c \mod n$ (数论概论第$17$章)

前提条件：$\gcd(c,n)=1$且$\gcd(e,\phi(m))=1$。

步骤：
1.计算$\phi(n)$
2.求$e$的逆元$d$
3.计算$x=c^d \mod n$

举个例子：求$x^7 \equiv 5 \mod 39$
1.计算$\phi(39)=24$
2.$e=7$在模$24$的意义下乘法逆元为$d=7$
3.$x=c^d=5^7=78125 \equiv 8 \mod 39$

这是什么？？ RSA解密 RSA解密 RSA解密！！ 密码学的知识成功地跟数论联系起来了（奇怪的知识增加了）23333333