前面已介紹過整除的概念和帶余除法

　　被除數(shù)=除數(shù)×商數(shù)+余數(shù)

　　在上面的式子里，若余數(shù)不為零，商叫做不完全商。

　　在生活中，人們也經(jīng)常關心“余數(shù)”，讓我們先看一個問題：

　　1993年6月1日是星期二，問20年后的6月1日是星期幾？

　　由于每年有365天，20年有20×365=7300天，但每四年有一個閏年，20年中有5個閏年，故20年有7305天。

　　7305=7×1043+4

　　說明20年中有1043周，外加4天，我們關心的其實不是20年中有多少周，而是“外加的4天”（換句話說，關心的不是商數(shù)而是余數(shù)，有了余數(shù)就可求得20年后的6月1日是星期幾）。因此，20年后的6月1日應該是星期六。

　　再看一個題目：

　　一個奇數(shù)去除288和510所得的兩個余數(shù)相同且為29，求這個奇數(shù)。

　　如果從被除數(shù)=除數(shù)×商數(shù)+余數(shù)這個式子出發(fā)，必有

　　被除數(shù)-余數(shù)=除數(shù)×商數(shù)

　　可以知道：288-29和510-29都是除數(shù)的倍數(shù)。即259和481都是除數(shù)的倍數(shù)，或除數(shù)是259和481的公約數(shù)。

　　用輾轉相除法求259和481的最大公約數(shù)。

　　481=259×1+222

　　259=222×1+37

　　222=37×6

　　故37是481和259的最大公約數(shù)，即37這個奇數(shù)恰為所求的除數(shù)。

　　驗證一下：288=37×7+29

　　510=37×13+29

　　知37確實是所求的奇數(shù)。

　　換一下角度考慮：由于288和510被同一奇數(shù)除所得的余數(shù)相同，那么510和288差就一定是這個奇數(shù)的倍數(shù)。（求差時，相同的余數(shù)被減掉了）

　　∵510-288=222=2×3×37

　　所求奇數(shù)為222的奇約數(shù)，只可能是37或111

　　但510=111×4+66

　　288=111×2+66

　　余數(shù)雖相同但并非29，故111不可能是所求的奇數(shù)，

　　510=37×13+29

　　288=37×7+29

　　故37為所求的奇數(shù)

　　象510和288這兩個數(shù)，被37除所得的余數(shù)相同，（都是29）我們稱510和288對于模37同余。

　　“對于模37同余”就是指被37除所得的余數(shù)相同，記為

　　510≡288（mod37）

　　這里mod37讀作“模37”，“≡”讀作“同余于”。

　　一般地，兩個整數(shù)a和b，除以一個大于1的自然數(shù)m所得的余數(shù)相同，就稱a和b對于模m同余或a和b在模m下同余，記為

　　a≡b（modm）

　　有時也可簡讀作a與b同余，這時只是未將模m讀出而已，很明顯一談到同余總與模有關容易看到，所有的偶數(shù)在模2下彼此同余，所有的奇數(shù)在模2下也彼此同余。

　　這里實際上是用2來將整數(shù)分成兩類，一類被2整除（余數(shù)為零），另一類被2除余1。

　　偶數(shù)0，2，4，6，8，……，2k，……

　　奇數(shù)1，3，5，7，9，……，2k+1，……

　　如果用4來將整數(shù)分類，由于余數(shù)可為0、1、2、3共四種，因而可分為四類：

　　0，4，8，12，16……

　　1，5，9，13，17……

　　2，6，10，14，18……

　　3，7，11，15，19……

　　同一行的兩個數(shù)，被4除的余數(shù)相同，也就是說在模4下同余，

　　如8≡16（mod4）5≡17（mod4）

　　2≡14（mod4）7≡15（mod4）

　　人們將一年的365天按星期日，星期一，星期二……星期六分為七類。

　　因此，對于每月的1號，8號，15號，22號，28號來說，1號是星期幾，共其它幾天也是星期幾。

　　我們說過可用模將全體整數(shù)分類。

　　被3除余1的所有數(shù)，可用1（mod3）表示，即1，4，7，10……這些數(shù)的全體，這些數(shù)在模6下卻分屬兩類，因為在模6下所有整數(shù)被分為下列六類：

　　0，6，12，18，……0（mod6）

　　1，7，13，19，……1（mod6）

　　2，8，14，20，……2（mod6）

　　3，9，5，21，……3（mod6）

　　4，10，16，22，……4（mod6）

　　5，11，17，23，……5（mod6）

　　1（mod3）表示1（mod6）和4（mod6）兩類

　　被2除余1的數(shù)1（mod2），在模6下卻分屬三類，即1（mod6），3（mod6），5（mod6）

性質1任何整數(shù)都和自己同余，（這條性質稱為自反性）a≡a（modn）。

性質2甲、乙二整數(shù)，如果甲和乙同余，那么乙和甲也同余。（這條稱為對稱性）

　　若a≡b（modm）現(xiàn)b≡a（modm）。

性質3甲，乙，丙三個整數(shù)，如甲和乙同余，乙和丙同余，那么甲和丙一定同余。（這條稱為傳遞性）

　　若a≡b（modm），b≡c（modm），則a≡c（modm）。

性質4甲和乙同余，丙和丁同余，那么甲與丙的和與乙和丁的和一定同余。（這條稱為可加性）。甲與丙的差與乙和丁的差一定同余。（這條稱為可減性）。甲與丙的積與乙和丁面積一是同余。（這條稱為可乘性）。

　　若a≡b（modm）c≡d（modm）

　　則a+c≡b+d（modm）

　　a-c≡b-d（modm）

　　a×c≡b×d（modm）

　　特別是當a≡b（modm），c=d對，有

　　a+c≡b+c（modm）

　　a-c≡b-c（modm）

　　ac≡bc（modm）

性質5甲和乙同余，那么甲和乙同次乘方的結果仍然同余。（這條稱為可乘方性，實際上是可乘性反復運用的結果）

　　若a≡b（modm），n為自然數(shù)

　　以上各條性質和等式的性質十分相似，不過同余式終究不是等式，并不是等式的各種性質都能移到同余式中來使用。

　　注意，同余式中不能隨意使用“可除性”。即在同余式ac≡be（modm）兩端，如同除以c之后可能不同余。

　　如10≡6（mod4）

　　即5×2≡3×2（mod4）

　　但53（mod4）

　　又如16≡2（mod7）

　　即8×2≡1×2（mod7）

　　卻有8≡1（mod4）

　　可見在ac≡be（mod4）兩端同除以C后，可能有a≡b（modm）也可能ab（modm），這取決于c與m之間的關系。

　　結論是：如果（c，m）=1，有a≡b（modm），如（c，m）≠1，就可能有ab（modm）

例1求437×309×1993被7除的余數(shù)

　　分析：如將437×309×1993算出后，再用7去除從而求得余數(shù)，這顯然是可以的，但是數(shù)字較大，比較麻煩，（實際上437×309×1993=269120769，被7除的余數(shù)為1）。

　　可將437，309，1993分別被7除求出余數(shù)，再用同余式性質將余數(shù)相乘即可容易得出原數(shù)被7除的余數(shù)。

解：∵437≡3（mod7）

　　 309≡1（mod7）

　　1993≡5（mod7）

　　利用同余式的可乘性，將三式相乘得

　　437×309×1993≡3×1×5（mod7）

　　≡15（mod7）≡1（mod7）

　　即437×309×1993被7除余1

例2 70個數(shù)排成一行，除了兩頭的兩個數(shù)以外，每個數(shù)的三倍恰好等于它兩邊兩個數(shù)的和，這一行數(shù)最左邊的幾個數(shù)是這樣的：0，1，3，8，21……，問這一行數(shù)最右邊的一個數(shù)被6除的余數(shù)是幾？

分析 如果將這70個數(shù)都寫出，再用6去除最右邊的數(shù)當然可以，但工作量相當大。

　　本題中并未要求算出最右邊的那個數(shù)，僅要求這個數(shù)被6除的余數(shù)。

　　根據(jù)這70個數(shù)組成的規(guī)律：中間的一個數(shù)的3倍是它兩邊的數(shù)的和。（兩頭的兩個數(shù)除外）

　　那么中間那個數(shù)被6除的余數(shù)的3倍與兩邊兩數(shù)被6除的余數(shù)之和再被6除的余數(shù)應該相同，（在模6下同余）

　　將0，1，3，8，21，55……，被6除的余數(shù)依次寫出為0，1，3，2，3，1，……

　　仔細觀察這串余數(shù)，中間的數(shù)的3倍與兩邊二數(shù)之和在模6下同余（被6除的余數(shù)相同）。因此，用70個數(shù)中每個數(shù)被6除的余數(shù)組成的新數(shù)串來代替原數(shù)串，不會影響題目的要求（求最右邊的數(shù)被6除的余數(shù)）?，F(xiàn)在變?yōu)榍笮碌臄?shù)串中最右的數(shù)了。

　　寫新數(shù)串的工作量比原來小多了。讓我們觀察新數(shù)串是否有一定規(guī)律，如能找到規(guī)律還可進一步減少工作量。

　　將新數(shù)串（被6除的余數(shù)串）多寫幾個數(shù)試試看：

　　0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，……

　　可以看出前12個數(shù)一段，將重復出現(xiàn)。

　　70個數(shù)的前5段共60個數(shù)，第六段的第十個數(shù)為4，這就是原來數(shù)串中第70個數(shù)被6除的余數(shù)。

例3 求被7除的余數(shù)

分析：由于這個數(shù)字太大，真正除工作量太大，不過可以試一試是否有某種規(guī)律。

　　經(jīng)過試除發(fā)現(xiàn)111111可被7整除，這樣可將被除數(shù)從最高位開始六位一段，由于共有1993個1，即有1993位。

　　1993=6×332+1

　　最后剩下的一位上的1，恰好是原數(shù)被7除的余數(shù)。

　　故被7除余數(shù)為1

　　（商為158730158730……158730。由332個158730連寫組成）

　　如知道1001是7的倍數(shù)，那么

　　111111=100100+10010+1001

　　右端的3個數(shù)均為7的倍數(shù)，所以111111也是7的倍數(shù)。

　　再象上面那樣，將從左往右六位一段，最后剩下1，被7除仍余1。

　　如將除數(shù)7改為6， 被6除的余數(shù)是多少？

　　作除法試試看

　　即除第一個1外每3位一段，1111111被6除余1，

　　1993-1=3×664

　　在商式上將出現(xiàn)185連寫664次，在商中最后一個5的位置所對的1恰好為余數(shù)，因此

被6除余1。

　　改換一種考慮辦法，由于6=2×3，可知原數(shù)數(shù)字和是1993個1之和為1993，而1993被3除余1。

　　即被3整除，而也被2整除，因此被6整除。

　　=+1

　　故被6除余1。

　　在進行計算時，要求準確無誤，可是當數(shù)字較大或運算復雜時，容易出現(xiàn)錯誤，這就要求我們有較簡便的辦法判斷是否出錯，如能迅速認定計算有誤將便于改正。

　　如4278×39682=169759894這個式子一看便知不正確，因為從末位數(shù)字8與2相乘，末位不可能是4，這種辦法稱為末位檢驗法。

　　但如改為4278×39682=169759896，從末位看不出問題，不敢確定計算有無錯誤。

　　在“同余的幾條簡單性質”的例1中，我們曾計算三個數(shù)的乘積被7除的余數(shù)，若改為計算乘積437×309×1993被9除的余數(shù)，根據(jù)同余的性質可分別計算437、309、1993，再求三個余數(shù)之積被9除的數(shù)即可

　　∵437≡（4+3+7）（mod9）≡5（mod9）

　　 309≡（3+9+0+）（mod9）≡3（mod9）

　　1993≡（1+9+9+3）（mod9）≡4（mod9）

　　∴437×309×1993≡5×3×4（mod9）

　　 ≡6（mod9）

　　故知437×309×1993被9除余6

　　由于求被9除的余數(shù)，只需計算數(shù)字和被9除的余數(shù)，因而可用被9除的余數(shù)來檢驗計算的錯誤。

　　如4278×39682=169759896，從末位看不出問題，若計算是正確的，那么兩端被9除的余數(shù)應相同。若兩端被9除余數(shù)不同，那么計算肯定有錯。

　　由 4278≡3（mod9）

　　39682≡1（mod9）

　　有 4278×39682≡3（mod9）

　　但 169759896≡6（mod9）

　　∴4278×39682≠169759896

　　以上辦法稱為棄九法。不過應該注意，用棄九法可發(fā)現(xiàn)錯誤，但用棄九法沒找出錯誤卻不能保證原題一定正確。

　　如下列算式明顯有錯誤，但用棄九法卻未能發(fā)現(xiàn)。

　　1278×17384=216387

　　∵ 1278≡0（mod9）

　　17384≡5（mod9）

　　1278×17384≡0×5≡0（mod9）

　　而 216387≡0（mod9）

　　但從末位可見1278×17384≠216387，這就是說棄九法未發(fā)現(xiàn)問題，不能認為計算一定正確，（其實一個四位數(shù)乘以一個五位數(shù)不可能得到一個六位數(shù)）

　　對于除法算式轉化為乘法即可檢驗。

　　如 465187586÷9762=47653是否正確？可轉化為9762×47653=46518786是否正確？

　　從末位數(shù)字看，找不出問題。從被乘數(shù)的位數(shù)（四位），乘數(shù)的位數(shù)（五位）、積的位數(shù)（九位）看也找不出問題。

　　棄九法檢查

　　9762≡6（mod9）

　　47653≡7（mod9）

　　9762×47653≡6×7≡42≡6（mod9）

　　但 465187586≡5（mod9）

　　∴ 9762×47653≠465187586

　　故 465187586÷9762≠47653

　　棄九法一般都用在整數(shù)范圍內，對于小數(shù)運算可將小數(shù)先“當作”整數(shù)，方可使用棄九法。

　　如 0.12345×0.9876=0.12191820是否正確？只需看12345×9876=12191820是否正確，即直接去掉小數(shù)點，檢查數(shù)字計算是否正確，再考察小數(shù)點位置是否正確。

　　1.求16×941×1611被7除的余數(shù)。

　　*2.求被41除所得的余數(shù)

　　3.用棄九法檢驗乘積

　　5483×9117=49888511

　　是否可能正確。

　　4.用棄九法檢驗商

　　1226452÷2683=334

　　是否可能正確。

　　5.乘法算式

　　3145×92653=2910____93995

　　的橫線處漏寫了一個數(shù)字，你能以最快的辦法補出嗎？

　　6.13511，13903，14589被自然數(shù)m除所得數(shù)相同，問m最大值是多少？

　　8.將奇數(shù)按下列圖排好，各列分別用A、B、C、D、E、F、G作為代表，問1993所在的列以哪個字母作為代表？

　　A B C D E F G

　　1 3 5 7 9 11

　　23 21 19 17 15 13

　　25 27 29 31 33 35

　　47 45 43 41 39 37

　　49 51 53 55 57 59

　　……………………

　　*10.形如8k+7的數(shù)不能表為三個平方數(shù)的和。