C++之同余定理

(一)同余定理的定义

数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。（证明略）

(二)同余定理的定理

符号

 两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。 记作：a≡b (mod m)， 读作：a同余于b模m，或读作a与b对模m同余，例如 26≡2(mod 12)。 

定义

定理一：

8.幂运算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)

9.若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)

(三)同余定理相关定理

定义1 如果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同余。

定义2 从模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为偶数).

定理1 k个整数a1,a2,…,ak构成模m的完全剩余系的充要条件是k=m，且这m个数对模m两两不同余。

定理2 若x1,x2,…,xm 是模m的完全剩余系，（a,m）=1,b为整数，则ax1+b，ax2+b，…，axm+b也是模m的完全剩余系。

欧拉函数

定义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

代入上面的同余式，可得 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-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^2=100，有n100≡1(mod 125);

再由n是奇数知8|n^{2-1，进而n}100≡1(mod 8),而(125,8)=1，得证。

相关例题

例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，

所以 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=时，由于579-234+101-89=357≡0 (mod 7)，所以7|a。

应用例如：

可以通过同余的性质换算成

因为 5 mod 3 = 2

所以 2 与 5 是同余，表示成 5^101 mod 3 ≡ 2^101 mod 3

又因为 101 mod 3 = 2

所以 101 与 3 是同余，表示成 2^101 mod 3 ≡ 2^2 mod 3

（到这里可能大家都不理解，简单解释就是在底数相同时，指数变化 后在 去 mod 3，其实是个循环）

5^1 mod 3 = 2

5^2 mod 3 = 1

5^3 mod 3 = 2

5^4 mod 3 = 1

…………

所以在底数相同时可以对指数进行同余

所以上面这个问题 可以表示成 5^101 mod 3 ≡ 2^2 mod 3 = 1

方法二：

5^101 mod 3

因为 5 mod 3 = 2

所以 2 与 5 是同余

因为 5 与 5 是同余

通过同余式相乘（ 若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m) ）

2 ≡ 5 (mod 3)，5 ≡ 5 (mod 3)

可以表示成

2 * 5 mod 3 ≡ 5 * 5 mod 3 = 1

1 * 5 mod 3 ≡ 2 * 5 * 5 mod 3 = 2

2 * 5 mod 3 ≡ 1 * 5 * 5 mod 3 = 1

…………

依次类推所以可以用程序循环表示：

int a = 5, pow = 101, m = 3, result = 1;

(a + b) mod m = (a mod m + b mod m) mod m (a * b) mod m = ((a mod m) * (b mod m)) mod m 

2、高精度取模：

12345 = ( ( (1 * 10 +2 ) * 10 +3 ) * 10 + 4 ) * 10 + 5) 这就可以用同余加减法表示了