《數(shù)學(xué)競賽》第三章-數(shù)論2012.2 (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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