初等數(shù)論(四)-幾個著名的數(shù)論定理

初等數(shù)論(四)--幾個著名的數(shù)論定理一些常用概念?歐拉函數(shù)9(n)—介于1和n之間與n互質(zhì)的自然數(shù)個數(shù)?縮系一-在9(n)個剩余類中各取一個元素，它們形成一個模n的縮系問題：為什么要介紹縮系這個概念呢？這是因為當(dāng)我們定一個縮系后，剩余類中的其它元素均可以由縮系生成。設(shè)(a,m)=1，則有s,t使得as+mt=1。任取一個不是縮系中的元素b，就有b=asb+mtb從而有b三asb(modm)。即，b可以表成ka(modm)的形式(即，由a的若干倍生成)，從而凡是與b有關(guān)的數(shù)論問題(在模m的意義下可以轉(zhuǎn)化為a的問題)。這就是群論中的生成元的問題。在高中里面的復(fù)數(shù)理論中也是如此。下面這個結(jié)果表明了一種構(gòu)造縮系的方法：例1.設(shè)(m,n)二1。如果{a,a，…,a},{b,b，…,b}分別是模m和模n的縮系，那么12t12sS={mb+na|1<i<s,1<j<t}ij就是模mn的縮系。解答：第一步。先證明S中每一個元素都與mn互質(zhì)。這是顯然的。第二步。證明S任意兩個數(shù)關(guān)于模mn不同余。假定有某兩個數(shù)mb+na與mb'+na'關(guān)于i j i j模mn同余，mb+na三mb'+na'(modmn)ijij則必有m(b一b')三n(a'一a)(modmn)。從而有ii jj(b—b')三0(modn),(a—a')三0(modm)，ii ii即有b=b',a=a'，矛盾！iijj第三步。證明：如果一個數(shù)c與mn互質(zhì)，那么必然與S中某個元素關(guān)于模mn同余。由于(m,n)=1,方程mx三c(modn)在模n剩余類中有解；由于(c,n)=1,所以(x,n)=1。因此，x與某個b在模n的同一個剩余類中，即有i

同理有a使得自然有根據(jù)(m,n)同理有a使得自然有根據(jù)(m,n)二1,mb三c(modn);ina三c(modm)jmb+na三c(modn);ijmb+na三c(modm).ijmb+na三c(modmn)ij這就網(wǎng)完成了證明。例2.在1,2,3,...,pa中有多少個數(shù)與pa互質(zhì)？解答:在1,2,3,...,pa中不與pa互質(zhì)的數(shù)有形式kp,1<k<pa-i。所以f1)申(Pa)二pa—pa-1二pa1—一。IP丿如果自然數(shù)n二伴仔…佇,那么f1-1]9(n)二nXX...X1p1丿1p2丿1匕丿Ip丿關(guān)于9(n)Ip丿申(n)二nnpkP質(zhì)數(shù)注意:大家可以嘗試用容斥原理來證明這個公式。面介紹著名的費馬小定理例2.設(shè)m是一個自然數(shù)，(a,m)=l。證明：a9(m)三1(modm)。這就是著名的歐拉定理。如果取m=p為質(zhì)數(shù)，那么就成為了費馬小定理。證明：設(shè)x,x,...,x(t=9(m))是一個模m的縮系。那么12tax,ax,...,ax12t中任何兩個都與m互質(zhì)，其中沒有兩個相同。從而它也是一個縮系，在模m的意義下，aX1,比,…,axt僅僅是沁,..吧的一個置換。從而有axax...ax三xx...x(modm)。1 2 t 12t證明完畢。例3?證明：任意的2p-1個整數(shù)中一定可以選出p個數(shù)，它們的和可以被p整除，這里p是一個質(zhì)數(shù)。證明：反證法。如果ai,「?, 中任意p個數(shù)ai，ap的和都不是p的倍數(shù)，那么由費馬小定理有TOC\o"1-5"\h\z\o"CurrentDocument"(a+a+...+a)p-1三1(modp)。i1 i2 ip注意到形如上式的組合共有Cd個，對所有這樣可能的組合求和后得到;工(a+a+...+a)p-1三Cp(modp)i1 i2 ip 2p-1因為辺-1三］罟卜1(mod幾\o"CurrentDocument"(a+a+...+a)p-1展開后得到形如a^a?2...a?z(/<p-1)的項。在工中含有i1 i2 ip i1i2 ila%a?2...a?z(/<p-1)的項有Cp-1個(即，從a,a,...,a以外的書中取p—/個與它搭ii i 2p-1-1 ii i1 2 1 1 2 p(2p-1-1)(2p-1)...(