簡介
用于查找除法運算中的餘數的運算被稱為模。當你用數字'a'除以'b'時，它可以表示為'amodb'，就是餘數。這也被稱為模數。使用這個計算器可以執行mod運算，計算出除法中的餘數。
模p運算
給定一個正整數p，任意一個整數n，一定存在等式
n=kp+r其中k、r是整數，且0≤r
對于正整數p和整數a,b，定義如下運算：
取模運算：amodp表示a除以p的餘數。
模p加法：(a+b)modp，其結果是a+b算術和除以p的餘數，也就是說，(a+b)=kp+r，則(a+b)modp=r。
模p減法：(a-b)modp，其結果是a-b算術差除以p的餘數。
模p乘法：(a×b)modp，其結果是a×b算術乘法除以p的餘數。
可以發現,模p運算和普通的四則運算有很多類似的規律，如：
簡單的證明其中第一個公式：
((a+b)modp+c)modp=(a+(b+c)modp)modp
假設
a=k1*p+r1
b=k2*p+r2
c=k3*p+r3
a+b=(k1+k2)p+(r1+r2)
如果(r1+r2)>=p，則
(a+b)modp=(r1+r2)-p
否則
(a+b)modp=(r1+r2)
再和c進行模p和運算，得到
結果為r1+r2+r3的算術和除以p的餘數。
對右側進行計算可以得到同樣的結果，得證。
歐拉函數
歐拉函數是數論中很重要的一個函數，歐拉函數是指：對于一個正整數n，小于n且和n互質的正整數的個數，記做：φ(n)，其中φ(1)被定義為1，但是并沒有任何實質的意義。
定義小于n且和n互質的數構成的集合為Zn，稱呼這個集合為n的完全餘數集合。
顯然，對于素數p，φ(p)=p-1.對于兩個素數p、q，他們的乘積n=pq滿足φ(n)=(p-1)(q-1)
證明：對于質數p,q，滿足φ(n)=(p-1)(q-1)
考慮n的完全餘數集Zn={1,2,....,pq-1}
而不和n互質的集合由下面三個集合的并構成：
1)能夠被p整除的集合{p,2p,3p,....,(q-1)p}共計q-1個
2)能夠被q整除的集合{q,2q,3q,....,(p-1)q}共計p-1個
3)很顯然，1、2集合中沒有共同的元素，因此Zn中元素個數＝pq-(p-1+q-1+1)=(p-1)(q-1)
歐拉定理
對于互質的整數a和n，有a^φ(n)≡1modn
證明：
首先證明下面這個命題：
對于集合Zn={x^1,x^2,...,x^φ(n)}，考慮集合
S={ax^1modn,ax^2modn,...,ax^φ(n)modn}
則S=Zn
1)由于a,n互質，x^i也與n互質，則ax^i也一定于p互質，因此
任意x^i,ax^imodn必然是Zn的一個元素
2)對于Zn中兩個元素x^i和x^j，如果x^i≠x^j
則ax^imodn≠ax^imodn，這個由a、p互質和消去律可以得出。
所以，很明顯，S=Zn
既然這樣，那麼
（ax^1×ax^2×...×ax^φ(n)）modn
=（ax^1modn×ax^2modn×...×ax^φ(nmodn）modn
=（x^1×x^2×...×x^φ(n）modn
考慮上面等式左邊和右邊
左邊等于(a^φ(n)×（x^1×x^2×...×x^φ(n)）modn)modn
右邊等于x^1×x^2×...×x^φ(n)）modn
而x^1×x^2×...×x^φ(n)）modn和p互質
根據消去律，可以從等式兩邊約去，就得到：
a^φ(n)≡1modn推論：對于互質的數a、n，滿足a^(φ(n)+1)≡amodn
進一步應用
有關mod的一道證明題
不用算數基本定理，證明[a,b](a,b)=|ab|
證明：在數論中，證明等式有一種常用的方式，就是證明兩邊互為整除，此題也不例外，隻是要先移
項。
|ab|/(a,b)=|a|(|b|/(a,b))=>
a|(|ab|/(a,b))
同理有：b|(|ab|/(a,b))
于是，|ab|/(a,b)是a,b的公倍數，即[a,b]|(|ab|/(a,b))
∵|a||[a,b]
∴(|a|/(a,b))|([a,b]/(a,b))
同理：(|b|/(a,b))|([a,b]/(a,b))
又∵(|a|/(a,b))與(|b|/(a,b))互質
∴（|ab|/(a,b)²）|([a,b]/(a,b))
∴(|ab|/(a,b))|[a,b]
綜上所述，[a,b](a,b)=|ab|.
設m,m′都是正整數，d=(m,mˆ)，b≡bˆ(modd).證明系統
x≡b(modm)①
x≡bˆ(modmˆ)②
的任意兩個解都是模ρ同餘，其中ρ=lcm{m，mˆ}.
證明:設y是滿足題設的另外一個解，則有：y≡b(modm)③
y≡bˆ(modmˆ)④
∵x≡b(modm)，∴x≡b(modm/d),y≡b(modm/d)
兩式相減，則有x-y≡b-b≡0≡(modm/d)
∴x≡y(modm/d)
同理：x≡y(modmˆ/d)
∵(m/d,mˆ/d)=1
∴x≡y(modmmˆ/d²)
設y=x+kmmˆ/d²
分别代入③，④中，并結合①，②，則有
x+kmmˆ/d²≡b≡x(modm)=>kmmˆ/d²≡0(modm)
x+kmmˆ/d²≡bˆ≡x(modmˆ)=>kmmˆ/d²≡0(modmˆ)
即：m|kmmˆ/d²=>kmˆ/d²為整數=>(mˆ/d)(k/d)為整數
mˆ|kmmˆ/d²=>km/d²為整數=>(m/d)(k/d)為整數
顯然，(mˆ/d,d)=1與(m/d,d)=1至少有一個成立，否則(m,mˆ)=d²,矛盾.
∴k=ld,y=x+lmmˆ/d,
而mmˆ/d=|mmˆ|/(m,mˆ)=[m,mˆ]=ρ=lcm{m，mˆ}
∴y=x+lρ=>
y≡x(modρ)
