數論和組合分析

設a1，a2，…，an是n(n≥2)個整數.若整數d是它們之中每一個的因數，那么d就叫做a1，a2，…，an的一個公因數.整數a1，a2，…，an的公因數中最大的一個叫做最大公因數，記作（a1，a2，…，an），若（a1，a2，…，an）＝1，我們說a1，a2，…，an互質，若a1，a2，…，an中每兩個整數互質，我們就說它們兩兩互質.顯然若整數a1，a2，…，an兩兩互質，則（a1，a2，…，an）＝1，反過來卻不一定成立.且若a1，a2，…，an不全為零，則（a1，a2，…，an）是存在的.

若a1，a2，…，an是任意n個不全為零的整數，則a1，a2，…，an與|a1|，|a2|，…，|an|的公因數相同；（a1，a2，…，an）＝（|a1|，|a2|，…，|an|）.

一個大于1的整數，如果它的正因數只有1及它本身，就叫作質數（或素數）；否則就叫做合數.設a是任一大于1的整數，則a的除1外最小正因數q是一質數，并且當a是合數時，q≤a.若p是一質數，a是任一整數，則a能被p整除或p與a互質.設a1，a2，…，an是n個整數，p是質數，若p|a1，a2，…，an，則p一定能整除某一ak.

函數［x］與{x}是對于一切實數都有定義的函數，函數［x］的值等于不大于x的最大整數；函數{x}的值是x-［x］.我們把［x］叫做x的整數部分，{x}叫做x的分數部分.在n！的標準分解式中質因數p(p≤n)的指數.

h=np+np2+…=∑∞r=1npr，

n!=∏p≤np∑∞r=1npr .

其中∏p≤n表示展布在不超過n的一切質數上的積式.

從三個不同的元素中任取兩個，不管怎樣的順序并成一組，求一共有多少個不同的組.這就是要研究的組合問題.一般地說，從n個不同元素中，任取m(m≤n)個元素并成一組，叫做從n個不同元素中取出m個元素的一個組合.如果兩個組合中的元素完全相同，那么不管元素的順序如何，都是相同的組合；只有當兩個組合中的元素不完全相同時，才是不同的組合.從n個不同元素中取出m(m≤n)個元素的所有組合的個數，叫做從n個不同元素中取出m個元素的組合數.從n個不同元素中取出m個元素后，剩下n-m個元素的唯一的一個組合；反過來也是一樣.因此，從n個不同元素中取出m個元素的組合數Cmn，等于從n個不同元素中取出n-m個元素的組合數Cn-mn，即Cmn＝Cn-mn.

設m和n是整數.如果存在整數k，使m＝kn，則說m被n整除或n整除m，這個情況記作n|m.如果m|n1，m|n2，…，m|nk，那么m稱為數n1，…，nk的公因子.這些數的最大公因子記為(n1，n2，…，nk).如果它等于1，則數n1，…，nk稱為互素.如果n1|m，n2|m，…，nk|m，則m稱為m，…，nk的公倍數.數n1，…，nk的最小公倍數記為［n1，n2，…，nk］.我們有關系式［m，n］=mn(m，n).如果(m，n)=k，那么對任何整數p存在整數x，y使mx+ny=kp.

大于1的正整數p，如果它的正因子只有1和p，則它稱為素數.素數的集是無限的，每個正整數n可以用唯一的方式表示成n=pm11…pmkk，這里p1

設n是正整數，不超過n的與n互素正整數個數記作φ(n)（歐拉函數）.如果n=pm11…pmkk是n的標準素因子分解式，那么nφ(m)≡1(modm)(歐拉定理).特別地，如果p是素數，n不能被p整除，那么np-1=1(modp)（費爾馬定理）.

φ(n)=∏ki=1(pmi1-pmi-1i)=n∏ki=11-1pi.

設m，n是整數，k是正整數.如果k|(m-n)，那么數和m和n稱對模k同余，記作m=n(modk).如果m是大于1的整數，(n，m)=1.那么對于任意實數x，表示式［x］表示不超過x的最大整數；［x］稱為數x的整數部分.數{x}=x-［x］稱數x的小數部分.

一個給定的素數p在數n！的標準素因子分解式中的方次等于np+np2+np3+….

設M是某個有限集.M的元素有序的選取稱做排列；M的元素無序的選取稱做組合.在排列和組合中M的同一個元素可以允許重復選取，也可以不允許重復選取，從n個元素取k個的不重復排列數用pkn表示，并且等于n!(n-k)!.從n個元素取k個的不重復組合數用Ckn表示，并且等于n!k!(n-k)!.從n個元素取k個的重復排列數等于nk.從n個元素取k個的重復組合數等于Ckn+k-1.為了推導這個公式，注意到從n個元素取k個的重復組合數等于方程k=x1+x2+…+xn的非負整數解數這個事實，是有益的.還有下列的關系式成立：

(x+y)n=∑nk=0Cknxkyn-k，

Ckn+Ckn-1=Ck+1n，∑nk=0Ckn=2n，

∑nk=0(-1)kCkn=0，∑nk=1(-1)k#8226;kCkn=0(n>1)，

∑CrnCrm=Cmn+m(n≤m)，

∑mn=rCrn=Cr+1m+1(m≥r)，

∑nk=r(-1)kCrkCkn=0(0>r).

【參考文獻】

江澤堅.數學分析.人民教育出版社，1965.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文