這篇關(guān)于初中奧數(shù)數(shù)論基礎(chǔ)知識精編，是特地為大家整理的，希望對大家有所幫助！
第1章 整 除
在日常生活中，我們會過到許多有趣而又耐人尋味的問題：
某同學(xué)到文具店買了七個一角二分錢的本子、五個六分錢的鉛筆和三個活頁夾子。售貨員收了他三元錢，并找還三角七分錢。這個同學(xué)馬上對售貨員說：“您的賬算錯了！”你能知道他為什么這樣快就知道“算錯了賬”嗎？
排練團(tuán)體操時，要求隊伍變成10行、15行、18行、24行時，隊形都能成為矩形，問最少需要多少人參加團(tuán)體操的排練？
§1.1 十進(jìn)制整數(shù)
在小學(xué)數(shù)學(xué)中，我們主要學(xué)習(xí)的是整數(shù)的運算，思考整數(shù)是怎樣表示的？“逢十進(jìn)一”是什么意思？
我們通常接觸到整數(shù)都是十進(jìn)制的整數(shù)。十進(jìn)制計數(shù)法就是采取逢十進(jìn)一的法則進(jìn)行計數(shù)的方法。例如，1995就是由1個一千，9個一百，9個十和1個五組成，因此1995這個數(shù)就可以寫成
1995=1×1000+9×100+9×10+5. 那么對于任意一個n+1位的正整數(shù)怎樣用這種形式表示？
為了表示方便，我們經(jīng)常把用字母表示數(shù)字的多位數(shù)，在這個多位數(shù)上面加一個橫線，以避免和乘法混淆，例如，37a56就表示一個五位數(shù)。
§1.2 數(shù)的整除
設(shè)有兩個整數(shù)a，b（b≠0），若有另一整數(shù)q，使得a=b×q，則稱a被b整除；或b能整除a；若a被b整除，也成a是b的倍數(shù)；b是a的約數(shù)，并記作b|a.若a不能被b整除，則記作b∤a.
我們曾經(jīng)學(xué)過下述有關(guān)整除的判別法則：
1、被2或5整除的數(shù)的特征是末位數(shù)字能被2或5整除；
2、被4或25整除的數(shù)的特征是末兩位數(shù)字能被4或25整除；
3、被8或125整除的數(shù)字的特征是末三位數(shù)字能被8或125整除；
4、被3或9整除的數(shù)的特征是個位數(shù)字的和能被3或9整除；
5、被11整除的數(shù)的特征是其奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差能被
11整除；
解題過程中我們常用的性質(zhì)：
1、若a b，b c，則a|c；
2、若a b，a c，則a| b±c ；
3、若a b，則a nb n是正整數(shù) ；
4、若a、b互質(zhì)，且a bc，則a c；
5、若a、b互質(zhì)，且a c，b c，則ab|c；
6、n個連續(xù)整數(shù)中，必有一個能被n整除；
§1.3~1.4 奇數(shù)和偶數(shù)
把全體整數(shù)分成奇數(shù)類和偶數(shù)類是一種最常用的分類方法；
奇數(shù)就是通常所述的單數(shù)，偶數(shù)就是通常所說的雙數(shù)；
一般的，一個整數(shù)如果能被2整除就叫做偶數(shù)，如果不能被2整除（即被2除余1）就叫做奇數(shù)；
偶數(shù)可以記作2n，奇數(shù)可以記作2n-1或2n+1（n為整數(shù)）；
奇數(shù)和偶數(shù)有一些十分簡單又明顯的性質(zhì)：
1、奇數(shù)不等于偶數(shù)；
2、奇數(shù)±奇數(shù)=偶數(shù)，偶數(shù)±偶數(shù)=偶數(shù)，奇數(shù)±偶數(shù)=奇數(shù)；
3、奇數(shù)個奇數(shù)的和是奇數(shù)，偶數(shù)個奇數(shù)的和是偶數(shù)，任意多個偶數(shù)的和都
是偶數(shù)；
4、奇數(shù)×奇數(shù)=奇數(shù)，偶數(shù)×整數(shù)=偶數(shù)，偶數(shù)×偶數(shù)=4的倍數(shù)；
5、兩個整數(shù)的和與這兩個整數(shù)的差具有相同的奇偶性；
6、奇數(shù)的平方為4k+1型的數(shù)，偶數(shù)的平方為4k型的數(shù)（k為整數(shù)）；
7、任意兩個整數(shù)的平方和被4除一定不余3；
8、任意兩個整數(shù)的平方差被4除一定不余2；
§1.5 質(zhì)數(shù)與合數(shù)
對于正整數(shù)可以依照它們的正約數(shù)的個數(shù)分為三類：一類是只有一個正約數(shù)的數(shù)，它就是1；一類是只有兩個正約數(shù)的數(shù)，這兩個正約數(shù)只能是1和它本身，例如5,7,11，這樣的數(shù)叫做質(zhì)數(shù)（也叫做素數(shù)）；第三類是有兩個以上的正約數(shù)的數(shù)，例如6就有4個正約數(shù)：1,2,3,6，這樣的數(shù)叫做合數(shù)。因此，正整數(shù)是由1，質(zhì)數(shù)，合數(shù)三部分組成的。
關(guān)于質(zhì)數(shù)、合數(shù)有下列性質(zhì)：
1、質(zhì)數(shù)有無限多個；
2、除2以外的全體質(zhì)數(shù)都是正奇數(shù)，除2以外的全體正偶數(shù)都是合數(shù)；
3、大于1的整數(shù)的所有約數(shù)中，1以外的最小正約數(shù)一定是質(zhì)數(shù)；
4、如果a是合數(shù)，那么a的最小質(zhì)因數(shù)一定不大于
§1.6 算術(shù)基本定理
每一個合數(shù)都可以寫成幾個質(zhì)數(shù)相乘的形式，這幾個質(zhì)數(shù)叫做這個合數(shù)的質(zhì)因數(shù)。
把一個合數(shù)用質(zhì)因數(shù)的連乘的形式來表示，叫做分解質(zhì)因數(shù)。分解質(zhì)因數(shù)有下面一個重要的定理：
算術(shù)基本定理：任何一個正整數(shù)N>1，都能分解成質(zhì)因數(shù)的連乘積，即：
𝛂𝟏𝛂𝟐𝛂𝐧𝐍=𝐏𝟏∙𝐏𝟐∙⋯∙𝐏𝐧，（n≥1）
其中p1，p2，⋯，pn為互不相等的質(zhì)數(shù)，α1，α2，⋯，αn是正整數(shù)；如果不考慮順序，則這個分解式是的。
§1.7 公約數(shù)與最小公倍數(shù)
對于4、8、12這一組數(shù)，顯然1、2、4都能整除它們中的每一個數(shù)，所以1、2、4都是它們的公約數(shù)，其中4是這些公約數(shù)中的的。把這個概念推廣到一般情形，有如下定義：
如果a1，a2，⋯，an和d都是正整數(shù)，且d|a1，d|a2，⋯，d|an，那么d叫做a1，a2，⋯，an的公約數(shù)。公約數(shù)中的叫做a1，a2，⋯，an的公約數(shù)，記作（a1，a2，⋯，an）。
當(dāng)（a，b）=1時，我們稱a，b互質(zhì)
a1，a2，⋯，an的公約數(shù)（a1，a2，⋯，an）表示的是一個正數(shù)，是一個能夠整除a1，a2，⋯，an并且能被a1，a2，⋯，an的每一個約數(shù)整除的數(shù)；
常用的有關(guān)約數(shù)的性質(zhì)有：
1、若a|b，則（a，b）=a；
2、若（a，b）=d，且n是正整數(shù)，則（na，nb）=nd；
3、若n|a，n|b，則（a/n，b/n）=（a，b）/n；
其中，性質(zhì)3表明，若（a，b）=d，則（a/d，b/d）=1；
4、若a=bq + r（0≤r<𝑏），則（a，b）=（b，r）；
對于4、8、12這一組數(shù)，24、48和72等都能被它們中的每一個數(shù)整除，24、48和72都叫他們的公倍數(shù)，而24是公倍數(shù)中最小的，把這個概念推廣到一般形式，有如下的定義：
如果a1，a2，⋯，an和m都是正整數(shù)，且a1|m，a2|m，⋯，an|m，那么m叫做a1，a2，⋯，an的公倍數(shù)。公倍數(shù)中最小的數(shù)叫做a1，a2，⋯，an的最小公倍數(shù)，記作[a1，a2，⋯，an]。
5、若b|a，則[a，b]=a；
6、若[a，b]=m，且n為正整數(shù)，則[na，nb]=mn；
7、若n|a，n|b，則[a/n，b/n]=[a，b]/n；
8、若[a，b]=m，則（m/a，m/b）=1；
9、（a，b）=ab/[a，b]；
第2章 同余
我們在解決一些有關(guān)整數(shù)的問題時，并不關(guān)心具體的數(shù)字是多少，而是關(guān)心被某個整數(shù)所除而得到的余數(shù)是多少。例如，2004年的元旦是星期四，2005年的元旦時星期幾？因為2004年全年共有366天，而366除以7的余數(shù)是2，所以2005念得元旦是星期六，再如，今天是星期六，101010天后是星期幾？這也是同余的問題；
我國古代對同于問題有比較深入的研究，其中比較的有《孫子算經(jīng)》中的“物不知數(shù)”問題，秦九韶的“大衍求一術(shù)”的解同余方程的方法，以及中國剩余定理。其實，有關(guān)同余的記載最早的是“韓信點兵”的故事。據(jù)說韓信在點兵的時候，為了軍事保密，不讓敵人知道自己的兵力，先讓士兵從1到3報數(shù)，然后記住最后一個士兵所報的數(shù)；再讓士兵從1到5報數(shù)，也記住最后一個士兵所報的數(shù)；最后讓士兵從1到7報數(shù)報數(shù)，又記下最后一個士兵所報的數(shù)。這樣，他很快算出了自己士兵的總?cè)藬?shù)，而敵人卻無法弄清他的兵力，這都是利用同余方程解決的。
然而，創(chuàng)立同余論的并不是我國古代的數(shù)學(xué)家，而是大數(shù)學(xué)家高斯，高斯最早使用了“同余”的概念，并創(chuàng)立了同余理論。下面我們就同余論做一個簡單的介紹。
§2.1 同余的概念和性質(zhì)
顧名思義，同于就是余數(shù)相同，是指被一個正整數(shù)所除，得到的余數(shù)相同。 定義：設(shè)a、b是兩個整數(shù)，如果a和b被正整數(shù)m除所得余數(shù)相同，則稱a與b對于模m同余，記作：
𝑎≡𝑏（mod 𝑚），
否則，就稱a與b對于模m不同余，記作𝑎≢𝑏（mod 𝑚）。
根據(jù)定義，a與b是否同于，不僅與a、b有關(guān)，還與模m有關(guān)，對一對數(shù)a和b，對于模m同余，而對于模n也許就不同余。根據(jù)同余的定義，顯然有以下幾種關(guān)系是成立的：
（1） 𝑎≡𝑎（mod 𝑚）；
（2） 𝑎≡𝑏（mod 𝑚）⟺𝑏≡𝑎（mod 𝑚）；
𝑎≡𝑏（mod 𝑚）（3） 𝑏≡𝑐（mod 𝑚） 𝑎≡𝑐（mod 𝑚）；
由此可見，同余是一種等價關(guān)系，以上這三條分別叫做同余的反身性，對稱性和傳遞性，而等式也具有這幾條性質(zhì)。
§2.2 剩余類與完全平方數(shù)
一、剩余類
一個整數(shù)被2除時，余數(shù)只能是0或1兩種可能，因此可以把所有的整數(shù)按照被2除的余數(shù)分成兩類，一類是被2除余數(shù)為0，另一類是被2除余數(shù)為1。也就是我們常說的偶數(shù)和奇數(shù)。同樣的道理，一個整數(shù)被3除時，余數(shù)只能是0、1、2這三種可能的某一種，因此所有的整數(shù)按照被3除可以分成余數(shù)為0、1、2三類。
一般地，任何一個整數(shù)。被一個非零的整數(shù)m除，可以得到商q和余數(shù)r，即a=mq+r。這里的r只能取O,l,2,„,m-1這m個值。
全體整數(shù)可按對模m是否同余分為若干個兩兩不相交的集合，使得在同一個集合申的任意兩個數(shù)對模m一定同余，而屬于不同集合中的兩個數(shù)對模m一定不同余。每下個這樣的集合稱為模m的同余類，或模m的剩余類。由模m的每個同余類中取定一個數(shù)作為代表構(gòu)成一組數(shù)，這組數(shù)就稱為模m的一個完全剩余系。 根據(jù)剩余類的概念，很容易得到以下幾條有關(guān)剩余類的性質(zhì)：
1、每一個整數(shù)一定包括在而且僅包含在模m的一個剩余類中；
2、整數(shù)p所屬的模m的剩余類中的每一個數(shù)都可以寫成km+p的形式，這里
k是整數(shù)；
3、整數(shù)p、q在模m的同一個剩余類中的充要條件是p、q對模m同余。
實際上，同余式就是剩余類等式的一個特殊情況，是集合中一個元素，前面有關(guān)同余的一些性質(zhì)對剩余類仍然成立。
4、在任意取定的m+1個整數(shù)中，必有兩個整數(shù)對模m同余；
根據(jù)同余式的性質(zhì)，我們很容易得到剩余系的其他一些性質(zhì)：
5、m個整數(shù)a1，a2，⋯，am是模m的一組完全剩余系的充要條件是
a1，a2，⋯，am中的任意兩個數(shù)對模m都不同余；
6、如果a1，a2，⋯，am是模m的一組完全剩余系，那么對任意的整數(shù)
c，c+a1，c+a2，⋯，c+am也是模m的一組完全剩余系；
二、完全平方數(shù)
若a為整數(shù)，則a2叫做完全平方數(shù)。例如1、4、9、16„„等，下面我們利用同余式來研究完全平方數(shù)。
完全平方數(shù)的個位數(shù)字只能是0、1、4、5、6、9；
具有一下性質(zhì)的數(shù)一定是非完全平方數(shù)：
（1） 個位數(shù)字是2、3、7、8的數(shù)；
（2） 𝑎≡2（mod 3）；
（3） 𝑎≡2,3（mod 4）；
（4） 𝑎≡2,3（mod 5）；
（5） 𝑎≡2,3,5,6,7（mod 8）；
§2.3 簡單的同余方程
《孫子算經(jīng)》中的“物不知數(shù)”問題開創(chuàng)了一次同余式研究的先河，但遺憾的是沒有上升到一套完整的計算程序和理論高度。南宋時期的數(shù)學(xué)家秦九韶在他的《數(shù)學(xué)九章》中提出了“大衍求一術(shù)”的算術(shù)方法，比較系統(tǒng)的論述一次同余方程組的解法的一般原理和一般程序。他的計算程序的核心是求一個數(shù)的多少倍除以另一個數(shù)所得的余數(shù)為1。
對于n次整系數(shù)多項式
𝑓 𝑥 =𝑎𝑛𝑥𝑛+𝑎𝑛−1𝑥𝑛−1+⋯+𝑎1𝑥+𝑎0
𝑓 𝑥 ≡0（mod 𝑚）叫做模m的同余方程。是同余方程成立的x的值叫做同余方程的解。顯然，若x=c是同余方程𝑓 𝑥 ≡0（mod 𝑚）的一個解，則剩余類c mod m中的每一個數(shù)都是這個方程的解。
第1章 整 除
在日常生活中，我們會過到許多有趣而又耐人尋味的問題：
某同學(xué)到文具店買了七個一角二分錢的本子、五個六分錢的鉛筆和三個活頁夾子。售貨員收了他三元錢，并找還三角七分錢。這個同學(xué)馬上對售貨員說：“您的賬算錯了！”你能知道他為什么這樣快就知道“算錯了賬”嗎？
排練團(tuán)體操時，要求隊伍變成10行、15行、18行、24行時，隊形都能成為矩形，問最少需要多少人參加團(tuán)體操的排練？
§1.1 十進(jìn)制整數(shù)
在小學(xué)數(shù)學(xué)中，我們主要學(xué)習(xí)的是整數(shù)的運算，思考整數(shù)是怎樣表示的？“逢十進(jìn)一”是什么意思？
我們通常接觸到整數(shù)都是十進(jìn)制的整數(shù)。十進(jìn)制計數(shù)法就是采取逢十進(jìn)一的法則進(jìn)行計數(shù)的方法。例如，1995就是由1個一千，9個一百，9個十和1個五組成，因此1995這個數(shù)就可以寫成
1995=1×1000+9×100+9×10+5. 那么對于任意一個n+1位的正整數(shù)怎樣用這種形式表示？
為了表示方便，我們經(jīng)常把用字母表示數(shù)字的多位數(shù)，在這個多位數(shù)上面加一個橫線，以避免和乘法混淆，例如，37a56就表示一個五位數(shù)。
§1.2 數(shù)的整除
設(shè)有兩個整數(shù)a，b（b≠0），若有另一整數(shù)q，使得a=b×q，則稱a被b整除；或b能整除a；若a被b整除，也成a是b的倍數(shù)；b是a的約數(shù)，并記作b|a.若a不能被b整除，則記作b∤a.
我們曾經(jīng)學(xué)過下述有關(guān)整除的判別法則：
1、被2或5整除的數(shù)的特征是末位數(shù)字能被2或5整除；
2、被4或25整除的數(shù)的特征是末兩位數(shù)字能被4或25整除；
3、被8或125整除的數(shù)字的特征是末三位數(shù)字能被8或125整除；
4、被3或9整除的數(shù)的特征是個位數(shù)字的和能被3或9整除；
5、被11整除的數(shù)的特征是其奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差能被
11整除；
解題過程中我們常用的性質(zhì)：
1、若a b，b c，則a|c；
2、若a b，a c，則a| b±c ；
3、若a b，則a nb n是正整數(shù) ；
4、若a、b互質(zhì)，且a bc，則a c；
5、若a、b互質(zhì)，且a c，b c，則ab|c；
6、n個連續(xù)整數(shù)中，必有一個能被n整除；
§1.3~1.4 奇數(shù)和偶數(shù)
把全體整數(shù)分成奇數(shù)類和偶數(shù)類是一種最常用的分類方法；
奇數(shù)就是通常所述的單數(shù)，偶數(shù)就是通常所說的雙數(shù)；
一般的，一個整數(shù)如果能被2整除就叫做偶數(shù)，如果不能被2整除（即被2除余1）就叫做奇數(shù)；
偶數(shù)可以記作2n，奇數(shù)可以記作2n-1或2n+1（n為整數(shù)）；
奇數(shù)和偶數(shù)有一些十分簡單又明顯的性質(zhì)：
1、奇數(shù)不等于偶數(shù)；
2、奇數(shù)±奇數(shù)=偶數(shù)，偶數(shù)±偶數(shù)=偶數(shù)，奇數(shù)±偶數(shù)=奇數(shù)；
3、奇數(shù)個奇數(shù)的和是奇數(shù)，偶數(shù)個奇數(shù)的和是偶數(shù)，任意多個偶數(shù)的和都
是偶數(shù)；
4、奇數(shù)×奇數(shù)=奇數(shù)，偶數(shù)×整數(shù)=偶數(shù)，偶數(shù)×偶數(shù)=4的倍數(shù)；
5、兩個整數(shù)的和與這兩個整數(shù)的差具有相同的奇偶性；
6、奇數(shù)的平方為4k+1型的數(shù)，偶數(shù)的平方為4k型的數(shù)（k為整數(shù)）；
7、任意兩個整數(shù)的平方和被4除一定不余3；
8、任意兩個整數(shù)的平方差被4除一定不余2；
§1.5 質(zhì)數(shù)與合數(shù)
對于正整數(shù)可以依照它們的正約數(shù)的個數(shù)分為三類：一類是只有一個正約數(shù)的數(shù)，它就是1；一類是只有兩個正約數(shù)的數(shù)，這兩個正約數(shù)只能是1和它本身，例如5,7,11，這樣的數(shù)叫做質(zhì)數(shù)（也叫做素數(shù)）；第三類是有兩個以上的正約數(shù)的數(shù)，例如6就有4個正約數(shù)：1,2,3,6，這樣的數(shù)叫做合數(shù)。因此，正整數(shù)是由1，質(zhì)數(shù)，合數(shù)三部分組成的。
關(guān)于質(zhì)數(shù)、合數(shù)有下列性質(zhì)：
1、質(zhì)數(shù)有無限多個；
2、除2以外的全體質(zhì)數(shù)都是正奇數(shù)，除2以外的全體正偶數(shù)都是合數(shù)；
3、大于1的整數(shù)的所有約數(shù)中，1以外的最小正約數(shù)一定是質(zhì)數(shù)；
4、如果a是合數(shù)，那么a的最小質(zhì)因數(shù)一定不大于
§1.6 算術(shù)基本定理
每一個合數(shù)都可以寫成幾個質(zhì)數(shù)相乘的形式，這幾個質(zhì)數(shù)叫做這個合數(shù)的質(zhì)因數(shù)。
把一個合數(shù)用質(zhì)因數(shù)的連乘的形式來表示，叫做分解質(zhì)因數(shù)。分解質(zhì)因數(shù)有下面一個重要的定理：
算術(shù)基本定理：任何一個正整數(shù)N>1，都能分解成質(zhì)因數(shù)的連乘積，即：
𝛂𝟏𝛂𝟐𝛂𝐧𝐍=𝐏𝟏∙𝐏𝟐∙⋯∙𝐏𝐧，（n≥1）
其中p1，p2，⋯，pn為互不相等的質(zhì)數(shù)，α1，α2，⋯，αn是正整數(shù)；如果不考慮順序，則這個分解式是的。
§1.7 公約數(shù)與最小公倍數(shù)
對于4、8、12這一組數(shù)，顯然1、2、4都能整除它們中的每一個數(shù)，所以1、2、4都是它們的公約數(shù)，其中4是這些公約數(shù)中的的。把這個概念推廣到一般情形，有如下定義：
如果a1，a2，⋯，an和d都是正整數(shù)，且d|a1，d|a2，⋯，d|an，那么d叫做a1，a2，⋯，an的公約數(shù)。公約數(shù)中的叫做a1，a2，⋯，an的公約數(shù)，記作（a1，a2，⋯，an）。
當(dāng)（a，b）=1時，我們稱a，b互質(zhì)
a1，a2，⋯，an的公約數(shù)（a1，a2，⋯，an）表示的是一個正數(shù)，是一個能夠整除a1，a2，⋯，an并且能被a1，a2，⋯，an的每一個約數(shù)整除的數(shù)；
常用的有關(guān)約數(shù)的性質(zhì)有：
1、若a|b，則（a，b）=a；
2、若（a，b）=d，且n是正整數(shù)，則（na，nb）=nd；
3、若n|a，n|b，則（a/n，b/n）=（a，b）/n；
其中，性質(zhì)3表明，若（a，b）=d，則（a/d，b/d）=1；
4、若a=bq + r（0≤r<𝑏），則（a，b）=（b，r）；
對于4、8、12這一組數(shù)，24、48和72等都能被它們中的每一個數(shù)整除，24、48和72都叫他們的公倍數(shù)，而24是公倍數(shù)中最小的，把這個概念推廣到一般形式，有如下的定義：
如果a1，a2，⋯，an和m都是正整數(shù)，且a1|m，a2|m，⋯，an|m，那么m叫做a1，a2，⋯，an的公倍數(shù)。公倍數(shù)中最小的數(shù)叫做a1，a2，⋯，an的最小公倍數(shù)，記作[a1，a2，⋯，an]。
5、若b|a，則[a，b]=a；
6、若[a，b]=m，且n為正整數(shù)，則[na，nb]=mn；
7、若n|a，n|b，則[a/n，b/n]=[a，b]/n；
8、若[a，b]=m，則（m/a，m/b）=1；
9、（a，b）=ab/[a，b]；
第2章 同余
我們在解決一些有關(guān)整數(shù)的問題時，并不關(guān)心具體的數(shù)字是多少，而是關(guān)心被某個整數(shù)所除而得到的余數(shù)是多少。例如，2004年的元旦是星期四，2005年的元旦時星期幾？因為2004年全年共有366天，而366除以7的余數(shù)是2，所以2005念得元旦是星期六，再如，今天是星期六，101010天后是星期幾？這也是同余的問題；
我國古代對同于問題有比較深入的研究，其中比較的有《孫子算經(jīng)》中的“物不知數(shù)”問題，秦九韶的“大衍求一術(shù)”的解同余方程的方法，以及中國剩余定理。其實，有關(guān)同余的記載最早的是“韓信點兵”的故事。據(jù)說韓信在點兵的時候，為了軍事保密，不讓敵人知道自己的兵力，先讓士兵從1到3報數(shù)，然后記住最后一個士兵所報的數(shù)；再讓士兵從1到5報數(shù)，也記住最后一個士兵所報的數(shù)；最后讓士兵從1到7報數(shù)報數(shù)，又記下最后一個士兵所報的數(shù)。這樣，他很快算出了自己士兵的總?cè)藬?shù)，而敵人卻無法弄清他的兵力，這都是利用同余方程解決的。
然而，創(chuàng)立同余論的并不是我國古代的數(shù)學(xué)家，而是大數(shù)學(xué)家高斯，高斯最早使用了“同余”的概念，并創(chuàng)立了同余理論。下面我們就同余論做一個簡單的介紹。
§2.1 同余的概念和性質(zhì)
顧名思義，同于就是余數(shù)相同，是指被一個正整數(shù)所除，得到的余數(shù)相同。 定義：設(shè)a、b是兩個整數(shù)，如果a和b被正整數(shù)m除所得余數(shù)相同，則稱a與b對于模m同余，記作：
𝑎≡𝑏（mod 𝑚），
否則，就稱a與b對于模m不同余，記作𝑎≢𝑏（mod 𝑚）。
根據(jù)定義，a與b是否同于，不僅與a、b有關(guān)，還與模m有關(guān)，對一對數(shù)a和b，對于模m同余，而對于模n也許就不同余。根據(jù)同余的定義，顯然有以下幾種關(guān)系是成立的：
（1） 𝑎≡𝑎（mod 𝑚）；
（2） 𝑎≡𝑏（mod 𝑚）⟺𝑏≡𝑎（mod 𝑚）；
𝑎≡𝑏（mod 𝑚）（3） 𝑏≡𝑐（mod 𝑚） 𝑎≡𝑐（mod 𝑚）；
由此可見，同余是一種等價關(guān)系，以上這三條分別叫做同余的反身性，對稱性和傳遞性，而等式也具有這幾條性質(zhì)。
§2.2 剩余類與完全平方數(shù)
一、剩余類
一個整數(shù)被2除時，余數(shù)只能是0或1兩種可能，因此可以把所有的整數(shù)按照被2除的余數(shù)分成兩類，一類是被2除余數(shù)為0，另一類是被2除余數(shù)為1。也就是我們常說的偶數(shù)和奇數(shù)。同樣的道理，一個整數(shù)被3除時，余數(shù)只能是0、1、2這三種可能的某一種，因此所有的整數(shù)按照被3除可以分成余數(shù)為0、1、2三類。
一般地，任何一個整數(shù)。被一個非零的整數(shù)m除，可以得到商q和余數(shù)r，即a=mq+r。這里的r只能取O,l,2,„,m-1這m個值。
全體整數(shù)可按對模m是否同余分為若干個兩兩不相交的集合，使得在同一個集合申的任意兩個數(shù)對模m一定同余，而屬于不同集合中的兩個數(shù)對模m一定不同余。每下個這樣的集合稱為模m的同余類，或模m的剩余類。由模m的每個同余類中取定一個數(shù)作為代表構(gòu)成一組數(shù)，這組數(shù)就稱為模m的一個完全剩余系。 根據(jù)剩余類的概念，很容易得到以下幾條有關(guān)剩余類的性質(zhì)：
1、每一個整數(shù)一定包括在而且僅包含在模m的一個剩余類中；
2、整數(shù)p所屬的模m的剩余類中的每一個數(shù)都可以寫成km+p的形式，這里
k是整數(shù)；
3、整數(shù)p、q在模m的同一個剩余類中的充要條件是p、q對模m同余。
實際上，同余式就是剩余類等式的一個特殊情況，是集合中一個元素，前面有關(guān)同余的一些性質(zhì)對剩余類仍然成立。
4、在任意取定的m+1個整數(shù)中，必有兩個整數(shù)對模m同余；
根據(jù)同余式的性質(zhì)，我們很容易得到剩余系的其他一些性質(zhì)：
5、m個整數(shù)a1，a2，⋯，am是模m的一組完全剩余系的充要條件是
a1，a2，⋯，am中的任意兩個數(shù)對模m都不同余；
6、如果a1，a2，⋯，am是模m的一組完全剩余系，那么對任意的整數(shù)
c，c+a1，c+a2，⋯，c+am也是模m的一組完全剩余系；
二、完全平方數(shù)
若a為整數(shù)，則a2叫做完全平方數(shù)。例如1、4、9、16„„等，下面我們利用同余式來研究完全平方數(shù)。
完全平方數(shù)的個位數(shù)字只能是0、1、4、5、6、9；
具有一下性質(zhì)的數(shù)一定是非完全平方數(shù)：
（1） 個位數(shù)字是2、3、7、8的數(shù)；
（2） 𝑎≡2（mod 3）；
（3） 𝑎≡2,3（mod 4）；
（4） 𝑎≡2,3（mod 5）；
（5） 𝑎≡2,3,5,6,7（mod 8）；
§2.3 簡單的同余方程
《孫子算經(jīng)》中的“物不知數(shù)”問題開創(chuàng)了一次同余式研究的先河，但遺憾的是沒有上升到一套完整的計算程序和理論高度。南宋時期的數(shù)學(xué)家秦九韶在他的《數(shù)學(xué)九章》中提出了“大衍求一術(shù)”的算術(shù)方法，比較系統(tǒng)的論述一次同余方程組的解法的一般原理和一般程序。他的計算程序的核心是求一個數(shù)的多少倍除以另一個數(shù)所得的余數(shù)為1。
對于n次整系數(shù)多項式
𝑓 𝑥 =𝑎𝑛𝑥𝑛+𝑎𝑛−1𝑥𝑛−1+⋯+𝑎1𝑥+𝑎0
𝑓 𝑥 ≡0（mod 𝑚）叫做模m的同余方程。是同余方程成立的x的值叫做同余方程的解。顯然，若x=c是同余方程𝑓 𝑥 ≡0（mod 𝑚）的一個解，則剩余類c mod m中的每一個數(shù)都是這個方程的解。