一、 同余
對於整數除以某個正整數的問題，如果只關心余數的情況，就產生同余的概念。
定義1 用給定的正整數m分別除整數a、b，如果所得的余數相等，則稱a、b對模m同余，記作a≡b(mod m)，如 56≡0 （mod 8）。
定理1 整數a,b對模m同余的充要條件是 a-b能被m整除（即m|a-b）。
證 設a=mq1+r1, 0<=r1<m;
b=mq2+r2, 0<=r2<m.
若a≡b(mod m)，按定義1，r1=r2,於是a-b=m(q1+q2),即有m|a-b.
反之，若m|a-b,即m|m(q1-a2)+r1-r2，則m|r1-r2，但|r1-r2|<m，故r1=r2,即a≡b(mod m)。
推論1 a≡b(mod m)的充要條件是a=mt+b（t為整數）。即a，b對m同余，則a，b相差整數個m。
定理2 同余關系具有反身性、對稱性與傳遞性，即
1）a≡a (mod m);
2）若a≡b (mod m), 則b≡a (mod m);
3）若a≡b (mod m), b≡c (mod m)，則a≡c (mod m).
定理3 若a≡b(mod m), c≡d (mod m),則
1）a+c≡b+d (mod m);
2）a-c≡b-d (mod m);
3）ac≡bd (mod m).
多於兩個的同模同余式也能夠進行加減乘運算。對於乘法還有下面的推論：
推論2 若a≡b(mod m),n為自然數，則an≡bn (mod m)。
定理4 若ca≡cb(mod m), (c,m)=d, 且a,b為整數，則a≡b(mod m/d).
推論3 若ca=cb(mod m), (c,m)=1,且a,b為整數，則a≡b(mod m).
定理5 若a≡b (mod m),a≡b (mod n),則a≡b(mod [m,n]). （注：[m,n]表示m,n的最小公倍數）
推論4 若a≡b(mod mi), i=1,2,…,n，則a≡b (mod [m1,m2,..,mn]).
例1 證明：正整數a是9的倍數必須且只須a的各位數碼之和是9的倍數。
證 設a=an.10n+an-1.10n-1+…+a0
由10≡1 (mod 9)得10k≡1(mod 9),k=0,1,2,…,n， （同余的傳遞性,推論2，1=10(mod9),10=100(mod9)---）
所以 ak.10k≡ak (mod 9), k=0,1,2,…,n。
所以a≡a0+a1+...+an (mod 9)
因此 9|a的充要條件是 9| a0+a1+...+an 。
例2 設a=anan-1…a1a0,求11|a的充要條件。
解由10≡-1 (mod 11),得10k≡(-1)k (mod 11), k=0,1,2,…,n
而 a≡a0-a1+a2-…+(-1)nan (mod 11)
因此 11|a的充要條件是11| a0-a1+a2-…+(-1)nan.
例3 求正整數a能被7整除的條件。
解 由於 1000≡-1 (mod 7)，從而1000k≡(-1)k (mod 7), k=0,1,2,…,n,
於是設a= anan-1…a1a0 (1000) 這就有a≡a0-a1+a2-…+(-1)nan (mod 7)
因此 7|a的充要條件是a0-a1+a2-…+(-1)nan ≡0 (mod 7) 這裡的ai為三位數（一千進制）.
如當a=89101234579時，由於579-234+101-89=357≡0 (mod 7)，所以7|a。
定義2 如果m為自然數，集合Kr={x|x=mt+r,t是任意整數}，r=0,1,…,m
則稱K0,K1,…,Km-1為模m的剩余類。
例如，模2的剩余類是偶數類與奇數類；模3的剩余類是:K0={…,-6,-3,0,3,6,…}，K1={…,-5,-2,1,4,7,…}，K2={…,-4,-1,2,5,8…}。
剩余類具有如下列比較明顯的性質：
1）模m的剩余類K0，K1，……，Km-1都是整數的非空子集；
2）每個整數必屬於且只屬於一個剩余類；
3）兩個整數屬於同一個剩余類的充要條件是它們對模m同余。
定義3 從模m的每個剩余類中任取一個數，所得到的m個數叫做模m的完全剩余系。
對模m來說，它的完全剩余系是很多的，經常采用的是：
0,1,2,…,m-1;
1,2,3,…,m;
-(m-1)/2,…,-1,0,1,…,m/2 (m為奇數)，
-m/2+1,…,-1,0,1,…,m/2 (m為偶數)，
-m/2,…,-1,0,1,…,m/2-1 (m為偶數).
定理6 k個整數a1,a2,…,ak構成模m的完全剩余系的充要條件是k=m，且這m個數對模m兩兩不同余。
定理7 若x1,x2,…,xm 是模m的完全剩余系，（a,m）=1,b為整數，則ax1+b，ax2+b，…，axm+b也是模m的完全剩余系。（注：(m,n)表示m,n的最大公約數）
定義1 在模m的完全剩余系中，所有與m互素的數叫做模m的簡化剩余系。例如1，3，7，9是模10的一個簡化剩余系。
定義2 若對任意的自然數m，用記號ф(m)表示0,1,2,…,m-1中與m互素的數的個數，則稱ф(m)為歐拉函數。
例如ф(10)=4，ф(7)=6，ф(1)=1。
定理1 k個整數a1,a2,…,ak構成模m簡化剩余系的充要條件是k=ф(m)，(ai,m)=1,i=1,2,…, ф(m),且這ф(m)個數對模m兩兩不同余。
定理2 若(a,m)=1，x1,x2,…,xф(m)是模m的簡化剩余系，則ax1,ax2,…,axф(m)也是模m的簡化剩余系。
定理3(歐拉定理) 若(a,m)=1，則aф(m) ≡1 (mod m)
證 設x1,x2,…,xф(m)是模m的簡化剩余系，根據定理2，ax1,ax2,…,axф(m)也是模m的簡化剩余系。
由此可知x1,x2,…,xф(m)中任一個數必與ax1,ax2,…,axф(m)中某一個數對模m同余；反之ax1,ax2,…,axф(m)中任一個數必與x1,x2,…,xф(m)中某一個數對模m同余，這就有：
ax1ax2…axф(m)≡x1x2…xф(m) (mod m),又(x1x2…xф(m),m)=1,所以aф(m) ≡1 (mod m)。
例1 已知x=h是使ax≡1 (mod m)中成立的最小正整數，求證h|ф(m)。
證 由ah-1=mt(t為整數)可知(a,m)=1，於是
aф(m) ≡1 (mod m)。
令ф(m)=hq+r,0<=r<h, q為自然數
代入上面的同余式，可得 ar ≡1 (mod m),所以r=0，故h|ф(m)。
推論（費馬小定理） 若p是素數，則
1） 當(a,p)=1時，ap-1 ≡1 (mod p)；
2） ap ≡a (mod p)
證 先證1）。由p是素數，知0,1,2,…,p-1中有p-1個數與p互素，於是ф(p)=p-1。又因為(a,p)=1，所以根據定理3得證1）。
再證2）。當(a,p)=1時，由1）知2)成立；當(a,p)不等於1時，p|a，余數同為0,2)也成立。
歐拉在1760年證明了定理3，故稱為歐拉定理。費馬在1640年提出了上面的推論，它的證明是歐拉在1736年完成的，這個推論通常叫做費馬小定理。
例2 設a為整數，求證a5≡a(mod 30).
證 由於30=2.3.5，而依據費馬小定理，有
a5≡a(mod 5) (1)
a3≡a(mod 3) (2)
a2≡a(mod 2) (3)
由(2)得 a5≡a3≡a(mod 3) （4）
由(3)得a5≡a4≡a2≡a(mod 2) (5)
於是由(1).(4),(5)，並且2,3,5兩兩互素，所以 a5≡a(mod 30).
定理4 若p是素數，則ф(pa)=pa-pa-1。 （ф(pa)的計算公式）
證 考慮模pa的完全剩余系0,1,2,…,p,…,2p,…,pa-1 (1)
(1)式中與pa不互素的數只有p的倍數0,p,2p,…,(pa-1–1)p,這共有p a-1個，於是(1)中與pa互素的數有pa-p a-1個，所以ф(pa)=pa-pa-1。
定理5 若(m,n)=1,則ф(mn)=ф(m)ф(n)。
推論 若正整數m1,m2,…mk兩兩互素，則ф(m1m2…mk)=ф(m1)ф(m2)…ф(mk).
定理6 若m的標准分解式為m=p1a1p2a2…pkak,
則ф(m)=p1a1-1p2a2-1…pkak-1(p1-1)(p2-1)…(pk-1).
例3 設(n,10)=1,求證n101與n的末三位數相同。
證：為了證明n101-n≡0只要證明n100≡1(mod 1000).
事實上由(n,125)=1,φ(125)= φ(5^3)=5^3-5^2=100，有n100≡1(mod 125);
再由n是奇數知8|n^2-1，進而n^100≡1(mod 8),而(125,8)=1，得證。
