扫码或点击进入无线充模块店铺
同余定理
一、同余：
对于整数除以某个正整数的问题，如果只关心余数的情况，就产生同余的概念。
定义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)。
推论 a≡b(mod m)的充要条件是a=mt+b（t为整数）。
表示对模m同余关系的式子叫做模m的同余式，简称同余，同余式的记号是高斯（Gauss）在1801年首先使用的。
定理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).
多于两个的同模同余式也能够进行加减乘运算。
对于乘法还有下面的推论：
推论 若a≡b(mod m),n为自然数，则an≡bn (mod m)。
定理4 若ca≡cb(mod m), (c,m)=d, 且a,b为整数，则a≡b(mod m/d).
推论 若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]).
推论 若a≡b(mod mi), i=1,2,…,n，则a≡b (mod [m1,m2,..,mn]).
例：已知23 ≡ 1(mod 7)，则22005 ≡ 23*668+1 ≡ (23)668*2 ≡ 2(mod 7) (该计算使用了定理3)
证：23 ≡ 1(mod 7)，由定律5，得23 * 23 ≡ 1*1(mod 7)…(23)668 ≡ 1(mod 7),
故，(23)668*2 ≡ 2(mod 7)。
算法运用：
1.乘法取模：ab mod n = (a mod n)(b mod n) mod n
1 //1.a*b%d 2 int mul_mod(int a, int b, int d) 3 { 4 a %= n; 5 b %= n; 6 return (int)((long long)a*b%n); 7 }
1 //2.a*b%c 2 int mul_mod(int a, int b, int c) 3 { 4 int r = 1, d = a; 5 while(b) 6 { 7 if(b&1) 8 r = (r*d)%c; 9 d = (d*d)%c; 10 b >>= 1; 11 } 12 return r; 13 }
2.大整数取模：
1 //大整数取模 n%m 2 int big_mod(char n[], int m) 3 { 4 int len = strlen(n); 5 long long ans=0; 6 for(int i=0; i<len; i++) 7 ans = ((long long)ans*10+n[i]-'0')%m; 8 return (int)ans; 9 }
3. 幂取模
1 //1.根据定义 2 int pow_mod(int a, int n, int m) 3 { 4 long long ans=1; 5 for(int i=0; i<n; i++) 6 ans = (long long)ans*n%m 7 return ans; 8 }
1 //2.分治法思想 2 int pow_mod(int a, int n, int m) 3 { 4 if(n == 0) 5 return 1; 6 int x = pow_mod(a, n/2, m); 7 long long ans = (long long)x*x%m; 8 if(n%2 == 1) 9 ans = ans*a%m; 10 return (int)ans; 11 }
定义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的完全剩余系。
二 、欧拉函数
定义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，得证。
算法：
1.求解φ(n)
1 //直接求解欧拉函数 2 int phi(int n) 3 { 4 //返回euler(n) 5 int res=n,a=n; 6 for(int i=2;i*i<=a;i++) 7 { 8 if(a%i==0) 9 { 10 res=res/i*(i-1); //先进行除法是为了防止中间数据的溢出 11 while(a%i==0) a/=i; 12 } 13 } 14 if(a>1) 15 res=res/a*(a-1); 16 return res; 17 }
筛选法打欧拉函数表 #define Max 1000001 int euler[Max]; void Init() { for(int i=1;i<Max;i++) euler[i]=i; for(int i=2;i<Max;i++) if(euler[i]==i) for(int j=i;j<Max;j+=i) euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出 }
设物有x，可得
x≡2（mod 3）；
x≡3（mod 5）；
x≡2（mod 7）.
先看看一次同余方程的一般解法。
[公式]
[公式]
...
[公式]
首先让 [公式]
使[公式]
使[公式]{[公式]取最小值}
求出[公式]，代入以下式子：
[公式]
即可求出x的 最小值
回到刚才的问题
设物有x，可得
x≡2（mod 3）；
x≡3（mod 5）；
x≡2（mod 7）.
m＝3*5*7=105
[公式]＝105，[公式]＝105，[公式]＝105
[公式] =35， [公式] =21， [公式] =15
[公式] ， [公式] {最小值}
[公式] ， [公式]
[公式] ， [公式]
最后
[公式]
[公式]
[公式]
穷举，得 x 的最小值为23，解毕.
检验：
23[公式]3=7......2 三三数之剩二
23[公式]5=4......3 五五数之剩三
23[公式]7=3......2 七七数之剩二
新人发
解释，数论中的重要概念。给定一个正整数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（mod m）。读为：a同余于b模m。在这里“≡”是同余符号。
二、同余定理的一些性质：
对于同一个除数，两个数之和（或差）与它们的余数之和（或差）同余。(加减乘同理）
(a+b)%c==(a%c+b%c)%c
对于同一个除数，如果有两个整数同余，那么它们的差一定能被这个除数整除。
对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。
扫码或点击进入无线充模块店铺