數(shù)論中的一些公式（轉(zhuǎn)）以下等式或者不等式均可以用數(shù)學(xué)歸納法予以證明！1+3+5+...+(2n-1)=n^21*2+2*3+3*4+...+n*(n+1)=n*(n+1)*(n+2)/31*1!+2*2!+3*3!+...+n*n!=(n+1)!-11^2+2^2+3^2+...+n^2=n*(n+1)*(2n+1)/61^2-2^2+3^2-...+(-1)^n*n^2=(-1)^(n+1)*n*(n+1)/22^2+4^2+...+(2n)^2=2n*(n+1)*(2n+1)/31/2!+2/3!+...+n/(n+1)!=1-1/(n+1)!2^(n+1)<1+(n+1)2^n1^3+2^3+3^3+...+n^3=(n*(n+1)/2)^21/(2*4)+1*3/(2*4*6)+1*3*5/(2*4*6*8)+...+(1*3*5*...*(2n-1))/(2*4*6*...*(2n+2))=1/2-(1*3*5*...*(2n+1))/(2*4*6*...*(2n+2))1/(2^2-1)+1/(3^2-1)+..+1/((n+1)^2-1)=3/4-1/(2*(n+1))-1/(2*(n+2))1/2n<=1*3*5*...*(2n-1)/(2*4*6*...*2n)<=1/sqrt(n+1)

n=1,2...2^n>=n^2,n=4,5,...2^n>=2n+1,n=3,4,...r^0+r^1+...+r^n<1/(1-r),n>=0,0<r<11*r^1+2*r^2+...+n*r^n<r/(1-r)^2,n>=1,0<r<11/2^1+2/2^2+3/2^3+...+n/2^n<2,n>=1(a(1)*a(2)*...*a(2^n))^(1/2^n)<=(a(1)+a(2)+...+a(2^n))/2^n,n=1,2,...a(i)是正數(shù)注:()用來標(biāo)記下標(biāo)cos(x)+cos(2x)+...+cos(nx)=cos((x/2)*(n+1))*sin(nx/2)/sin(x/2),其中sin(x/2)!=01*sin(x)+2*sin(2x)+...+n*sin(nx)=sin((n+1)*x)/(4*sin(x/2)^2)-(n+1)cos((2n+1)/2*x)/(2*sin(x/2))

其中sin(x/2)!=05^n-1能被4整除7^n-1能被6整除11^n-6能被5整除6*7^n-2*3^n能被4整除3^n+7^n-2能被8整除n條直線能將平面最多劃分為(n^2+n+2)/2個區(qū)域定義H(k)=1+1/2+1/3+...+1/k

則

1+n/2<=H(2^n)<=1+nH(1)+H(2)+...+H(n)=(n+1)*H(n)-n1*H(1)+2*H(2)+...+n*H(n)=n*(n+1)/2*H(n+1)-n*(n+1)/4歐拉函數(shù)的定義:E(k)=([1,n-1]中與n互質(zhì)的整數(shù)個數(shù)).因為任意正整數(shù)都可以唯一表示成如下形式:

k=p1^a1*p2^a2*……*pi^ai;(即分解質(zhì)因數(shù)形式)

可以推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))

=k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);

=k*(1-1/p1)*(1-1/p2)....(1-1/pk)在程序中利用歐拉函數(shù)如下性質(zhì)，可以快速求出歐拉函數(shù)的值(a為N的質(zhì)因素)

若(N%a==0&&(N/a)%a==0)則有:E(N)=E(N/a)*a;

若(N%a==0&&(N/a)%a!=0)則有:E(N)=E(N/a)*(a-1);若N>2,歐拉函數(shù)E(N)必定是偶數(shù)

若gcd(a,b)=1,則有E(a*b)=E(a)*E(b)

若一個數(shù)N分解成p1^a1*p2^a2*...*pn^an，那么

E(N)=p1^(a1-1)*(p1-1)*...*pn^(an-1)*(pn-1)

若N>1,不大于N且與N互素的所有正整數(shù)的和是1/2*N*E(N)

因子和:

若k=p1^a1*p2^a2...*pi^ai

F(k)=(p1^0+...+p1^a1)*(p2^0+...+p2^a2)*...*(pi^0+...+pi^ai)

沒有一個平方數(shù)是以2,3,7,8結(jié)尾的

max{a,b,c}-min{a,b,c}=(|a-b|+|b-c|+|a-c|)/2

ac%m=bc%m可以得到a%m'=b%m'

m'=m/gcd(m,c)

如果a%mi=b%mi(i=1,2,...,n)并且l=lcm(m1,m2,...,mn)

則可以得到a%l=b%l

Euler定理

若gcd(a,m)==1,則a^(phi(m))%m=1%m

Fermat小定理

p為素數(shù)，對任意的a有a^p%p=a%p

p為素數(shù)

，對任意的a(a<p),a^(p-1)%p=

1%p

p為素數(shù)

，對任意的a，若gcd(p,a)==1,a^(p-1)%p=1%p

一個奇數(shù)a的平方減1都是8的倍數(shù)

任意4個連續(xù)整數(shù)的乘積再加上1一定是完全平方數(shù)

當(dāng)a是整數(shù)時，a(a-1)(2a-1)是6的倍數(shù)

當(dāng)a是奇數(shù)時,

a(a^2-1)是24的倍數(shù)

n次代數(shù)方程x^n+a1*x^(n-1)+...+an-1*x+an=0的系數(shù)都是a1,a2,...,an都是整數(shù)。

如果它有有理數(shù)的根，證明這個根一定是整數(shù)，而且這個數(shù)一定是an的因子。如果不是整數(shù)，就一定是無理數(shù)。

設(shè)a,b都是正整數(shù)，a<b而gcd(a,b)=1,如果存在一個素數(shù)p，它能夠整除b，但是不能夠整除10，則a/b一定不能夠化成有限小數(shù)。如果b=2^a*5^b，其中a,b都是非負(fù)整數(shù)，則a/b能化成有限小數(shù)。

設(shè)0<a<b,且gcd(a,b)=1,如果a/b能表示成純循環(huán)小數(shù)，則我們有g(shù)cd(b,10)=1。

設(shè)0<a<b,且gcd(a,b)=1,令h是一個最小的正整數(shù)，使得10^h與1關(guān)于b同余，那么a/b可以表示成純循環(huán)小數(shù)

0.d1d2d3...dh。

設(shè)b是一個正整數(shù)且gcd(10,b)=1，令h是一個最小的正整數(shù)，能使得10^h與1關(guān)于b同余，則h能夠整除Euler(b)

設(shè)a,b,b1都是正整數(shù)，a<b,gcd(a,b)=1,b1>1,gcd(b1,10)=1。b=2^c*5^d*b1,其中c，d都是非負(fù)整數(shù)，且不同時為0，令h是一個最小的正整數(shù)，使得10^h與1關(guān)于b1同余,則當(dāng)c>=d時，我們有a/b=0.a1a2...aca'(c+1)...a'(c+h)

，而當(dāng)c<d時，我們有a/b=0.a1a2...ada'(d+1)...a'(d+h)

設(shè)0.a1a2...an...不能換成有限小數(shù)，也不能化成循環(huán)小數(shù)，則它不能化成分?jǐn)?shù)。

設(shè)p是一個素數(shù)，m是一個正整數(shù)且m=na+b其中a是一個非負(fù)整數(shù)而b是一個不大于n-1的非負(fù)整數(shù)。令

a=p^m,當(dāng)b=0的時候，a的開n次方是一個整數(shù)，當(dāng)1<=b<=n-1時，a的開n次方不能表示為分?jǐn)?shù)。

設(shè)p是一個素數(shù)，m是一個正整數(shù)且m=na+b其中a是一個非負(fù)整數(shù)而b是一個不大于n-1的非負(fù)整數(shù)。令

a=p^m,當(dāng)b=0的時候，a的開n次方是一個整數(shù)，當(dāng)1<=b<=n-1時，a的開n次方=b+c,其中b是一個正整數(shù)而c是一個無限小數(shù)但不是循環(huán)小數(shù)。

設(shè)a是一個正整數(shù),當(dāng)a的開n次方=b+c中b是一個正整數(shù)而0<c<1時，則a的開n次方不能表示成為分?jǐn)?shù)，并且這時c是一個無限小數(shù)但不是循環(huán)小數(shù)。

(4b^3+3b)/(4b^2+1)<=b+1/(2b+1/2b)<=

根號b平方+1<=b+1/(2b+1/(2b+1/2b))=(8b^4+8b^2+1)/(8b^3+4b)

b+1/(2b

+1/(2b+1/(2b+1/2b)))<=根號b平方+1

(16b^5+20b^3+5b)/(16b^4+12b^2+1)<=根號b平方+1<=(8b^4+8b^2+1)/(8b^3+4b)

8*8棋盤2牌的完美覆蓋數(shù)目為12988816=2^4*901^2

一張m行n列棋盤有一個b-牌的完美覆蓋，當(dāng)且僅當(dāng)b是m的一個因子或者b是n的一個因子

n階幻方的幻和為n*(n^2+1)/2

n階幻方體的幻和為(n^4+n)/2

鴿巢原理：如果n+1個物體被放進(jìn)n個盒子，那么至少有一個盒子包含兩個或者更多的物體鴿巢原理加強(qiáng)形式：令q1，q2，..，qn為正整數(shù)。如果將q1+q2+...+qn-n+1個物體放入n個盒子內(nèi)，那么，至少第一個盒子至少含有q1個物體，或者第二個盒子至少含有q2個物體，...，或者第n個盒子至少含有qn個物體

給定m個整數(shù)a1,a2,...,am，存在整數(shù)p和q，0<=p<q<=m,使得a(p+1)+a(p+2)+...+a(m)能夠被m整除。通俗的說，就是在序列a1,a2,...,am中存在連續(xù)個a，使得這些a的和能被m整除

由n^2+1個實數(shù)構(gòu)成的序列a1，a2,...,a(n^2+1)或者含有長度為n+1的遞增子序列，或者含有長度為n+1的遞減子序列

Ramsey定理：在6個（或更多的）人中，或者有3個人，他們中的每兩個人都互相認(rèn)識；或者有3個人，他們中的每兩個人都彼此不認(rèn)識

n個元素的集合的循環(huán)r-排列的個數(shù)由A(n,r)/r=n!/(r*(n-r)!)給出。特別地，n個元素的循環(huán)排列的個數(shù)是(n-1)!

多重集排列：令S是一個多重集，有k個不同類型的元素，各元素的重數(shù)分別為n1,n2,...,nk。設(shè)S的大小為n=n1+n2+...+nk。則S的排列數(shù)等于n!/(n1!*n2!*...*nk!)

多重集的組合：令S為具有k中類型元素的一個多重集，每種元素均具有無限的重復(fù)數(shù)。則S的r-組合的個數(shù)等于C(r+k-1,r)

如果排列P1P2...Pn有逆序列b1,b2,...,bn，且k=b1+b2+...+bn為逆序數(shù)，那么P1P2...Pn可以通過k次連續(xù)交換得到12...n

利用反射Gray碼生成相鄰元組1的個數(shù)相差1的所有組合

生成{1,2,...,n}的字典序r-組合的算法：從r-組合a1a2...ar=12..r開始當(dāng)a1a2...ar不等于（n-r+1)(n-r+2)...n時,做：i)確定最大的整數(shù)k，是的ak+1<=n且ak+1不等于a1,a2,...arii)用r-組合

a1...a(k-1)(ak+1)(ak+2)...(ak+r-k+1)替換a1a2...ar

C(n,k)=C(n-1,k)+C(n-1,k-1)

1<=k<=n-1

k*C(n,k)=n*C(n-1,k-1)

C(n,0)+C(n,1)+...+C(n,n)=2^n

C(n,0)+C(n,2)+...=2^(n-1)

C(n,1)+C(n,3)+...=2^(n-1)

1*C(n,1)+2*C(n,2)+...+n*C(n,n)=n*2^(n-1)(n>=1)

通過對等式(1+x)^n=sigma(C(n,k)*x^k)

k:0->n兩邊就微分，可以得到sigma(k^p*C(n,k))k:1->n的和

sigma(C(n,k)^2)=C(2n,n)

k:

1->n

C(r,0)+C(r+1,1)+...+C(r+k,k)=C(r+k+1,k)

C(0,k)+C(1,k)+...+C(n-1,k)+C(n,k)=C(n+1,k+1)

Dilworth定理：

令(X,<=)是一個有限偏序集，并令m是反鏈的最大大小。則X可以被劃分成m個但不能再少的鏈同理，若r是鏈的最大大小，那么X可以被劃分成r個但不能再少的反鏈。

卷積定理：對任意兩個長度為n的向量a和b，其中n是2的冪，a,b的卷積等于(DFT2n)-1(DFT2n(a).DFT2n(b))其中向量a和b是用0擴(kuò)充使其長度達(dá)到2n，"."表示2個2n個元素組成的向量的點(diǎn)乘

18014398509481931素數(shù)

18014398509482111最小質(zhì)因子為11

1637672591771101最小質(zhì)因子為6780253

中線定理（pappus定理）是指三角形ABC內(nèi)BM=MC,則AB^2+AC^2=2*(AM^2+BM^2)證明：

AC^2=AH^2+HC^2?

AB^2=AH^2+BH^2=AH^2+(HC+2MH)^2=AH^2+HC^2+4MH*HC+4MH^2

左邊=AB^2+AC^2=2*AH^2+2CH^2+4MH*CH+4MH^2

右邊=2*(AM^2+BM^2)=2*(AH^2+MH^2+(CH+MH)^2)=2*(AH^2+MH^2+CH^2+2CH*MH+MH^2)

得證

[modifiedfrom&豪'sblog]

(1)定理:設(shè)x0,x1,x2,...是無窮實數(shù)列,xj>0,j>=1,那么,

(i)對任意的整數(shù)n>=1,r>=1有

<X0,...,Xn-1,Xn,...,Xn+r>=<X0,...,Xn-1,<Xn,...,Xn+r>>

=

<X0,...,Xn-1,Xn+1/<Xn+1,...,Xn+r>>.