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

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

1、6中等數(shù)學完全剩余系與縮剩余系的性質(zhì)及解法何憶捷(華東師范大學理工學院數(shù)學系2012級博士研究生，200041)中圖分類號：0156．1文獻標識碼：A文章編號：1005—6416(2015)06-0006—06(本講適合高中)價于其均與n互素，且關于模凡兩兩不同余．剩余類與剩余系是初等數(shù)論中的重要概性質(zhì)2若a(1≤i≤12)構(gòu)成模n的完念．在數(shù)學競賽中，除數(shù)論問題外，許多組合系，、m∈Z，(m，12)=1，則k+(1≤≤n)題、甚至代數(shù)題也與剩余類、剩余系有密切的也構(gòu)成模的完系；聯(lián)系．在解題時，不僅需要熟悉剩余系(完全若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知識介紹系，則1．1定義一(±!2(1)剩余類對正整數(shù)n，把全體整數(shù)按模12的余數(shù)『詈(modn)，凡為偶數(shù)；三分成／2類，每一類數(shù)的全體稱為模12的一個【0(modn)，n為奇數(shù)．剩余類(或稱同余類)．性質(zhì)4若a、b(1≤i≤(n))均構(gòu)成(2)完全剩余系模n的縮系，則在模12的每個剩余類中各取一個元素，則這n個數(shù)就組成模n的一個完全剩余系酊6(m。d凡)．(以下簡稱完系)．性質(zhì)3與性質(zhì)4是從整體的角

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

4、2—02則∑i=1(。+bi)三號+2~2(m。d)．2015年第6期7故a+bi(1≤≤n)不構(gòu)成模n的完系．解由于a。，a：，?，a構(gòu)成模n的縮例2設整數(shù)n>1，(a，n)=1．證明：系，而(n，2)=1，則2a，2a，?，2a也構(gòu)成a‘三1(modn)．模n的縮系．證明設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())因為立Sin≠o'所以，=a縱ak=lIa2?

5、a∞()(modn)．又(aIa2~o．a(chǎn))，n)=1，故Il~COSanSkl=1．口‘蘭1(modn)．【注】本題即為歐拉定理．下面考慮nc。s的符號，只需確定k=l接下來再看幾個例子．例3設n為正偶數(shù)．證明：在n×n矩陣0。，0：，?，口中大于詈的數(shù)的個數(shù)．l2n不妨設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中恰有一半大于詈同列．(注意每個口均不為)．

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

7、列．恰能求出nCOS的絕對值．值得注意的【注】本題中，式①刻畫了矩陣的特征，將組合問題轉(zhuǎn)化為一個關于完系的常規(guī)問題．是，若本題中a，，a，?，a僅僅為模n的(任例4設奇數(shù)凡>1．求nc。s竽的值，意的)縮系，則無法判定立k：1c。sl／,的符號．其中，a。，a，?，a為所有不大于n且與n互例5對以下兩個問題，分別求正整數(shù)n素的正整數(shù)．的所有可能值：8中等數(shù)學(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、完系，