理論背景
同餘數學上
，兩個整數除以同一個整數，若得相同餘數，則二整數同餘（英文：Modular arithmetic；德文：Kongruenz）。同餘理論常被用於數論中。最先引用同餘的概念與符號者為德國數學家高斯。同餘理論是初等數論的重要組成部分，是研究整數問題的重要工具之一，利用同餘來論證某些整除性的問題是很簡便的。同餘是數學競賽的重要組成部分。
同餘符號
同餘數a，b，若它們除以整數m所得的餘數相等，則稱a與b對於模m同餘或a同餘於b模m
記作a ≡ b (mod m)
讀作a同餘於b模m，或讀作a與b關於模m同餘。
比如 26 ≡ 2 (mod 12)
【定義】設m是大於1的正整數,a,b是整數,如果m|(a-b),則稱a與b關於模m同餘,記作a≡b(mod m),讀作a與b對模m同餘.
顯然,有如下事實
(1)若a≡0(mod m),則m|a;
(2)a≡b(mod m)等價於a與b分別用m去除,餘數相同.
【證明】 充分性:設a=mq1+r1,b=mq2+r2,0<=r1,r2
∵ m|(a-b),a-b=m(q1-q2)+(r1-r2).
則有m|(r1-r2).
∵0<=r1,r2<=|r1-r2|
即r1-r2=0,∴r1=r2.
必要性:設a,b用m去除餘數為r,即a=mq1+r,b=mq2+r,
a-b=m(q1-q2) ∴m|(a-b),
故a≡b(mod m).
性質信息
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)
4 同餘式相加若a ≡ b (mod m)，c≡d(mod m)，則a+-c≡b+-d（mod m）
5 同餘式相乘 若a ≡ b (mod m)，c≡d(mod m)，則ac≡bd（mod m）
【證明】上述性質很容易證明,下面僅證明(3).
∵a≡b(mod m)∴m|(a-b) 同理m|(b-c),
∴m|[(a-b)+(b-c)]∴m|(a-c).
故a≡c(mod m).
4 線性運算如果a ≡ b (mod m)，c ≡ d (mod m),那么(1)a ± c ≡ b ± d (mod m)，(2)a * c ≡ b * d (mod m)
【證明】(1)∵a≡b(mod m),∴m|(a-b) 同理 m|(c-d)
∴m|[(a-b)±(c-d)] ∴m|[(a±c)-(b±d)]
∴a ± c ≡ b ± d (mod m)
(2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)
又 m|(a-b) , m|(c-d) ∴m|(ac-bd)
∴a * c ≡ b * d (mod m)
5 除法若ac ≡ bc (mod m) c≠0 則 a≡ b (mod m/(c,m)) 其中(c,m)表示c,m的最大公約數
特殊地 (c,m)=1 則a ≡ b (mod m)
6 乘方如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)
7 若a ≡ b (mod m)，n|m,則 a ≡ b (mod n)
8 若a ≡ b (mod mi） i=1,2...n 則 a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最低公倍數
9 歐拉定理
設a,m∈N,(a,m)=1,則a^(φ(m))≡1(mod m)
(注:φ(m)指模m的簡系個數， φ(m)=m-1, 如果m是素數；φ(m=q1^r1 * q2^r2 * ...*qi^ri)=m (1-1/q1)(1-1/q2)...(1-1/qi))
推論: 費馬小定理: 若p為質數，則a^p ≡ a (mod p) 即a^(p-1) ≡ 1 (mod p)
（但是當p|a時不等價）
10 中國剩餘定理
設整數m1,m2,m3,......,mn 兩兩互素，令m=m1m2m3m4m5...mn（mi的連乘）。則對於任意的J在（1,n)整數，下列聯立的同餘式有解：
{xj≡1(mod mj)
{xj≡0(mod mi) i不等於j
令x為從1到najxj的和，則x適合下列聯立同餘式
x≡aj（mod mj）, j=1,2,3,.....,n
另：求自然數a的個位數字，就是求a與哪一個一位數對於模10同餘。
相關定理
同餘一次同餘式和孫子定理同餘式的求解中，一次同餘式是最基本的。設整係數n次(n>0)多項式ƒ(x)=αnx+…+α1x+α0,m是一個正整數且不能整除αn，則
(1)叫做模m的n次同餘式。如果整數 α是(1)的解且α≡α┡(mod m)，那么α┡也是(1)的解，因此,(1)的不同解是指滿足(1)的模 m互不同餘的數。對於一次同餘式 αx≡b(mod m)有解的充分必要條件是(α,m)│b)，若有解則有(α,m)個解。一次同餘式組是指
。 (2)
同餘在中國古代《孫子算經》中，對某些具體的一次同餘式組已有解法，把這一解法加以推廣，就是著名的孫子剩餘定理：設m, m,…, m是k個兩兩互素的正整數
，則同餘式組(2)的解是。式中，孫子剩餘定理又被稱之為中國剩餘定理，是數論中一個重要的定理，除了數論本身，數學的許多其他分支以及一些套用學科都要用到它。例如,設m=m1m2…mk，m1, m2,…,mk兩兩互素,利用孫子剩餘定理可將同餘式(1)的求解問題化為同餘式組ƒ(x)≡0(mod mi)(i=1，2,…,k)的求解問題，於是就只需要研究(1)中m是素數方冪的情形了。又如,可將0≤x
如果已知x的模係數記數法，就可用孫子定理找出x。這個記數法的優點是加法和乘法無須進位，它在計算機方面有套用。
素數為模的同餘式 關於素數為模的同餘式，1770年，J.-L.拉格朗日證明了如下定理：設p是素數，那么模 p的n次同餘式的解數不大於 n（重解也計算在內）。人們稱之為拉格朗日定理。由此立即可以得威爾森定理：如果 p是素數，那么(p-1)!+1≡0(mod p)。因為x-1≡0(mod p)有p-1個解1,…,p-1，故由拉格朗日定理可得
同餘，
將x=0代入上式得-1≡(-1)(p-1)!(mod p),這就證明了威爾森定理。威爾森定理的逆定理也是成立的，可用反證法簡單證出。用拉格朗日定理還可證明：當p≥5是一個素數時,則有同餘。這個定理是1862年，由J.沃斯頓霍姆證明的。
設ƒ(x1,x2,…,xn)是n元整係數多項式,p是一個奇素數,對於同餘式ƒ(x,x,…,x) ≡0(mod p)的解(x,x,…,x)(0≤xj
