《數學競賽》第三章-數論2012.2 (1)

1、第二篇 競賽數學的主要內容第三章 數論 §3．1 整數的奇偶性和整除性 §3．2 同余 §3．3 不定方程 §3．4 高斯函數[x],2024/3/20,第三章 數 論,2,第三章 數 論,3．1 整數的奇偶性和整除性,一、整數的奇偶性,1、偶數+偶數=偶數；奇數+奇數=偶數； 奇數+偶數=奇數2、a,b為整數，若a±b為偶數，則a,b的奇偶性相同

2、；若a±b為奇數，則a,b的奇偶性相反。3、奇數個奇數之和是奇數； 偶數個奇數之和是偶數。4、奇數×奇數=奇數；偶數×偶數=偶數； 奇數×偶數=偶數,2024/3/20,第三章 數 論,3,第三章 數 論,3．1 整數的奇偶性和整除性,一、整數的奇偶性,5、任意n個奇數的積仍是奇數，奇數的n次冪是奇數。若n個數的積為奇數，則這n個數均為奇數。6、若任意有限個整數

3、中至少有一個偶數，那么它們的積是偶數；反之，任意有限個整數之積是偶數，則這些因數中至少有一個偶數。 7、 若a,b為整數，則a+b與a-b奇偶性相同,2024/3/20,第三章 數 論,4,第三章 數 論 3．1 整數的奇偶性和整除性,,一、整數的奇偶性,例1.在1, 2, 3, ?, 1999 這1999 個數的前面任意添上正號或負號, 問它們的代數和是奇數還是偶數?,例2.設a1 , a2 , ?, an 是自然數 1, 2, ?

4、, n 的一個排列, 若n 為奇數,求證: ( a1 - 1) ( a2- 2) ?( an- n) 為偶數。,2024/3/20,第三章 數 論,5,第三章 數 論 3．1 整數的奇偶性和整除性,,一、整數的奇偶性,例3.設n個整數a1 , a2 , ?, an 的積等于n，其和為0. 證明：4|n.,例4.設n個數x1 , x2 , ?, xn ,它們中的每一個要么是1，要么是-1.若x1 x2 +x2 x3

5、+ ? +xn-1 xn+xn x1=0 . 證明：4|n.,2024/3/20,第三章 數 論,6,二、整數的整除性,3．1 整數的奇偶性和整除性,1. 整除的定義：對于兩個整數a、b(b≠0）， 若存在一個整數c，使得 a=bc ① 成立，則稱b整除a，或a被b整除，記作b|a。a叫做b的倍數，b叫做a的約數（因數）。,若滿足①的整數

6、c不存在，就稱a不能被b整除，或b不能整除a，記作b ?a， 如2|6，4 ? 6。,2024/3/20,第三章 數 論,7,2、整除的性質,3．1 整數的奇偶性和整除性,性質1 a,b,c為整數， 1）a|a; 2）若c|b，b|a，則c|a ;（傳遞性） 3）若a|b，a|c，則a|（ma+nb），m、n為任意整數.性質2 等式中除某一項外，其他所有項都能被m整除，則這一項也能被m整除。性質3 1)若a|bm

7、，且（a，b）=1，則a|m； 2) 若a|m，b|m，且（a，b）=1，則ab|m； 3) 若p為質數，且p|ab ，則p|a，或p|b。,二、整數的整除性,2024/3/20,第三章 數 論,8,3．1 整數的奇偶性和整除性,,連續(xù)整數之積的性質① 任意兩個連續(xù)整數之積必定是一個奇數與一個偶數之一積，因此一定可被2整除。② 任意三個連續(xù)整數之中至少有一個偶數且至少有一個是3的倍

8、數，所以它們之積一定可以被2整除，也可被3整除，所以也可以被2×3=6整除。這個性質可以推廣到任意個整數連續(xù)之積。,二、整數的整除性,2、整除的性質,2024/3/20,第三章 數 論,9,3．1 整數的奇偶性和整除性,,例10. 設p是大于5的素數，求證：240|p4-1.,例11. p≥5是素數，且2p+1也是素數，證明：4p+1必是合數。,二、整數的整除性,2024/3/20,第三章 數 論,10,3．1 整數的奇偶性

9、和整除性,,1.證明：不定方程x2+y2=1983無整數解.3.能否找到10個奇數，使它們的倒數和等于1？,二、整數的整除性,4. 方程ax2+bx+c=0，其中a、b、c都是奇數，證明此方程無整數解.,2024/3/20,第三章 數 論,11,第三章 數 論,3．2 同 余,一、同余的定義和性質,2024/3/20,第三章 數 論,12,3．2 同 余,一、同余的定義和性質,2024/3/20,第三章 數 論,13,3．2

10、 同 余,一、同余的定義和性質,2024/3/20,第三章 數 論,14,3．2 同 余,一、同余的定義和性質,2024/3/20,第三章 數 論,15,3．2 同 余,一、同余的定義和性質,例1.今天是星期四，則101000天后是星期幾？例2.證明：993993+991991能被1984整除.,習題3.21.n為任意正整數，證明：A=2034n + 846n -1917n -963n 能被1989整除.,2024/3/20,

11、第三章 數 論,16,3．2 同 余,一、同余的定義和性質,例3.求證：x14 +x24 + x34 + … + x144 =1599無整數解.,（1898年匈牙利奧林匹克競賽題）求使2n+1能被3整除的一切自然數n. 求證31980+41981能被5整除.,2024/3/20,第三章 數 論,17,3．2 同 余,二、剩余類、完全剩余系、費馬小定理,定理3（費馬小定理）設p是素數，且(a,p)=1，那么 ap-1 ≡１（mod

12、 p） .更一般地,設p是素數,對任意整數a,有ap ≡a(modp).,例9.求20032005 被17除的余數.,習題3.25.求19992000被29除的余數.,例13.設a為正整數，且17?a，求證：a8 -1與a8 +1中有且僅有一個能被17整除.,2024/3/20,第三章 數 論,18,第三章 數 論,3．3 不定方程,不定方程是數論中最古老的分支之一。 古希臘的丟番圖（Diophantus）早在公元

13、3世紀就開始研究不定方程，因此常稱不定方程為丟番圖方程. 中國是研究不定方程最早的國家.公元5世紀的《 張丘建算經》中的百雞問題標志中國對不定方程理論有了系統(tǒng)研究.秦九韶的大衍求一術將不定方程與同余理論聯(lián)系起來. 百雞問題說：“雞翁一，直錢五，雞母一，直錢三，雞雛三，直錢一.百錢買百雞，問雞翁、母、雛各幾何？”. 費馬（Fermat）大定理（當n＞2時，xn＋yn＝zn沒有非平凡的整數解），歷經30

14、0余年，已由英國數學家安德魯 ·維爾斯（A.Wiles ）證明。,丟番圖,數書九章——大衍類,2024/3/20,第三章 數 論,19,3．3 不定方程,一、一次不定方程,2024/3/20,第三章 數 論,20,3．3 不定方程,一、一次不定方程,1.觀察法2.逐步取整法,例.求4x-3y=10的整數解.,例1.求37x+107y=5的整數解.,2024/3/20,第三章 數 論,21,3．3 不定方程,一、一次不定

15、方程,1.觀察法2.逐步取整法,例2.求不定方程25x+13y+7z=4的整數解.,多元一次不定方程,2024/3/20,第三章 數 論,22,3．3 不定方程,二、高次不定方程,1.分解因式（因數）2.估計方法3.同余方法,例3.求不定方程 x2y + 2x2 -3y -7=0 的整數解.,例6.求不定方程 x3 +y3 =1072 的正整數解.,2024/3/20,第三章 數 論,23,3．3 不定方程,二、高次不定方程,

16、1.分解因式（因數）2.估計方法3.同余方法,例8.求所有正整數m，n，使得1！+2！+…+m!=n2.,習題3.34.求不定方程 3x2-4xy+3y2=35 的正整數解.5.求不定方程 x2+xy+2y2=29 的整數解.,2024/3/20,第三章 數 論,24,第三章 數 論,3．4 高斯函數[x],,,2024/3/20,第三章 數 論,25,3．4 高斯函數[x],2024/3/20,第三章 數 論,26,