同餘數

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

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

一、同餘數：

在介紹同餘數這個概念之前,讓我們先看一看下面這個例子.當任一整數被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:已知兩整數 4n＋1，3n＋1 均為完全平方數，試證：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互質的數有幾個 ?”,此時運算必定工程浩大,有的同學可能放棄或帶起死背的公式,而不知其所以然.往下我們將利用尤拉函數道出原委.