MOD运算

mod运算，即求余运算，是在整数运算中求一个整数n除以另一个整数p的余数的运算，且不考虑运算的商。在计算机程序设计中通常都有MOD运算，它的含义是取得两个整数相除后结果的余数。例如:7mod3=1因为7除以3商2余1。余数1即执行MOD运算后的结果。

简介

用于查找除法运算中的余数的运算被称为模。当你用数字'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ρ)