100除以7的余數(shù)是2，意思就是說把100個東西七個七個分成一組的話最后還剩2個。余數(shù)有一個嚴(yán)格的定義：假如被除數(shù)是a，除數(shù)是b（假設(shè)它們均為正整數(shù)），那么我們總能夠找到一個小于b的自然數(shù)r和一個整數(shù)m，使得a=bm+r。這個r就是a除以b的余數(shù)，m被稱作商。我們經(jīng)常用mod來表示取余，a除以b余r就寫成a mod b = r。
如果兩個數(shù)a和b之差能被m整除，那么我們就說a和b對模數(shù)m同余（關(guān)于m同余）。比如，100-60除以8正好除盡，我們就說100和60對于模數(shù)8同余。它的另一層含義就是說，100和60除以8的余數(shù)相同。a和b對m同余，我們記作a≡b(mod m)。比如，剛才的例子可以寫成100≡60(mod 8)。你會發(fā)現(xiàn)這種記號到處都在用，比如和數(shù)論相關(guān)的書中就經(jīng)常把a mod 3 = 1寫作a≡1(mod 3)。
之所以把同余當(dāng)作一種運算，是因為同余滿足運算的諸多性質(zhì)。比如，同余滿足等價關(guān)系。具體地說，它滿足自反性（一個數(shù)永遠(yuǎn)和自己同余）、對稱性（a和b同余，b和a也就同余）和傳遞性（a和b同余，b和c同余可以推出a和c同余）。這三個性質(zhì)都是顯然的。
同余運算里還有稍微復(fù)雜一些的性質(zhì)。比如，同余運算和整數(shù)加減法一樣滿足“等量加等量，其和不變”。小學(xué)我們就知道，等式兩邊可以同時加上一個相等的數(shù)。例如，a=b可以推出a+100=b+100。這樣的性質(zhì)在同余運算中也有：對于同一個模數(shù)m，如果a和b同余，x和y同余，那么a+x和b+y也同余。在我看來，這個結(jié)論幾乎是顯然的。當(dāng)然，我們也可以嚴(yán)格證明這個定理。這個定理對減法同樣有效。
性質(zhì)：如果a≡b(mod m)，x≡y(mod m)，則a+x≡b+y(mod m)。 證明：條件告訴我們，可以找到p和q使得a-mp = b-mq，也存在r和s使得x-mr = y-ms。于是a-mp + x-mr = b-mq + y-ms，即a+x-m(p+r) = b+y-m(q+s)，這就告訴我們a+x和b+y除以m的余數(shù)相同。
容易想到，兩個同余式對應(yīng)相乘，同余式兩邊仍然相等：
如果a≡b(mod m)，x≡y(mod m)，則ax≡by(mod m)。 證明：條件告訴我們，a-mp = b-mq，x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms)，等式兩邊分別展開后必然是ax-m(...) = by-m(...)的形式，這就說明ax≡by(mod m)。
現(xiàn)在你知道為什么
有的題要叫你“輸出答案mod xxxxx的結(jié)果”了吧，那是為了避免高精度運算，因為這里的結(jié)論告訴我們在運算過程中邊算邊mod和算完后再mod的結(jié)果一樣。假如a是一個很大的數(shù)，令b=a mod m，那么(a * 100) mod m和(b * 100) mod m的結(jié)果是完全一樣的，這相當(dāng)于是在a≡b (mod m)的兩邊同時乘以100。這些結(jié)論其實都很顯然，因為同余運算只關(guān)心余數(shù)（不關(guān)心“整的部分”），完全可以每一次運算后都只保留余數(shù)。因此，整個運算過程中參與運算的數(shù)都不超過m，避免了高精度的出現(xiàn)。
在證明
Fermat小定理時，我們用到了這樣一個定理：
如果ac≡bc(mod m)，且c和m互質(zhì)，則a≡b(mod m) （就是說同余式兩邊可以同時除以一個和模數(shù)互質(zhì)的數(shù)）。
證明：條件告訴我們，ac-mp = bc-mq，移項可得ac-bc = mp-mq，也就是說(a-b)c = m(p-q)。這表明，(a-b)c里需要含有因子m，但c和m互質(zhì)，因此只有可能是a-b被m整除，也即a≡b(mod m
http://www.matrix67.com/blog/archives/236保存一下，以備今后學(xué)習(xí):-)