10數(shù)論問題的常用方法(教師版)

1、數(shù)論問題的常用方法數(shù)論是研究數(shù)的性質(zhì)的一門科學(xué)，它與中學(xué)數(shù)學(xué)教育有密切的聯(lián)系。數(shù)論問題解法靈活，題型豐富，它是中學(xué)數(shù)學(xué)競賽試題的源泉之一。下面介紹數(shù)論試題的常用方法.1. 基本原理為了使用方便，我們將數(shù)論中的一些概念和結(jié)論摘錄如下：我們用(a1, a2,.,an) 表示n個整數(shù)a1 ,a2 ,an的 最大公約數(shù)。用 a1,a2,an表示a1 ,a2 , ,an的 最小公倍數(shù)。對于實數(shù)x，用 x表示 不超過x的最大整數(shù)，用 x= x- x表示 x的小數(shù)部分。對于整數(shù)a,b ,若 m | (a b) ， m 1, 則稱 a,b關(guān)于 模 m 同余 ，記為a b(mod m) 。對于正整數(shù)m ，用(m

2、)表示1 ， 2， ， m中與 m 互質(zhì)的整數(shù)的個數(shù)，并稱 (m)為 歐拉函數(shù) 。對于正整數(shù)m ，若整數(shù)r1, r2,., rm中任何兩個數(shù)對模m均不同余，則稱 r1, r2 ,.,rm為模m的一個 完全剩余系；若整數(shù)r1,r2,.,r (m)中每一個數(shù)都與m互質(zhì)，且其中任何兩個數(shù)關(guān)于模m不同余，則稱 r1 ,r2,.,r (m)為模m的 簡化剩余系。定理 1 設(shè) a, b 的最大公約數(shù)為d ，則存在整數(shù)x, y ，使得d xa yb .定理 2 ( 1)若aibi(modm)， i 1 ， 2，n， x1 x2(modm)，則nnii aix1bix2i ；i1i1( 2)若a b(mod

3、m) ， d (a, b) ， d | m，則a b (mod m) ；dd dab( 3)若a b(mod m) ， d (a, b) ，且 (d , m) 1 ，則(mod m)；dd( 4)若a b ( modmi ) ， i 1,2,.,n ， M= m1,m2 ,.,mn，則a b ( mod M ) .定理 3 ( 1) x 1 x x x 1 ；( 2) x y x y；( 3)設(shè)p 為素數(shù)，則在n! 質(zhì)因數(shù)分解中，p 的指數(shù)為nk .k1p定 理 4 (1 ) 若 r1 ,r2,.,rm 是 模 m 的 完 全 剩 余 系 ，(a,m)1 ， 則 ar1b,ar2 b,., a

4、rm b也是模 m 的完全剩余系；( 2) 若 r1, r2,., r (m)是模 m的簡化剩余系，(a, m) 1 ， 則 ar1 ,ar2.,ar (m)是模 m的簡化剩余系.定理 5( 1 )若 (m, n) 1 ，則 (mn) (m) (n) .(2) 若 n 的標(biāo)準(zhǔn)分解式為np11 p22 . pkk ， 其中 1, 2,. k 為正整數(shù)，p1 , p2 ,.pk 為互不相同的素數(shù)，則111(n) n(11 )(11 ) . .1. ( 1 ).p1p2pk對于以上結(jié)論的證明，有興趣的讀者可查閱初等數(shù)論教材.2 方法解讀對于數(shù)論試題，除直接運用數(shù)論的基本原理外，常用的基本方法還有因式

5、(因數(shù))分.下面解法，配對法，分組法，估值法，同余方法，構(gòu)造法，調(diào)整法，數(shù)學(xué)歸納法與反證法分別予以說明2.1 基本原理的應(yīng)用例 1 設(shè)正整數(shù)a ， b ， c的最大公約數(shù)為1，并且1)abab證明： (a b)是一個完全平方數(shù).證 設(shè) (a,b) d ,a a1d ,b b1d ,其中(a1,b1 ) 1.由于 (a,b,c) 1 ，故有 (d ,c) 1.由(1)得a1b1da1c b1c ( 2)由(2)知，a1|b1c，又(a1, b1 )1 ，a1| c.同理可證b1| c，從而有a1b1|c，設(shè)c a1b1k ，k 為正整數(shù)，代入(2)得d k(a1 b1 )( 3)由(3)知k |

6、 d ，又 k | c ， k | (d, c) 1 ， k 1 . da1b1.2 a b d(a1 b1) d .故 (a b)是一個完全平方數(shù).例 2 設(shè) n為大于 1 的奇數(shù)，k1，k2， ，kn 為給定的n個整數(shù) .對于 1,2,., n的任n一排列 P (a1,a2,.,an) ， 記 s(P)kiai ， 試證存在 1,2,., n 的兩個不同的排列i1B、 C，使得 n!| s(B) s(C) .證 假設(shè)對于任意兩個不同的排列B、 C， 均有 n! 不整除 s(B) S(C) .令 X為 1,2,., n 的所有排列構(gòu)成的集合，則 s(P) | P X 為模n! 的一個完全剩余

7、系，從而有n (1 n!) n!1)2)s(P) i (1 n!) n!(mod n!)PXi12n n!(n 1) n又 s(P) (kiai)=n!(n 1)kiPXPX i12 i1而 n 為大于 1 的奇數(shù)，所以由(1) ， ( 2)得(1 n!)n! n!(n 1) nki0( m ond!) .22 i1 i又 (1 n!,n!) 1 ，所以 n! 0(mod n!) ，矛盾 .2這個矛盾表明必存在B、 C X ， B C，使得 n!| s(B) s(C) .2.2 因式(數(shù))分解數(shù)論中許多問題直接與因式(數(shù))分解相關(guān)聯(lián)，如合數(shù)問題，整除問題等常常是要證明某種分解式的存在.數(shù)的標(biāo)準(zhǔn)

8、分解式本身就是一種特定形式的因數(shù)分解.在不定方程的求解與一些代數(shù)式的求值中，因式(數(shù))分解能幫助我們確定某些變量的取值范圍，尋找到解題的方法.例 2 求三個素數(shù)，使得它們的積為和的5 倍 .解 采用分析中的記號，易知a ， b ， c 中必有一個為5，不妨設(shè)c 5 ，則有ab a b 5，從而有 (a 1)(b 1) 6 .因為 a 1 與 b 1 均為正整數(shù)，不妨設(shè)a b ，則有a1 1a1 2或，b16b13從而知 a 2 ， b 7 .故所求的三個素數(shù)為2， 5， 7.2.3 配對例 4 設(shè) k 為正奇數(shù)，證明：1 2 3 . n整除 1k 2k . nk.分析 因為 1 2 3 . n

9、 n(n 1).故需證 n(n 1) |2(1k 2k . nk)， 注意到 2當(dāng) k 為奇數(shù)時，xkyk 可因式分解，因此可將2(1k2k. nk )中的 2n個數(shù)兩兩配對.證 2(1k 2k . nk)=1k (n 1)k 2k (n 2)k . (n 1)k 1k 2nk，而當(dāng) k 為奇數(shù)時，a b| akbk，從而知n|21k2k . nk( 1)又 21k 2k . nk =1knk 2k(n 1)k . nk 1k， (n 1) | 2(1k 2k . nk)( 2)由( 1) ( 2)知，n(n 1) | 2(1k 2k . nk) ，故結(jié)論成立.2.4 分組例 5 ( 1990

10、年高中聯(lián)賽試題)設(shè)E1,2,.,200， G a1,a2,.,a100 E ，且 G具有下列性質(zhì)：( 1) 對任何 1 i j 100， ai aj 201；100( 2) ai10080.i1試證： G 中的奇數(shù)的個數(shù)是4 的倍數(shù)，且G 中所有數(shù)的平方和是一定數(shù).證 對于 1 i 100， 令 i 2i 1， i 201 i .Ei i , i ， 則 G 中恰含 Ei 中的一個元素.設(shè) G 中 有 k 個 奇 數(shù) i ， i ， ， i ， 有 s個 偶 數(shù) j , j ,., j ， 這 里i1,i2,. ik, j1,j2,. j,s =1,2,.,100 .由題設(shè)知，kskskkks

11、10080= ij (201 i ) j =201 2 i + ijt1r1t1r1t1t1t1r1k= 201k 2 i + (2 4 6 . 200) t1k= 201k 2it 10100.t11)k201k 2it20t1kit為偶數(shù)，所以4 | 2it ，又4 | 20，所以4 | 201k ，4 | k ，即k是 4 的倍數(shù) .t1100ksai2i2tj2ri1t1r1ks(201it )2j2rt1r1kk2012 2 201 i +t1t1第 14 頁 共 10 頁ksk( i2j2 )=2012k 2 201 i +(22 42 62 . 2002)t1r1 rt1100(

12、100 1)(200 1)62)k= 201(201k 2 it)+4t1將( 1)代入(2)得1002aii1201 ( 20) 4100101201=1349380.62.5 估值例 6 令 an表示前n 個質(zhì)數(shù)之和，即a1 2， a22 3 5,a3 2 3 5 10 , ,證明：對任意的正整數(shù)n ，區(qū)間an,an 1中包含有一個完全平方數(shù).分析 設(shè) 質(zhì)數(shù) 從小到大依次為p1, p2,., pk ，要結(jié)論成立，只要存在正整數(shù)m ，使an man 1 ，只要anm an 1 ，只要a n 1an1 ，只要an 1an12an ，只要pn 112an只要( 1 )(pn 1 1)2 4an

13、4( p1p2 .pk)證 直接驗證易知 a1,a2， a2,a3 ， a3,a4， a4,a5 中都含有1 個完全平方數(shù).當(dāng)n 5 時，我們證明(1 )式成立.為此，令f(n 1) p(n 121)p41( p 2.p.k ，)22則 f(n 1) f(n)(pn 11)(pn1) 4pn=(pn1pn)(pn1pn 2)4pn.因為當(dāng) n 2 時， pn 為奇數(shù)，所以pn 1pn2，f (n 1) f(n) 2(pn 1pn 2 2pn)=2(pn 1 pn 2) 0，故當(dāng) n 2 時，數(shù)列f (n) 為遞增數(shù)列.由于22f(5) (p5 1)2 4(p1p2p3 p4)=(11 1)2

14、4(2 3 5 7) =32> 0所以當(dāng) n 5時， f (n) f (5) 0 .故當(dāng)n 5時(1)式成立.例 7 求出不定方程(n 1)! nk 1( 1)的全部正整數(shù)解.解 當(dāng) n 2 時，易得k 1 ；當(dāng) n 2 時， ( 1 )式左邊為偶數(shù)，故右邊也是偶數(shù)，所以 n 為奇數(shù).當(dāng)n 3時，由k2! 3k 1 ，得 k 1 .當(dāng) n 5時，由 k4! 5k 1 ，得 k 2.n1n1n1當(dāng) n 5 且 為 奇 數(shù) 時 ， n 1 n 3 ， n 12 ， 故 2 n 1 |(n 2)! ， 即222(n 1) |(n 2)!，因此 (n 1)2 |(n 1)!，所以(n 1)2 |

15、(nk 1).另一方面，由二項式定理知nk 1 (n 1) 1)k 1 =A(n 1)2+ k(n 1) .其中 A 為整數(shù)，所以(n 1)2 | k(n 1) ，故 (n 1) |k ，因此 k n 1 ，從而有nk 1 nn 1 1 (n 1)! .這說明當(dāng)n5時，方程(1)無解，故方程(1)的解為(n,k) (2,1)， (3,1)， (5,2)2.6 同余例 8 證明993993 991991 能被1984整除 .證 993993 ( 991)993=( 991)2( 991) 991991991=(495 1984 1)( 991)991( 991)991(mod1984) ， 99

16、3993 991991 ( 991) 991 991991 0(mod1984) . 1984|993993 991991.例 9 用數(shù)碼 1 ， 2， 3， 4， 5， 6， 7 排成 7 位數(shù)，每個數(shù)碼恰用一次，證明：這些7 位數(shù)中沒有一個是另一個的倍數(shù).證 若有兩個7 位數(shù) a ， b ，使得a kb( 1 )由于 a ， b 均是由1， 2， .,7 所排成，故2 k 7由( 1)得a kb(mod 9) ， 1 k 1(mod 9) ，即 k 1(mod 9)，這與2 k 9矛盾，故結(jié)論成立.2.7 構(gòu)造例 10 若一個正整數(shù)的標(biāo)準(zhǔn)分解中， 每個素約數(shù)的冪次都大于1， 則稱它為冪數(shù)，

17、證明：存在無窮多個互不相同的正整數(shù)，它們及它們中任意多個不同數(shù)的和都不是冪數(shù).證 將全體素數(shù)從小到大依次記為p1， p2， .， pn ， .令 a1p1 ， a2p12 p2，當(dāng)n2時，222anan 1pn 1pn p1 p2.pn1pn，下證a1 ， a2 ， ， an ， 滿足要求.事實上，pn | an ，但pn2 | an，所以an不是冪數(shù).又對于1 i1 i2 ik ，ai2aik2 22ai1ai2aikai1(12k)=ai1(1Api1)=p12p22pi121pi1(1Api1)，ai1ai1其中 A 為正整數(shù).因為( pi ,1Api) 1 ， 所以pi在(aiaiai

18、 ) 的標(biāo)準(zhǔn)分解中的冪次為 1，因而不是冪數(shù).例 11 設(shè) 1,2,3,2011 中質(zhì)數(shù)的個數(shù)為a， n為正整數(shù)且1 na，求證必有2011個連續(xù)正整數(shù)，其中恰有n 個質(zhì)數(shù) .證令A(yù)k k, k 1,k 2,k2010 ，并令f(k) 為Ak中質(zhì)數(shù)的個數(shù)，則易知f(1)a，f(2012! 2) 0. 對于k1,2,(2012!1)，顯然有| f(k 1) f(k)| 1，所以對于0 n a ，必存在一個k0，使得f(k0) n，從而 Ak 中的 2011 個連續(xù)整數(shù)滿足要求.2.9 數(shù)學(xué)歸納法2n2例 12 設(shè) n是正整數(shù)，求證：512 |32n 32n2 24n 1 .2n2證 令 f(n) 32n 32n2 24n 1 . 因 為 f (1) 0 ， 所 以 512 | f (1) ， 假 設(shè)512 | f (n) ，那么對于n 1 ，因為f(n 1) f (n) 8(32n 8n 1)，所以要證 512 | f (n 1)，只需證512|8(32n 8n 1)，即只需證明64| (32n 8n 1) .為此，令g(n) 32n 8n 1 .顯然有 64 | g(1) 0 ，假設(shè)64 | g(n)，由于g(n 1) g(n) 8(9n 1) 64(9n 1 9n 21)， 64 | g(n 1) ，由歸納法原理知對一切n ，有64 |32n 8n 1 ，從而有512