台北市立第一女子高級中學高一數學科專題講義

教材內容:整數論淺談                                         張澎雄老師

 

一、同餘數:

在介紹同餘數這個概念之前,讓我們先看一看下面這個例子.當任一整數被5除時,所得之餘數為何 ? 請看下圖

 

 由上圖可看出當任一整數被5除時,其餘數必為0,1,2,3,4五個整數中之一個,-3,2,7,12,17,

22,•••5除時皆餘2;-4,1,6,11,16,21,•••5除時皆餘1,所以定義同餘數:若兩整數a,b被一個正整數n除時,所得餘數相同(或n|a-b),則稱a,b為模數n之同餘數,以符號 (mod n)表之。若a,b不是模數n之同餘數(或n|a-b),則以符號  (mod n)表之.上例中-3,2,7,12, 17,22,•••都是模數5的同餘數。由上面說明可知:任一等差數列之任兩項均為模數公差的同餘數。在日常生活中也有同餘數的影子,例如任兩個星期一是模數7之同餘數。

  同餘數的基本性質:已知a,b,c,d,均為整數,m,n為正整數,

(1) 反身性:     (2) 對稱性: 
(3) 遞移性:

,則:

(4)   (5)    (6)    (7)

證明:

 

 

 

 

 往下我們引入一些可利用同餘數概念處理的例子.

1:已知一n位之自然數
試証:3(或9)之倍數為3(或9)之倍數

証明:


2:已知一n位之自然數,
試証:11之倍數 為11之倍數

証明:

 

 

 

 

3:已知一n位之自然數
試証:7之倍數為7之倍數

証明:

 

 

 

 

 

練習題:模仿上面三個例子,請找出一自然數13之倍數的充要條件 ?

    

 

 

 

 

4:在0至6這七個數中,那一個數與10´15´2320´13´18是模數7的同餘數?

:

 

 

 

 

5:在0至4這五個數中,那一個數與是模數5的同餘數 ?

:

 

 

 

 

6: 的展開式中,後三位數為何 ?

:

 

 

 

 

7:若一個四位數aabb為完全平方數,則aabb= ?

:

 

 

 

 

練習題:(1)試求 632596198763 除以45的餘數?
:


(2)在0至12這十三個數中,那一個數與3
´7´12´18´23´28´113是模數13的同餘數?

:

 

      

:

 

8:已知兩整數 4n13n1 均為完全平方數,試證:n為56的倍數

證明:

 

 

 

 

 

9:試求兩整數 之最大公因數?

:

 

 

 

 

練習題(4)試証:被8除於7的自然數,均不可表為3個整數的平方和

證明:

 

 

 

 

(5)試求兩整數  之最大公因數? 

:

 

10:已知兩整數a,b,一質數p,請證明

證明:

 

練習題:在例6中,若p不為質數,請問結果是否仍然成立 ?若不成立,請舉例說明之.

:

 

 

 

 

練習題:(同餘數之消去律)已知三整數a,b,c,一質數p,
,則

 

 

二、下面將介紹一些與同餘數相關之定理與應用:中國剩餘定理 尤拉函數 費馬小定理 畢氏數 今有一數,被3除,餘1;被5除,餘1;被7除,餘1,請問此數為何 ?”,“今有一數,被3除,不足1;被5除,不足1;被7除,不足1,請問此數為何 ?”上面之問題,相信同學們必能得心應手,但若換成下面這個問題,同學們可能要碰壁了.

   “今有一數,被3除,餘2;被5除,餘3;被7除,餘2,請問此數為何 ?”

   往下介紹一個處理此類問題的方法:中國剩餘定理

(1)中國剩餘定理:設為k個兩兩互質之正整數;為k個任意整數,則

                下列同餘方程組有解:

               

證明:

 

 

 

 

  中國算學古籍“孫子算經”書中,有這樣的一個題目:“今有物不知數,三三數之,賸二;五五數之,賸三;七七數之,賸二;問物為何 ?” 此問題即同學們剛才碰壁之問題,現解答如下:

:

 

:

 

 

 

 

練習題:1.七數剩一,八數剩二,九數剩三,問本數?            

:

 

 

 

2.十一數餘三,十二數餘二,十三數餘一,問本數?

:

 

 

 

 

3.二數餘一,五數餘二,七數餘三,九數餘四,問本數?(上三題摘自楊輝續古摘奇算法)

:

 

 

 

 

 

:

 

 

 

 

(2)尤拉函數:相信同學們在國中或高中曾經碰到這樣的題目:請求不大於540且與540互質的數有幾個 ?,當然540的質因數僅有2、3、5三個,所以以集合個數運算並不困難,但若是不大於1001000的且與1001000互質的數有幾個 ?,此時運算必定工程浩大,有的同學可能放棄或帶起死背的公式,而不知其所以然.往下我們將利用尤拉函數道出原委.

引理一:令(m)表示不大於m而與m互質的自然數的個數.若p為一質數,則(p)=p-1,(pn)=pn-pn-1.

證明:

 

 

 

引理二:已知m,aN,若(m,a)=1,則(m,km+a)=1;若(m,a)1,則(m,km+a)1,其中k.

證明:

 

 

 

引理三(積性性質):若m,nN且(m,n)=1,則(mn)=(m)(n).

證明:

 

 

 

 

證明:

 

 

 

 

  其次引入費馬小定理:十七世紀中,現代數論的創立者費馬所發現的.

(3)費馬小定理:設p是一質數,a是與p互質的一個非零整數,則

             (1)

             (2)若d是使得成立的最小自然數,則d∣p-1

證明:

 

 

 

利用費馬小定理因數分解

2:因數分解第四個費馬數F4=(凡是型如Fn =,n非負整數,之數者稱為費馬
數)

:

 

 

3:因數分解213-1=8191

:

 

 

 

 

練習題:(1)因數分解211-1=2047

:

 

 

 

(2)因數分解217-1=131071

:

 

 

 

(3)證明237-1不是質數.

:

 

 

 

  最後在介紹畢氏數之前,讓我們先看一看下面這個的例子

4:設m,n為整數,請證明

  (1)2mn, 兩數中至少有一個數為3的倍數

  (2)2mn, 兩數中至少有一個數為4的倍數

  (3)2mn, ,三數中至少有一個數為5的倍數

證明:

 

 

 

 

(4)畢氏數:所謂一組畢氏數(a,b,c)意指自然數a,b,c互質且構成一個直角三角形之三邊長

          (即a2+b2=c2)

定理:方程式x2+y2=z2的互質整數解(即(x,y,z)=1的整數解)均可表為

     其中m,n為互質的整數且一為奇數,一為偶數;而且x,y

兩數中至少有一個數為3的倍數;x,y兩數中至少有一個數為4的倍數;x,y,z三數中至少有一個數為5的倍數.

證明:

 

 

 

 

5:證明方程式無自然數解x,y,z.

證明:

 

 

 

 

 

練習題:(1)證明方程式無自然數解x,y,z.

:

 

 

 

 

(2)請利用上列定理找6組畢氏數.

:

 

 

 

 

 

(5)完全數(Euclid):若自然數 n 所有小於本身的正因數之和亦為 n,
則稱 n 為完全數(perfact number)

: 6=1+2+3 , 28=1+2+4+7+14 , 而下一個呢?是496……

 

證明:

 

 

 

 

 

證明: