九十五年度专题演讲讲义

九十五年度專題演講講義2006淡江數學營李武炎數論上的幾則問題引言1.證明9512-1一定被13整除。2.證明12!+1一定被13整除(不必將12!+1算出再以13除之)數論上有兩個很有名的定理:『費馬定理』若p為質數，a為與p互質的任意整數，則一定被11−−pap整除。『威爾生定理』若p為質數，則+1必為)!1(−pp整除。例1.被13除之餘數為何?132006例2.被13除之餘數為何?962006例3.被13除之餘數為何?952006例4.22!被23除之餘數為何?例5.21!被23除之餘數為何?例6.20!被23除之餘數為何?練習1.被29除之餘數為何?292006練習2.被29除之餘數為何?562006練習3.被29除之餘數為何?552006練習4.18!被17除之餘數為何?練習5.16!被17除之餘數為何?練習6.15!被17除之餘數為何?1練習7.14!被17除之餘數為何?附記:最大新質數德國一位業餘數學家諾瓦克在公元2005年2月發現至今所知最大的一個質數:2的25964951次方減1，這個質數超過七百八十萬位，十分驚人。這個質數是屬於所謂的梅森尼質數(2的n次方減1)2006淡江數學營李武炎n模整數以n為模數的整數(Integersmodulon)，簡稱為模整數。n設≧2為整數，定義一個同餘(Congruent)關係在整數集合Z上：n若、bZ且n|(-b)則稱同餘於b(以為模數)；a∈aan記為a≡b(mod)。n例如：17≡2(mod3)，2≡8(mod3)，31≡16(mod5)。定理1：以為模數的同餘關係是一個等價關係(Equivalencerelation)。n証明：等價關係是一個具備下列三個性質的關係：(1)反身性(Reflexive)：a≡(modn)a∀a∈Z(2)對稱性(Symmetric)：若a≡b(modn)，則b≡(mod)an(3)遞移性(Transitive)：若a≡b(modn)且b≡(modn)，則≡(mod)cacn其簡略說明如下：(1)a−aa=0∴n|a–。(2)b−a=–(a–b)；當|–則n|b–。naba(3)若|(–b)且|(–c)則n|[(–b)+(–)]；即n|–c。nanbabaa定義：在以n為模數的同餘關係下，[]={ax∈Z|≡ax(modn)}。[]是指與有同餘關係的所有整數所成的集合，有時也記為aaa，稱為以為模數的剩餘數(Residueclass)。n例如：當=4時n[0]={…,−8,−4,0,4,8,12,…}[1]={…,−7,−3,1,5,9,13,…}2[2]={…,−6,−2,2,6,10,14,…}[3]={…,−5,−1,3,7,11,15,…}[4]={…,−4,0,4,8,12,16,…}M其中[0]=[4]=[8]=…[1]=[5]=[9]=…ㄧ共有四個不同的classes，即[0]、[1]、[2]及[3]，這四個classes彼此之間都不相交(交集為空集合)，其聯集為整數Z全體，他們形成Z的ㄧ個分割(Partition)由例中我們可觀察到a≡b(mod)[]=[]。n⇔ab定義：在以n為模數的同餘關係下，所得的剩餘數類所成的之集合以記之，nZ即={[0],[1],[2],…,[nZn−1]}。又稱為以為模數的整數(模整數)。nZnn例：={[0],[1],[2],[3]}4Z={[0],[1],[2],[3],[4],[5]}6Z此處中的[0]為{…,4Z−8,−4,0,4,8,…}，此處中的[0]為{…,6Z−12,−6,0,6,12,…}。如果要加以區分，可特別將前者表為，後者記為。4]0[6]0[定義：若[a]、[b]∈nZ規定[]+[b]=[+];aab[a]‧[b]=[]。ab例如：在中，[2]+[3]=[5]=[1];4Z[2]‧[3]=[6]=[2]。在中，[3]+[5]=[8]=[2];6Z[3]‧[4]=[12]=[0]。練習：證明定義中的加法與乘法運算都是定義適當的(Well−defined)。若[]=[]，1a2a[]=[]，1b2b則≡(modn)即1a2a1a−2a=nk≡(mod)1b2bn1b−2b=、lnlk∈Z因此（1a−2a）+(1b−2b)=(+)，nkl3故（+）1a1b−(+)=(k+l)。2a2bn所以+≡+(mod)，1a1b2a2bn即[+]=[+]。1a1b2a2b又=+n1a2ak=+1b2bnk故=(+n)(+)1a1b2ak2bnl=+n++2222abalnbk2nkl=+n[++]2a2b2al2bknkl因此1a1b−2a2b也是的倍數，所以≡(mod)n1a1b2a2bn即[][]=[][]1a1b2a2b定理2：設與為整數且n≧2，若且為若與n互質，則[]在中有乘法反元素。anaanZ証明：若與互質，則存在兩個整數b與使得+n=1。ancabc故ab−1=−nc=(n−c)；因此[]=[1]。ab即[a][b]=[1]，[b]為[]之乘法反元素。a反之，若[b]為[]之反元素，則[][]=[1]或[ab]=1。aab因此n|1−ab。設1−ab=n，Z，則+=1。qq∈abnq若d為與之公因數，an則d|a+，即d|1。bnq因此，a與之最大公因數為1，也就是與互質。nan定義：若={[0],[1],[2],…,[nZn−1]}為n模整數，則為中所有乘法反元素的元素所成的集合。*nZnZ例：={[1],[5]}，={[1],[3],[5],[7]}。*6Z*8Z例：={[1],[5],[7],[11],[13],[17]}為一個具有六個元素的乘法群，其中[5]與[11]互為乘法反元素，[7]與[13]互為乘法反元素，而[17]的乘法反元素為[17]自己。*18Z例：={[1],[2],[3],[4]}*5Z例：={[1],[2],[4],[5],[7],[8]}*9Z4定理3：n≧2為整數，下列是等價的(1)[a]∈，[]0，[]有乘法反元素∀nZa≠a(2)若[a]、[b]∈且[][b]=[0]，則[]=[0]或[b]=[0]nZaa(3)為質數n証明：(1)(2)⇒假設[][b]=[0]，[]、[]aab∈nZ若[]=0，則得證；a若[]0，則根據(1)，[a]有乘法反元素[c]a≠則[][a][b]=[][0]=[0]cc而[c][a]=[1]，故[b]=[0](2)⇒(3)若n不是質數，則=，2nab≤a≤1−n，2≤b≤1−n而[a][b]=[]=[]=[0]且[a]abn≠[0]，[b]≠[0]，與(2)矛盾。因此n為質數。(3)(1)⇒假設為質數，若[]∈且[]nanZa≠[0]則1≤。a≤n故a與n互質。因此，存在兩個整數b、c使得b+=1。acn因此b≡1(mod)an即[]=[1]或[b][]=[1]，[]為[a]的乘法反元素baab例：的乘法表如下5Z‧[0][1][2][3][4][0][0][0][0][0][0][1][0][1][2][3][4][2][0][2][4][1][3][3][0][3][1][4][2][4][0][4][3][2][1]由表可知，[2]與[3]互為乘法反元素；[4]之乘法反元素為[4]自己，5定理4：費馬定理(Fermat’sTheorem)若p為質數，則對於任何整數a恆有(modp)。aap≡事實上，若a與p互質，則(modp)。11≡−pa証明：要證明(modp)等於證明aap≡，[]][][][aaapp==a∈pZ當[]=[0]時，a][]0[]0[][aapp===當[][0]，根據定理5，[a]必有乘法反元素[b]；[b][]=[1]。a≠a將中的每一個異於[0]的元素都乘以[]得[a][1]，[][2]，…，[][ppZaaa−1]。上面的元素都是相異的:若[][ar]=[][as]，則[b][][ar]=[][a][bs]。因此[r]=[1][r]=[1][s]=[s]。而且均不為[0]。故{[a][1]，[][2]，…，[][paa−1]}={[1]，[2]，…，[p−1]}。因此([a][1])([][2])，…，([][paa−1])=[1][2]…[p−1]。即。]1[]2][1[]1[]2][1[][1−=−−ppapLL而[1]，[2]，…，[p−1]均有乘法反元素，因此，在等式之兩邊乘上他們的乘法反元素後，得。]1[1=−pa而且][]1][[]][[][1aaaaapp===−例：求被7除之餘數為何？200594解：2005÷6=334…餘1由費馬定理，。]1[]94[6=因此，即≡3(mod7)。]3[]3][1[]3[]1[]94[)]94([]94[33433462005====200594故餘數為3。6內湖高中數學營上課講義淡江大學數學系李武炎數學遊戲1.規則:有一堆火柴桿(或小石子)兩人輪流取，先取的一方笫一次可任意取，但必須至少取一個且不可全取，以後每次所取的火柴桿數不得超過上一次所取的火柴桿數的兩倍以上，規定取得最後一根者贏。觀察:當火柴桿數為2,3,5.8,13,…時，對先取者不利。2.規則:在三堆小石子(或小沙包)，兩人輪流從中拿取，每人僅限從其中一堆拿取，至少取一個，至多可取一堆；不可跨堆取。規定取得最後一個的人為輸(或贏)。觀察:對先取者不利的格局：(每堆數均不多於15)(1‚2‚3)、(1‚4‚5)、(1‚6‚7)、(1‚8‚9)、(1‚10‚11)、(1‚12‚13)、(1‚14‚15)、(2‚4‚6)、(2‚5‚7)、(2‚8‚10)、(2‚9‚11)、(2‚12‚14)、(2‚13‚15)、(3‚4‚7)、(3‚5‚6)、(3‚8‚11)、(3‚9‚10)、(3‚12‚15)、(3‚13‚14)、(4‚8‚12)、(4‚9‚13)、(4‚10‚14)、(4‚11‚15)、(5‚8‚13)、(5‚9‚12)、(5‚10‚15)、(5‚11‚14)、(6‚8‚14)、(6‚9‚15)、(6‚10‚12)、(6‚11‚13)、(7‚8‚15)、(7‚9‚14)、(7‚10‚13)、(7‚11‚12)7內湖高中數學營月曆的故事一個星期有七天—沿襲古代巴比倫文明的制度並以日月及五大行星金、木、水、火、土命名。現行月曆的沿革:一.一個回歸年約為365又1/4天(實際上是365.2422天),公元前46年,羅馬帝國凱撒制定曆法規定一年十二個月,單月31天、雙月為30天,但2月為29天,每4年加一個閏年,史稱朱曆。凱撒死後的繼承者奧古斯都將8月改成大月並將8月以後的大小月全部顛倒過來,2月再被扣一天變成28天,這就是我們現行所沿用的曆法。二.公元1582年的春分落在3月11日,當時的天主教教宗葛雷哥利十三世,重新制定曆法,一舉將十天刷掉並宣布當年的3月11日改為3月21日並且將閏年作了適當的調整,史稱葛曆。三.葛曆中規定,,若某一年的公元數被4整除,則為閏年,但如果被100整除,則必須也被400整除方為閏年,因此,每400年有97個閏年。練習:1.下列哪一年的月曆與1960年的月曆完全相同?(A)1991年(B)1900年(C)1980年(D)1968年(E)1988年2.下列哪一年的一月一日與十月一日的星期數不同?(A)1979年(B)1980年(C)1981年(D)1982年(E)1983年計算星期數:星期數Xm公元0年3月1日3公元0年4月1日68公元0年5月1日1公元0年6月1日4公元0年7月1日6公元0年8月1日2公元0年9月1日5公元0年10月1日0公元0年11月1日3公元0年12月1日5公元1年1月1日1公元1年2月1日4公式:y年x月d日的星期數為y+[y/4]-[y/100]+[y/400]+(d-1)+X被7除之餘數m練習:1.公元1971年5月11日星期幾?2.公元1623年2月15日星期幾?3.民國80年9月23日星期幾?4.民國74年1月16日星期幾?5.今年黑色星期五發生於幾月?6.公元2002年黑色星期五發生於