完全剩余系與縮剩余系的性質(zhì)及解法

《完全剩余系與縮剩余系的性質(zhì)及解法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、6中等數(shù)學(xué)完全剩余系與縮剩余系的性質(zhì)及解法何憶捷(華東師范大學(xué)理工學(xué)院數(shù)學(xué)系2012級(jí)博士研究生，200041)中圖分類號(hào)：0156．1文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1005—6416(2015)06-0006—06(本講適合高中)價(jià)于其均與n互素，且關(guān)于模凡兩兩不同余．剩余類與剩余系是初等數(shù)論中的重要概性質(zhì)2若a(1≤i≤12)構(gòu)成模n的完念．在數(shù)學(xué)競(jìng)賽中，除數(shù)論問題外，許多組合系，、m∈Z，(m，12)=1，則k+(1≤≤n)題、甚至代數(shù)題也與剩余類、剩余系有密切的也構(gòu)成模的完系；聯(lián)系．在解題時(shí)，不僅需要熟悉剩余系(完全若a(1≤i≤(n))構(gòu)成模的縮系，剩余系或縮

2、剩余系)的性質(zhì)，還經(jīng)常需要借、m∈Z，(m，n)=1，貝0n+mn(1≤i≤助整體化思想來考慮剩余系．(n))也構(gòu)成模的縮系．性質(zhì)3若a(1≤i≤n)構(gòu)成模凡的完1知識(shí)介紹系，則1．1定義一(±!2(1)剩余類對(duì)正整數(shù)n，把全體整數(shù)按模12的余數(shù)『詈(modn)，凡為偶數(shù)；三分成／2類，每一類數(shù)的全體稱為模12的一個(gè)【0(modn)，n為奇數(shù)．剩余類(或稱同余類)．性質(zhì)4若a、b(1≤i≤(n))均構(gòu)成(2)完全剩余系模n的縮系，則在模12的每個(gè)剩余類中各取一個(gè)元素，則這n個(gè)數(shù)就組成模n的一個(gè)完全剩余系酊6(m。d凡)．(以下簡(jiǎn)稱完系)．性質(zhì)3與性質(zhì)4是從整體的角

3、度考慮完(3)縮剩余系系和縮系，這樣的想法也是解決許多問題的在任意一個(gè)模n的完全剩余系中，僅保出發(fā)點(diǎn)．以下兩例是其簡(jiǎn)單應(yīng)用．留與n互素的那些數(shù)(共(凡)個(gè)數(shù)，其中，2應(yīng)用舉例(n)為歐拉函數(shù))，則這(12)個(gè)數(shù)組成模12的一個(gè)縮剩余系(或稱既約剩余系、簡(jiǎn)化剩例1設(shè)兒為偶數(shù)，0i、bi(1≤i≤n)均構(gòu)余系，以下簡(jiǎn)稱縮系)．成模n的完系．證明la+b(1≤i<~／2)不構(gòu)成1．2常用性質(zhì)模凡的完系．性質(zhì)1對(duì)于／2個(gè)整數(shù)，其構(gòu)成模n的證明由性質(zhì)3知完系等價(jià)于其關(guān)于模n兩兩不同余；對(duì)于(n)個(gè)整數(shù)，其構(gòu)成模的縮系等∑ai三∑b三詈(mod／2)．收稿13期：2015—0

4、2—02則∑i=1(。+bi)三號(hào)+2~2(m。d)．2015年第6期7故a+bi(1≤≤n)不構(gòu)成模n的完系．解由于a。，a：，?，a構(gòu)成模n的縮例2設(shè)整數(shù)n>1，(a，n)=1．證明：系，而(n，2)=1，則2a，2a，?，2a也構(gòu)成a‘三1(modn)．模n的縮系．證明設(shè)a1，a2，?，()構(gòu)成模17,的縮系．由性質(zhì)2知aal，aa2，?，aa)也構(gòu)成模故Ink=lsinaZnkl_I靠k=lsinIn的縮系．a(chǎn)in】j[cos根據(jù)性質(zhì)4得k=lk=lZnk1．口l02?a()蘭(aa1)(aa2)?(aa())因?yàn)榱in≠o'所以，=a縱ak=lIa2?

5、a∞()(modn)．又(aIa2~o．a(chǎn))，n)=1，故Il~COSanSkl=1．口‘蘭1(modn)．【注】本題即為歐拉定理．下面考慮nc。s的符號(hào)，只需確定k=l接下來再看幾個(gè)例子．例3設(shè)n為正偶數(shù)．證明：在n×n矩陣0。，0：，?，口中大于詈的數(shù)的個(gè)數(shù)．l2n不妨設(shè)0n—al>n—a2>?>n—am>0，A=342且n—a(1≤≤m)也構(gòu)成模n的縮系．：：：●●●從而，a+1一=n—a(1≤≤m)．凡1n一1中找不到一組1，2，?，n，其兩兩不同行且不因此，0。，0，?，0中恰有一半大于詈同列．(注意每個(gè)口均不為)．

6、證明反證法．假設(shè)有一組1，2，?，兩兩不同行且不同列，記這組中的k(1≤k≤n)在第a行故亙cos，號(hào)I蕻cosnl第6列．則a、b(1≤i≤n)分別構(gòu)成模n的=(一1)丁(m=(n)為偶數(shù))．兀為·另一方面，根據(jù)矩陣A的特點(diǎn)知【注】這是一道三角公式與剩余系性質(zhì)的af+bf蘭+1(modn)．)綜合題，關(guān)鍵思想是從整體考慮模n的縮系故a+b(1≤≤凡)也構(gòu)成模n的完系．a(chǎn)l，a2，?，a與20l，2口2，?，20，結(jié)合誘導(dǎo)公注意到，17,為偶數(shù)，上述結(jié)論與例1矛式建立耳msin與sin之間的關(guān)系，盾．因此，矩陣中不存在一組1，2，?，n兩兩=1，=1，不同行且不同

7、列．恰能求出nCOS的絕對(duì)值．值得注意的【注】本題中，式①刻畫了矩陣的特征，將組合問題轉(zhuǎn)化為一個(gè)關(guān)于完系的常規(guī)問題．是，若本題中a，，a，?，a僅僅為模n的(任例4設(shè)奇數(shù)凡>1．求nc。s竽的值，意的)縮系，則無法判定立k：1c。sl／,的符號(hào)．其中，a。，a，?，a為所有不大于n且與n互例5對(duì)以下兩個(gè)問題，分別求正整數(shù)n素的正整數(shù)．的所有可能值：8中等數(shù)學(xué)(1)存在口1，02，?，n，使得0、0l+i(2)若存在整數(shù)0、b(1≤i≤n)，使得(1≤i≤)分別構(gòu)成模n的完系；0、6、口+6、口一6(1≤i≤n)均構(gòu)成模n的(2)存在口1，02，?，0，使得口、0+

8、i、完系，