數(shù)論學(xué)習(xí)筆記
編寫目的:在學(xué)習(xí)數(shù)論的同時(shí)練習(xí)markdown與LaTeX
時(shí)間 2021/12/9
第一章、整數(shù)的可除性
==有關(guān)整除的一些定理推論和定理==
整除的概念、歐幾里得除法
==整除的概念==:定義1.1.1：設(shè)a,b是任意兩個(gè)整數(shù)，其中b不為0，如果存在一個(gè)整數(shù)使得等式 a=q*b成立，就稱為b整除a，或者a被b整除，記作 b|a ，并把b叫做a的因數(shù)，把a(bǔ)叫做b的倍數(shù)，人們長將q表示為 a/b ，否則就稱b不能整除a，或a不能整除b記作b
==定理1.1.1==設(shè)a，b，c不等于0，且都為整數(shù)，若 b|a , c|b ,那么c|a。（整除的傳遞性）
==證明==
==定理1.1.2==
==證明==
==定理1.1.3==
==定理1.1.4==
==定理1.1.5==
==素?cái)?shù)的概念==
$$
設(shè)整數(shù)n不等于0，正負(fù)1，如果除了顯然因數(shù)：正負(fù)1,正負(fù)n以外，n沒有其他因數(shù)，那么，n就叫做素?cái)?shù)（或質(zhì)數(shù)或不可約數(shù)），否則稱為合數(shù)。
$$
==定理1.1.6==
==證明==
==Eratoshenes篩法==
$$
當(dāng)我們定義了整除，并依據(jù)整除的定義劃分了素?cái)?shù)與合數(shù)之后，自然而然的想法是，如何判斷一個(gè)數(shù)是否是素?cái)?shù)？這個(gè)時(shí)候希臘數(shù)學(xué)家埃拉托斯特尼提出了一種判斷方法：即Eratoshenes篩法
$$
==定理1.1.7==
==證明==
$$
用反證法, 設(shè)n是合數(shù),取 p是n的大于1的最小正因數(shù), 即p |n. 則由定理6, p 一定是素?cái)?shù), 與定理?xiàng)l件
$$
==定理1.1.8==
==證明==
==歐幾里得除法——最小非負(fù)余數(shù)==**帶余除法**
==證明==
==定義1.1.3==
==定義1.1.4==
==素?cái)?shù)的平凡判別==
==歐幾里得除法 一般余數(shù)==
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b, a%b);
}
==擴(kuò)展歐幾里得==
==描述==
==定理==：對于任意整數(shù)a，b，都存在一組整數(shù)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==
==定理==：
對余數(shù)的叫法根據(jù)性質(zhì)有不同的叫法:
==整數(shù)的表示形式==算術(shù)基本定理（唯一分解定理）
==證明==
==貝祖定理==
==1==:若a,b是整數(shù),且gcd(a,b)=d，那么對于任意的整數(shù)x,y,ax+by都一定是d的倍數(shù)，特別地，**一定存在整數(shù)x,y，使ax+by=d成立。**
==2==:兩個(gè)整數(shù) a、b 是互質(zhì)的，等價(jià)于方程 ax+by=1有整數(shù)解。
==貝祖定理的一種證明==
==貝祖定理擴(kuò)展==
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;
}
第二章、同余
==同余==數(shù)學(xué)上，兩個(gè)整數(shù)除以同一個(gè)整數(shù)，若得相同余數(shù)，則二整數(shù)同余（英文：Modular arithmetic，德文：Kongruenz）。同余理論常被用于數(shù)論中。最先引用同余的概念與符號(hào)者為德國數(shù)學(xué)家高斯。同余理論是初等數(shù)論的重要組成部分，是研究整數(shù)問題的重要工具之一，利用同余來論證某些整除性的問題是很簡單的.
==同余的一些性質(zhì)==
==同余定理==
給定一個(gè)正整數(shù) m，如果兩個(gè)整數(shù) a 和 b 滿足 m|(a-b)，即 a-b 能夠被 m 整除，或者 (a-b)/m 得到一個(gè)整數(shù)，那么就稱整數(shù) a 與 b 對模 m 同余，記作 a≡b(mod m)。對模 m 同余是整數(shù)的一個(gè)等價(jià)關(guān)系。例如：26≡2(mod 12)。
顯然，有如下事實(shí)：
==剩余與剩余類==
==剩余類==
推論
==完系==
==定義==
從每個(gè)中任取一個(gè)數(shù)，取出的m個(gè)數(shù)就是m的完全剩余系（簡稱完系），顯然m的完系有無窮多個(gè)。
推論
常用的完全剩余系
·0,1，.....，m-1稱為模m的==非負(fù)最小完全剩余系==
· m 為奇數(shù)時(shí)，
-(m-1)/2 , -(m+1)/2 , ... , -1 , 0 , 1 , ... , (m-1)/2
· m為偶數(shù)時(shí)，
① -m/2, -m/2+1 , ... , -1 , 0 , 1 , ... , m/2-1
②-m/2+1 , ... , -1 , 0 , 1 , ... , m/2-1 , m/2
稱為模m 的==絕對最小完全剩余系==。
==簡系==
==定義==
如果中任意一個(gè)數(shù)與m互質(zhì)，那么
就是與m互質(zhì)的剩余類。歐拉函數(shù)
φ(n)$個(gè)）稱為模m的一個(gè)簡化剩余系（簡稱簡系）。
推論
==一些定理==
歐拉定理:（也稱費(fèi)馬-歐拉定理或歐拉函數(shù)定理）是一個(gè)關(guān)于同余的性質(zhì)。歐拉定理表明，若n，a為正整數(shù)，且互素（即，則：
即
與1在模n下同余；φ(n)為歐拉函數(shù)。歐拉定理得名于瑞士數(shù)學(xué)家萊昂哈德·歐拉。歐拉定理實(shí)際上是費(fèi)馬小定理的推廣。
歐拉定理是用來闡述素?cái)?shù)模下，指數(shù)同余的性質(zhì)。
歐拉定理：對于正整數(shù)N，代表小于等于N的與N互質(zhì)的數(shù)的個(gè)數(shù)，記作φ(N)
例如φ(8)=4，因?yàn)榕c8互質(zhì)且小于等于8的正整數(shù)有4個(gè)，它們是：1,3,5,7
歐拉定理還有幾個(gè)引理，具體如下：
①：如果n為某一個(gè)素?cái)?shù)p，則φ(p)=p-1;
①很好證明：因?yàn)樗財(cái)?shù)p的質(zhì)因數(shù)只有1和它本身，p和p不為互質(zhì)，所以φ(p)=p-1；
②：如果n為某一個(gè)素?cái)?shù)p的冪次，那么φ(p^a)=(p-1)*p^(a-1)；
②因?yàn)楸萷^a小的數(shù)有p^a-1個(gè)，那么有p^(a-1)-1個(gè)數(shù)能被p所整除（因?yàn)榘?~p^a-1的p的倍數(shù)都篩去了）
所以φ(p)=p^a-1-(p^(a-1)-1)=(p-1)*p^(a-1)
③：如果n為任意兩個(gè)數(shù)a和b的積，那么φ(a*b)=φ(a)*φ(b)
③因?yàn)楸萢*b小的數(shù)有a*b-1個(gè)，條件是a與b互質(zhì)
那么可以知道，只有那些既滿足a與其互質(zhì)且既滿足b與其互質(zhì)的數(shù)滿足條件。
根據(jù)乘法原理，這樣的數(shù)可以互相組合，那么就有φ(a)*φ(b)個(gè)
所以可以得知φ(a*b)=φ(a)*φ(b) (注意條件必須滿足a和b互質(zhì))
④：設(shè)n=(p1^a1)*(p2^a2)*……*(pk^ak) (為N的分解式)
那么φ(n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)
④因?yàn)楦鱾€(gè)分解完的p1、p2、……pk均為素?cái)?shù)，所以它們均為互質(zhì)的
那么φ(n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)
④因?yàn)楦鱾€(gè)分解完的p1、p2、……pk均為素?cái)?shù)，所以它們均為互質(zhì)的
==歐拉篩==
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int prime[100001],mark[1000001];//prime是素?cái)?shù)數(shù)組，mark為標(biāo)記不是素?cái)?shù)的數(shù)組
int tot,phi[100001];//phi為φ(),tot為1~i現(xiàn)求出的素?cái)?shù)個(gè)數(shù)
void getphi(int N){
phi[1]=1;//φ(1)=1
for(int i=2;i<=N;i++){//從2枚舉到N
if(!mark[i]){//如果是素?cái)?shù)
prime[++tot]=i;//那么進(jìn)素?cái)?shù)數(shù)組，指針加1
phi[i]=i-1;//根據(jù)性質(zhì)1所得
}
for(int j=1;j<=tot;j++){//從現(xiàn)求出素?cái)?shù)枚舉
if(i*prime[j]>N) break;//如果超出了所求范圍就沒有意義了
mark[i*prime[j]]=1;//標(biāo)記i*prime[j]不是素?cái)?shù)
if(i%prime[j]==0){//應(yīng)用性質(zhì)2
phi[i*prime[j]]=phi[i]*prime[j];break;
}
else phi[i*prime[j]]=phi[i]*phi[prime[j]];//應(yīng)用性質(zhì)3
}
}
}
int N;
int main(){
cin>>N;
getphi(N);
for(int i=1;i<=N;i++){
cout<<i<<":phi ( "<<phi[i]<<" )"<<endl;//輸出phi(i)
}
}
費(fèi)馬小定理
==若 p 為素?cái)?shù)，則 ，即
（但是 p|a 時(shí)不等價(jià))。==
`數(shù)論中充斥著許多易于觀察到的事實(shí)，誘使人們用普通歸納推理的辦法去進(jìn)行推廣。對此，必須慎之又慎，以免誤入陷阱。設(shè)想你偶而把2自乘7次，再減去2，得27－2＝126，隨后發(fā)現(xiàn)，126恰好能被2的冪指數(shù)7整除。接著又發(fā)現(xiàn)，25－2＝30，30也能被2的冪指數(shù)5整除；211－2＝2048，2048也能被2的冪指數(shù)11整除。從7,5,11都是奇數(shù)產(chǎn)生一個(gè)想法，把2的冪指數(shù)換成偶數(shù)會(huì)怎么樣？于是，又去試驗(yàn)24－2＝14，發(fā)現(xiàn)14不能被2的冪指數(shù)4整除；26－2＝62，62也不能被2的冪指數(shù)6整除；28－2＝254，254也不能被2的冪指數(shù)8整除。
這時(shí)，你或許會(huì)產(chǎn)生一個(gè)感覺：2的冪指數(shù)p為奇數(shù)時(shí)，2p－2似乎能被p整除；2的冪指數(shù)p為偶數(shù)時(shí)，2p－2似乎不能被p整除。為了慎重起見，你可能會(huì)測試一下29－2＝510，并驚訝地發(fā)現(xiàn)，9雖然是奇數(shù)，510卻不能被2的冪指數(shù)9整除；還有，215－2＝32766，15雖然是奇數(shù)，32766也不能被2的冪指數(shù)15整除。于是感到，不能總在奇數(shù)和偶數(shù)上兜圈子，索性擴(kuò)大試驗(yàn)范圍，并對數(shù)據(jù)進(jìn)行系統(tǒng)整理。于是得到：
P 2p－2 (2p－2)÷p
2(質(zhì)數(shù)) 22－2＝4－2＝2 2÷2＝1
3(質(zhì)數(shù)) 23－2＝8－2＝6 6÷3＝2
4(合數(shù)) 24－2＝16－2＝14 14不能被4整除
5(質(zhì)數(shù)) 25－2＝32－2＝30 30÷5＝6
6(合數(shù)) 26－2＝64－2＝62 62不能被6整除
7(質(zhì)數(shù)) 27－2＝128－2＝126 126÷7＝18。
8(合數(shù)) 28－2＝256－2＝254 254不能被8整除
9(合數(shù)) 29－2＝512－2＝510 510不能被9整除
10(合數(shù)) 210－2＝1024－2＝1022 1022不能被10整除
11(質(zhì)數(shù)) 211－2＝2048－2＝2046 2046÷11＝186。
12(合數(shù)) 212－2＝4096－2＝4094 4094不能被12整除
13(質(zhì)數(shù)) 213－2＝8192－2＝8190 8190÷13＝630
14(合數(shù)) 214－2＝16384－2＝16382 16382不能被14整除
15(合數(shù)) 215－2＝32768－2＝32766 32766不能被15整除
16(合數(shù)) 216－2＝65536－2＝65534 65534不能被16整除
17(質(zhì)數(shù)) 217－2＝131072－2＝131070 131070不能被17整除
18(合數(shù)) 217－2＝262144－2＝262142 262142不能被18整除
19(質(zhì)數(shù)) 217－2＝524288－2＝524286 524286÷19＝27594
20(合數(shù)) 217－2＝1048576－2＝1048574 1048574不能被20整除
21(合數(shù)) 217－2＝2097152－2＝2097150 2097150不能被21整除
22(合數(shù)) 217－2＝4194304－2＝4194302 4194302不能被22整除
23(質(zhì)數(shù)) 217－2＝8388608－2＝8388606 8388606÷23＝364722
24(合數(shù)) 217－2＝16777216－2＝16777214 16777214不能被24整除
25(合數(shù)) 217－2＝33554432－2＝33554430 33554430不能被25整除
至此，事情已經(jīng)非常清楚，你很可能會(huì)按耐不住興奮的心情，作出自以為絕對正確無誤的結(jié)論：
當(dāng)p為質(zhì)數(shù)時(shí)，2p－2能被p整除。當(dāng)p為合數(shù)時(shí)，2p－2不能被p整除。其實(shí)，這個(gè)結(jié)果，我國的古代先哲，早在公元前500年就已經(jīng)知道了。只是到了1819年，有人發(fā)現(xiàn)，當(dāng)p＝341時(shí)，2341－2也能被341整除，而341＝31×11，卻是個(gè)合數(shù)，才使上面的“結(jié)論”產(chǎn)生動(dòng)搖。
那么，真實(shí)情況又是怎樣的呢？真實(shí)情況是：p為質(zhì)數(shù)時(shí)，2p－2恒能被p整除；p為合數(shù)時(shí)，2p－2有時(shí)也能被p整除。通過這個(gè)事例，也使我們再一次認(rèn)識(shí)到，僅僅靠歸納得出來的結(jié)論，往往是不可靠的。后來，就是那位提出“$x^n＋y^n＝z^n$，當(dāng)n≥3時(shí)不成立”，而使無數(shù)數(shù)學(xué)大師為之絞盡腦汁苦思冥想了200多年，大名鼎鼎號(hào)稱“業(yè)余數(shù)學(xué)王子”的費(fèi)馬，重新發(fā)現(xiàn)并證明了“p為質(zhì)數(shù)時(shí)，$2^p－2$恒能被p整除”，并且將其推廣到：如果p為質(zhì)數(shù)，$x^p－x$（x是任意正整數(shù)）必能被p整除。在提出公因子x后，$x^p－x＝x(x^{p－1}－1)$，并且設(shè)x不是p的倍數(shù)，這樣，就得到著名的“費(fèi)馬小定理”：若x是一個(gè)不能被質(zhì)數(shù)p整除的整數(shù)，則$x^{p－1}-1$必能被p整除。如果用同余式寫法，就是$x^{p－1}≡1 mod p$。這種樸實(shí)無華的代數(shù)關(guān)系，似乎不會(huì)給人們留下什么深刻印象。然而它導(dǎo)致了眾多的思維與奧妙的數(shù)學(xué)邏輯通道，因而被看成是數(shù)論大廈的一塊基石。
費(fèi)馬小定理有著非常獨(dú)特的作用，從下面這個(gè)例子，就可見一斑。2134217826－1是一個(gè)非常非常大的數(shù)，有四千萬位數(shù)字，需要40卷500頁的大書，每頁2000字，才能容納得下。然而根據(jù)費(fèi)馬小定理，立即可以肯定它能被134217827整除。當(dāng)然，先決條件是：134217827是質(zhì)數(shù)。
費(fèi)馬小定理有多種證法，以同余證法最為簡短而精致。任意取一個(gè)質(zhì)數(shù)，比如13?？紤]從1到12的一系列整數(shù)1,2,3,4,5,6,7,8,9,10,11,12，給這些數(shù)都乘上一個(gè)與13互質(zhì)的數(shù)，比如3，得到3,6,9,12,15,18,21,24,27,30,33,36。對于模13來說，這些數(shù)同余于3,6,9,12,2,5,8,11,1,4,7,10。這些余數(shù)實(shí)際上就是原來的1,2,3,4,5,6,7,8,9,10,11,12，只是順序不同而已。把1,2,3,…,12統(tǒng)統(tǒng)乘起來，乘積就是12的階乘12！。把3,6,9,…,36也統(tǒng)統(tǒng)乘起來，并且提出公因子3，乘積就是312×12！。對于模13來說，這兩個(gè)乘積都同余于1,2,3,…,12系列，盡管順序不是一一對應(yīng)，即312×12！≡12！mod 13。兩邊同時(shí)除以12！得312≡1 mod 13。如果用p代替13，用x代替3，就得到費(fèi)馬小定理$x^{p－1}≡1 mod p$。需要提醒的是，不能把費(fèi)馬小定理理解為只是對質(zhì)數(shù)成立。如果那樣的話，就會(huì)得到一個(gè)判定質(zhì)數(shù)的簡單而實(shí)用準(zhǔn)則：某數(shù)p能整除$x^{p－1}－1$，則p必為質(zhì)數(shù)。尋找簡便易行的判定質(zhì)數(shù)的方法，一直是人們夢寐以求的愿望。不幸的是，費(fèi)馬小定理對質(zhì)數(shù)永遠(yuǎn)成立，對合數(shù)有時(shí)也成立，使得這一美好愿望落了空。不過，盡管如此，費(fèi)馬小定理仍然不失為數(shù)論大廈的一塊基石`---《數(shù)論妙趣——數(shù)學(xué)女王的盛情款待》
中國剩余定理(Chinese remainder theorem, CRT)
下面把問題一般化：假設(shè)整數(shù)
兩兩互素，則對于任意的整數(shù)
，方程組
[圖片上傳失敗...(image-9c0c68-1640615512734)]
都存在整數(shù)解，且若
都滿足該方程組，則必有
，其中
。 具體而言，
。
==中國剩余定理擴(kuò)展==——求解模數(shù)不互質(zhì)情況下的線性方程組：若不互素的情況下求解方程組
對于二階情況:
以此類推
//中國剩余定理模板
typedef long long ll;
ll china(ll a[],ll b[],int n)//a[]為除數(shù)，b[]為余數(shù)
{
ll M=1,y,x=0;
for(int i=0;i<n;++i) //算出它們累乘的結(jié)果
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); //計(jì)算逆元
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();
}
