数论的性质

ℤ整数 ∃存在 |整除

质数

整数分解定理

证明

N=p*(N/p) 若N不满足条件 则N/p也不满足条件 就不满足N是最小的

这个的证明过程用到了

而这个的证明用到了整数分解定理 所以也就是说我们用了整数分解定理证明了整数分解定理，所以这个证明方法是不对的。
正确的后面再说

素数的判定

Miller-rabin素性测试
性质:

s.t. 使得

证明

做法 选k个素数测试，如果都通过，就极大可能是素数

代码实现

**int gg[8] = {2,3,5,7,13,29,37,89};
bool miller_rabin(int a,int n)
{
	int d=n-1,r=0;
	while (d%2==0)
		d/=2,r++;
	int x = kuaisumi(a,d,n);//快速幂 
	if (x==1) return true;
	for (int i=0;i<r;i++)
	{
		if (x==n-1) return true;
		x=(long long)x*x%n;
	}
	return false;
}
bool is_prime(int n)
{
	if (n<=1) return false;
	for (int a=0;a<8;a++)
		if (n==gg[a]) return true;
	for (int a=0;a<8;a++)
		if (!miller_rabin(gg[a],n)) return false;
	return true;
}**

裴蜀定理

充分条件 正推 必要条件 反推 充分必要（充要）条件 互推 等价
证明

d=gcd(a,b)

知道了裴蜀定理就可以证明上面那个证明方法不正确的定理了，就是这个

证明

扩展欧几里得

根据欧几里得可知 gcd(a,b)=gcd(b,a%b)

代码实现

void ggcd(ll a,ll b,ll &d,ll &x,ll &y)
{
	if(b==0)
	{
		d=a,x=1,y=0;
	}
	else
	{
		ggcd(b,a%b,d,x,y);
		int t=x;
		x=y,y=t-(a/b)*y;
	}
}

中国剩余定理

若p1 p2 到 pn都是互质的

当p不互质的时候

解出b1 b2后 得到了一个新的方程
x≡r(mod lcm(p1,p2)) r=a1+p1*b1
不断两两合并最后解出

介绍一种邪门做法 大数翻倍法
假设 x=a1 不断加上p2 直到x mod p2 = a2，当然加的次数也是有限制的，如果超过了p2次，就可以不用再算了，因为在往后就重复了。这样复杂度就是O(p2),如果p1小于p2，可以交换一下以减小复杂度。