数论学习笔记
编写目的:在学习数论的同时练习markdown与LaTeX
时间 2021/12/9
第一章、整数的可除性
==有关整除的一些定理推论和定理==
整除的概念、欧几里得除法
==整除的概念==:定义1.1.1：设a,b是任意两个整数，其中b不为0，如果存在一个整数使得等式 a=q*b成立，就称为b整除a，或者a被b整除，记作 b|a ，并把b叫做a的因数，把a叫做b的倍数，人们长将q表示为 a/b ，否则就称b不能整除a，或a不能整除b记作b
==定理1.1.1==设a，b，c不等于0，且都为整数，若 b|a , c|b ,那么c|a。（整除的传递性）
==证明==
==定理1.1.2==
==证明==
==定理1.1.3==
==定理1.1.4==
==定理1.1.5==
==素数的概念==
$$
设整数n不等于0，正负1，如果除了显然因数：正负1,正负n以外，n没有其他因数，那么，n就叫做素数（或质数或不可约数），否则称为合数。
$$
==定理1.1.6==
==证明==
==Eratoshenes筛法==
$$
当我们定义了整除，并依据整除的定义划分了素数与合数之后，自然而然的想法是，如何判断一个数是否是素数？这个时候希腊数学家埃拉托斯特尼提出了一种判断方法：即Eratoshenes筛法
$$
==定理1.1.7==
==证明==
$$
用反证法, 设n是合数,取 p是n的大于1的最小正因数, 即p |n. 则由定理6, p 一定是素数, 与定理条件
$$
==定理1.1.8==
==证明==
==欧几里得除法——最小非负余数==**带余除法**
==证明==
==定义1.1.3==
==定义1.1.4==
==素数的平凡判别==
==欧几里得除法 一般余数==
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b, a%b);
}
==扩展欧几里得==
==描述==
==定理==：对于任意整数a，b，都存在一组整数x、y使得成立
推论:
#define ll long long
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(!b){x=1;y=0;return a;}
ll t, d;
d=exgcd(b,a%b,x,y);
t=x;x=y;y=t-a/b*y;
return d;
}
==求解方程ax+by=c==
==定理==：
对余数的叫法根据性质有不同的叫法:
==整数的表示形式==算术基本定理（唯一分解定理）
==证明==
==贝祖定理==
==1==:若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，**一定存在整数x,y，使ax+by=d成立。**
==2==:两个整数 a、b 是互质的，等价于方程 ax+by=1有整数解。
==贝祖定理的一种证明==
==贝祖定理扩展==
bool Bezout(int a, int b, int *px, int *py)
{
int q, r;
int x, y;
bool ok;
if( a == 1 )
{
*px = 1;
*py = 0;
return true;
}
if( b == 1 )
{
*px = 0;
*py = 1;
return true;
}
if( a >= b )
{
q = a / b;
r = a % b;
if ( r == 0 )
{
return false;
}
ok = Bezout(r, b, &x, &y);
if( ok )
{
*px = x;
*py = y - q * x;
}
return ok;
}
else
{
q = b / a;
r = b % a;
if ( r == 0 )
return false;
}
ok = Bezout(a, r, &x, &y);
if( ok )
{
*py = y;
*px = x - q * y;
}
return ok;
}
return true;
}
//test_demo.cpp
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool Bezout(int a, int b, int *px, int *py);
int main()
{
int x, y;
int a = 73;
int b = 32;
bool ok;
ok = Bezout(a, b, &x, &y);
if(ok)
{
printf("%d * %d + %d * %d = %d, is ok\n", a, x, b, y, a * x + b * y);
}
return 0;
}
第二章、同余
==同余==数学上，两个整数除以同一个整数，若得相同余数，则二整数同余（英文：Modular arithmetic，德文：Kongruenz）。同余理论常被用于数论中。最先引用同余的概念与符号者为德国数学家高斯。同余理论是初等数论的重要组成部分，是研究整数问题的重要工具之一，利用同余来论证某些整除性的问题是很简单的.
==同余的一些性质==
==同余定理==
给定一个正整数 m，如果两个整数 a 和 b 满足 m|(a-b)，即 a-b 能够被 m 整除，或者 (a-b)/m 得到一个整数，那么就称整数 a 与 b 对模 m 同余，记作 a≡b(mod m)。对模 m 同余是整数的一个等价关系。例如：26≡2(mod 12)。
显然，有如下事实：
==剩余与剩余类==
==剩余类==
推论
==完系==
==定义==
从每个中任取一个数，取出的m个数就是m的完全剩余系（简称完系），显然m的完系有无穷多个。
推论
常用的完全剩余系
·0,1，.....，m-1称为模m的==非负最小完全剩余系==
· m 为奇数时，
-(m-1)/2 , -(m+1)/2 , ... , -1 , 0 , 1 , ... , (m-1)/2
· m为偶数时，
① -m/2, -m/2+1 , ... , -1 , 0 , 1 , ... , m/2-1
②-m/2+1 , ... , -1 , 0 , 1 , ... , m/2-1 , m/2
称为模m 的==绝对最小完全剩余系==。
==简系==
==定义==
如果中任意一个数与m互质，那么
就是与m互质的剩余类。欧拉函数
φ(n)$个）称为模m的一个简化剩余系（简称简系）。
推论
==一些定理==
欧拉定理:（也称费马-欧拉定理或欧拉函数定理）是一个关于同余的性质。欧拉定理表明，若n，a为正整数，且互素（即，则：
即
与1在模n下同余；φ(n)为欧拉函数。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。欧拉定理实际上是费马小定理的推广。
欧拉定理是用来阐述素数模下，指数同余的性质。
欧拉定理：对于正整数N，代表小于等于N的与N互质的数的个数，记作φ(N)
例如φ(8)=4，因为与8互质且小于等于8的正整数有4个，它们是：1,3,5,7
欧拉定理还有几个引理，具体如下：
①：如果n为某一个素数p，则φ(p)=p-1;
①很好证明：因为素数p的质因数只有1和它本身，p和p不为互质，所以φ(p)=p-1；
②：如果n为某一个素数p的幂次，那么φ(p^a)=(p-1)*p^(a-1)；
②因为比p^a小的数有p^a-1个，那么有p^(a-1)-1个数能被p所整除（因为把1~p^a-1的p的倍数都筛去了）
所以φ(p)=p^a-1-(p^(a-1)-1)=(p-1)*p^(a-1)
③：如果n为任意两个数a和b的积，那么φ(a*b)=φ(a)*φ(b)
③因为比a*b小的数有a*b-1个，条件是a与b互质
那么可以知道，只有那些既满足a与其互质且既满足b与其互质的数满足条件。
根据乘法原理，这样的数可以互相组合，那么就有φ(a)*φ(b)个
所以可以得知φ(a*b)=φ(a)*φ(b) (注意条件必须满足a和b互质)
④：设n=(p1^a1)*(p2^a2)*……*(pk^ak) (为N的分解式)
那么φ(n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)
④因为各个分解完的p1、p2、……pk均为素数，所以它们均为互质的
那么φ(n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)
④因为各个分解完的p1、p2、……pk均为素数，所以它们均为互质的
==欧拉筛==
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int prime[100001],mark[1000001];//prime是素数数组，mark为标记不是素数的数组
int tot,phi[100001];//phi为φ(),tot为1~i现求出的素数个数
void getphi(int N){
phi[1]=1;//φ(1)=1
for(int i=2;i<=N;i++){//从2枚举到N
if(!mark[i]){//如果是素数
prime[++tot]=i;//那么进素数数组，指针加1
phi[i]=i-1;//根据性质1所得
}
for(int j=1;j<=tot;j++){//从现求出素数枚举
if(i*prime[j]>N) break;//如果超出了所求范围就没有意义了
mark[i*prime[j]]=1;//标记i*prime[j]不是素数
if(i%prime[j]==0){//应用性质2
phi[i*prime[j]]=phi[i]*prime[j];break;
}
else phi[i*prime[j]]=phi[i]*phi[prime[j]];//应用性质3
}
}
}
int N;
int main(){
cin>>N;
getphi(N);
for(int i=1;i<=N;i++){
cout<<i<<":phi ( "<<phi[i]<<" )"<<endl;//输出phi(i)
}
}
费马小定理
==若 p 为素数，则 ，即
（但是 p|a 时不等价)。==
`数论中充斥着许多易于观察到的事实，诱使人们用普通归纳推理的办法去进行推广。对此，必须慎之又慎，以免误入陷阱。设想你偶而把2自乘7次，再减去2，得27－2＝126，随后发现，126恰好能被2的幂指数7整除。接着又发现，25－2＝30，30也能被2的幂指数5整除；211－2＝2048，2048也能被2的幂指数11整除。从7,5,11都是奇数产生一个想法，把2的幂指数换成偶数会怎么样？于是，又去试验24－2＝14，发现14不能被2的幂指数4整除；26－2＝62，62也不能被2的幂指数6整除；28－2＝254，254也不能被2的幂指数8整除。
这时，你或许会产生一个感觉：2的幂指数p为奇数时，2p－2似乎能被p整除；2的幂指数p为偶数时，2p－2似乎不能被p整除。为了慎重起见，你可能会测试一下29－2＝510，并惊讶地发现，9虽然是奇数，510却不能被2的幂指数9整除；还有，215－2＝32766，15虽然是奇数，32766也不能被2的幂指数15整除。于是感到，不能总在奇数和偶数上兜圈子，索性扩大试验范围，并对数据进行系统整理。于是得到：
P 2p－2 (2p－2)÷p
2(质数) 22－2＝4－2＝2 2÷2＝1
3(质数) 23－2＝8－2＝6 6÷3＝2
4(合数) 24－2＝16－2＝14 14不能被4整除
5(质数) 25－2＝32－2＝30 30÷5＝6
6(合数) 26－2＝64－2＝62 62不能被6整除
7(质数) 27－2＝128－2＝126 126÷7＝18。
8(合数) 28－2＝256－2＝254 254不能被8整除
9(合数) 29－2＝512－2＝510 510不能被9整除
10(合数) 210－2＝1024－2＝1022 1022不能被10整除
11(质数) 211－2＝2048－2＝2046 2046÷11＝186。
12(合数) 212－2＝4096－2＝4094 4094不能被12整除
13(质数) 213－2＝8192－2＝8190 8190÷13＝630
14(合数) 214－2＝16384－2＝16382 16382不能被14整除
15(合数) 215－2＝32768－2＝32766 32766不能被15整除
16(合数) 216－2＝65536－2＝65534 65534不能被16整除
17(质数) 217－2＝131072－2＝131070 131070不能被17整除
18(合数) 217－2＝262144－2＝262142 262142不能被18整除
19(质数) 217－2＝524288－2＝524286 524286÷19＝27594
20(合数) 217－2＝1048576－2＝1048574 1048574不能被20整除
21(合数) 217－2＝2097152－2＝2097150 2097150不能被21整除
22(合数) 217－2＝4194304－2＝4194302 4194302不能被22整除
23(质数) 217－2＝8388608－2＝8388606 8388606÷23＝364722
24(合数) 217－2＝16777216－2＝16777214 16777214不能被24整除
25(合数) 217－2＝33554432－2＝33554430 33554430不能被25整除
至此，事情已经非常清楚，你很可能会按耐不住兴奋的心情，作出自以为绝对正确无误的结论：
当p为质数时，2p－2能被p整除。当p为合数时，2p－2不能被p整除。其实，这个结果，我国的古代先哲，早在公元前500年就已经知道了。只是到了1819年，有人发现，当p＝341时，2341－2也能被341整除，而341＝31×11，却是个合数，才使上面的“结论”产生动摇。
那么，真实情况又是怎样的呢？真实情况是：p为质数时，2p－2恒能被p整除；p为合数时，2p－2有时也能被p整除。通过这个事例，也使我们再一次认识到，仅仅靠归纳得出来的结论，往往是不可靠的。后来，就是那位提出“$x^n＋y^n＝z^n$，当n≥3时不成立”，而使无数数学大师为之绞尽脑汁苦思冥想了200多年，大名鼎鼎号称“业余数学王子”的费马，重新发现并证明了“p为质数时，$2^p－2$恒能被p整除”，并且将其推广到：如果p为质数，$x^p－x$（x是任意正整数）必能被p整除。在提出公因子x后，$x^p－x＝x(x^{p－1}－1)$，并且设x不是p的倍数，这样，就得到著名的“费马小定理”：若x是一个不能被质数p整除的整数，则$x^{p－1}-1$必能被p整除。如果用同余式写法，就是$x^{p－1}≡1 mod p$。这种朴实无华的代数关系，似乎不会给人们留下什么深刻印象。然而它导致了众多的思维与奥妙的数学逻辑通道，因而被看成是数论大厦的一块基石。
费马小定理有着非常独特的作用，从下面这个例子，就可见一斑。2134217826－1是一个非常非常大的数，有四千万位数字，需要40卷500页的大书，每页2000字，才能容纳得下。然而根据费马小定理，立即可以肯定它能被134217827整除。当然，先决条件是：134217827是质数。
费马小定理有多种证法，以同余证法最为简短而精致。任意取一个质数，比如13。考虑从1到12的一系列整数1,2,3,4,5,6,7,8,9,10,11,12，给这些数都乘上一个与13互质的数，比如3，得到3,6,9,12,15,18,21,24,27,30,33,36。对于模13来说，这些数同余于3,6,9,12,2,5,8,11,1,4,7,10。这些余数实际上就是原来的1,2,3,4,5,6,7,8,9,10,11,12，只是顺序不同而已。把1,2,3,…,12统统乘起来，乘积就是12的阶乘12！。把3,6,9,…,36也统统乘起来，并且提出公因子3，乘积就是312×12！。对于模13来说，这两个乘积都同余于1,2,3,…,12系列，尽管顺序不是一一对应，即312×12！≡12！mod 13。两边同时除以12！得312≡1 mod 13。如果用p代替13，用x代替3，就得到费马小定理$x^{p－1}≡1 mod p$。需要提醒的是，不能把费马小定理理解为只是对质数成立。如果那样的话，就会得到一个判定质数的简单而实用准则：某数p能整除$x^{p－1}－1$，则p必为质数。寻找简便易行的判定质数的方法，一直是人们梦寐以求的愿望。不幸的是，费马小定理对质数永远成立，对合数有时也成立，使得这一美好愿望落了空。不过，尽管如此，费马小定理仍然不失为数论大厦的一块基石`---《数论妙趣——数学女王的盛情款待》
中国剩余定理(Chinese remainder theorem, CRT)
下面把问题一般化：假设整数
两两互素，则对于任意的整数
，方程组
[图片上传失败...(image-9c0c68-1640615512734)]
都存在整数解，且若
都满足该方程组，则必有
，其中
。 具体而言，
。
==中国剩余定理扩展==——求解模数不互质情况下的线性方程组：若不互素的情况下求解方程组
对于二阶情况:
以此类推
//中国剩余定理模板
typedef long long ll;
ll china(ll a[],ll b[],int n)//a[]为除数，b[]为余数
{
ll M=1,y,x=0;
for(int i=0;i<n;++i) //算出它们累乘的结果
M*=a[i];
for(int i=0;i<n;++i)
{
ll w=M/a[i];
ll tx=0;
int t=exgcd(w,a[i],tx,y); //计算逆元
x=(x+w*(b[i]/t)*x)%M;
}
return (x+M)%M;
}
#include<iostream>
#include<string>
#include<cstdio>
typedef long long ll;
using namespace std;
const int maxn=100000+5;
int n;
ll ai[maxn],bi[maxn];
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0){ x=1, y=0; return a;}
ll gcd=exgcd(b,a%b,x,y);
ll tp=x;
x=y, y=tp-a/b*y;
return gcd;
}
ll mult(ll a,ll b,ll mod){
long long res=0;
while(b>0){
if(b&1) res=(res+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return res;
}
ll excrt(){
ll x,y;
ll ans=bi[1],M=ai[1];
for(int i=2;i<=n;++i){
ll a=M,b=ai[i],c=(bi[i]-ans%ai[i]+ai[i])%ai[i];
ll gcd=exgcd(a,b,x,y);
x=mult(x,c/gcd,b/gcd);
ans+=x*M;
M*=b/gcd;
ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i)
cin>>ai[i]>>bi[i];
cout<<excrt();
}
