初等数论.docx

1、初等数论初等数论本讲内容：数论基本性质同余及同余方程【大数取余】【费马定理】【快速幂模运算】数论主要讨论自然数、整数等一系列数字之间的关系。数论四大定理费马小定理：a是一个整数，p是一个质数，a、p互素，则 apa(mod p)威尔逊定理： p是一个质数，则(p-1)! -1(mod p)欧拉定理：对于互质的整数a和n，有a(n) 1 (mod n)。欧拉函数(n) 表示与 n互素且不超过n的正整数的个数 还有一个呢？（China reminder theory）1、整除的概念2、公约数3、公倍数4、欧几里得算法（辗转相除法）5、扩展欧几里得算法定义：设a和b不完全为0，则存在整数x和y,使得

2、xa+yb=gcd(a,b)。若gcd(a, b) = d, 则必定存在整数x, y使得 ax + by = d 由于ax + by = d bx0 + (a%b)y0 = d （经过一次辗转：a=b,b=a%b） 在计算机中a%b = a (a/b) * b 所以 bx0 + (a%b)y0 = bx0 + a (a/b) * by0 = a y0 + b(x0 (a/b) y0) = ax + by 对照a, b系数，可由不定方程bx0 + (a%b)y0 = d的解x0 ,y0，得ax + by = d的解x = y0 , y = x0 (a/b) y0而初始条件为 ax + 0*y =

3、 d = a 明显，这个不定方程的一组解为x = 1, y = 0 5.1 【求解 x，y的方法的理解】：设 ab。 1、显然当 b=0，gcd（a，b）=a。此时 x=1，y=0； 2、ab0 时 设 ax1+by1=gcd(a,b); bx2+(a mod b)y2=gcd(b,a mod b); 根据欧几里德原理有 gcd(a,b)=gcd(b,a mod b); 则:ax1+by1=bx2+(a mod b)y2; 即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2; 根据恒等定理得：x1=y2; y1=x2-(a/b)*y2; 这样我们就得到了

4、求解 x1,y1 的方法：x1，y1 的值基于 x2，y2. 上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。5.2 【使用扩展欧几里德算法解决不定方程的办法】：利用扩展欧几里得算法，很容易求得诸如ax+by=c (1)这样二元一次不定方程的整数解问题。设a,b的最大公约数为d=（a,b），则a=a1d， b=b1d，(a1,b1)=1，因此(1)可表示为：d(a1x+b1y) = c于是，当且仅当d|c时(1)方有整数解显然，若x0,y0为(1)的解，那么对任意整数t有x = x0-bt, y = y0 + at 均为该方程的解因此，可设计一个

5、求解出特解的算法，然后利用这条性质得到该方程的通解步骤如下：求解a、b的最大公约数d=(a,b)，若d不被c整除则方程无整数解，否则，将方程两边同时除以d，得到:a0x+b0y=c0 使用扩展欧几里得算法计算上述方程的解x0,y0，求得特解x1=x0c0，y1=y0c0。代入通解得x=x0c0-a0t，y=y0c0+b0tPOJ 1061 青蛙的约会两只青蛙它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上

6、，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。 思路：设两只青蛙跳了 t 步A的坐标 x+mt， B的坐标 y+nt相遇的充要条件：x+mt-y-nt= pL ( pZ) 即 (n-m)*t+Lp=x-y

7、(L0)问题转化为：求满足 A*t+Lp=B 的最小 t (t0)即求 一次同余方程 A*t = B (mod L) 的最小正整数解（穷举？）解ax = b (mod n)方程 等价于存在y，使得ax-ny=b。记d=gcd(a,n), a=d*a, n=d*n,那么必有d|b。求解ax-ny=b/d。x不是唯一的，但x的所有解相差n的整数倍x,x+n/d,x+2*n/d+x+(d-1)*n/d扩展欧几里得算法：# include _int64 gcd(_int64 a,_int64 b) if(b=0) return a; return gcd(b,a%b);void exgcd(_int6

8、4 a,_int64 b,_int64 &m,_int64 &n) if(b=0) m=1; n=0; return ; exgcd(b,a%b,m,n); _int64 t; t=m; m=n; n=t-a/b*n;int main() _int64 x,y,m,n,l,a,b,c,k1,k2,r,t; while(scanf(%I64d%I64d%I64d%I64d%I64d,&x,&y,&m,&n,&l)!=EOF) a=n-m; b=l; c=x-y; r=gcd(a,b); if(c%r) printf(Impossiblen); continue; a/=r; b/=r; c/=r

9、; exgcd(a,b,k1,k2); t=c*k1/b; k1=c*k1-t*b; if(k10) k1+=b; printf(%I64dn,k1); return 0;5.3【同余式】若a, b为整数，m为一个常整数，则当m|(a - b)时，我们称a，b对模m同余，记作ab(mod m) 5.4 【同余方程】a,b都是整数，m是正整数，形如axb(mod m)，且x是未知整数的同余式称为一元线性同余方程。设gcd(a,b)=d,如果d|b，则方程恰有d个mod m不同余的解，否则方程无解。设a0=a/d,m0=m/d;现在我们又回到了之前学的扩展欧几里得算法。由于此时gcd(a0,m0)

10、=1,因此可以运用扩展欧几里得算法算出a0x+m0y=b/d的解x,虽然 x不唯一，但都属于同一个模m剩余系，方程共有d个模m剩余类满足要求，即：X,x+m0,x+2m0,x+(d-1)m0.求方程所有解的算法：int solve (int a,int b,int m) Ex_gcd(a,m,d,x,y); if(b%d) return -1;/代表无解 x=x*(b/d)%m; for(int i=1;i=d;i+) ansi=(x+(i-1)*m/d)%m; 5.5 【中国剩余定理】学习这个之前，我们先看一道题目：POJ 1006 Biorhythms这是一道中国剩余定理的典型应用。根据题

11、意，可得同余方程组：X=p(mod 23) X=e(mod 28) X=i(mod 33)因为23,28,33都是两两互素的，即满足中国剩余定理的条件，不过值得注意的是题目要求的是大于d的最小整数解。根据中国剩余定理，给定两两互素的正整数m1,m2,m3.mr,任何小于M=m 1 * m 2 * m 3 *.m r的非负整数N均可由M%mi唯一确定。令Mi=M/mi,因为m1,m2,m3.，mr两两互素，因此gcd（Mi，mi）=1，即Mi* Pi=1(mod mi),同余方程组：x=a 1(mod m1);x=a 2(mod m2); x=a 3(mod m3); . x=a r(mod m

12、r);有模M的唯一解；容易验证a1*M1*P1+a2*M2*P2+.ar*Mr*Pr就是同余方程组的解。代码：二、素数：定义：设整数n0，1.如果除了显然因数1，n以外，n没有其他因数，那么，n叫做素数（或质数不可约数），否则，n叫做合数.规定：若没有特殊说明，素数总是指正整数，通常写成p或 p1， p2， pn。1. 算术基本定理因为每一个大于1的正整数n都可以唯一的被分解成素数的乘积，在乘积中的素因子按照非降序排列。即正整数n的分解式n=P1a1*P2a2*Pkak，其中P1,P2Pk是素数，P1P2Pk，且a1,a2,ak是正整数。设D(n)为n的正因子个数，则D(n)=（a1+1）*(

13、a2+1)(ak+1)；Q（n）为n的所有因子之和，Q(n)=P1(a1+1)/(P1-1)*P2(a2+1)/(P2-1)Pk(ak+1)/(Pk-1);2、【素数定理】：（1）、一个小于整实数x的素数个数P(x)=x/(lnx)；（ln以10为底）； （2）、令F(n)是第n个素数，其中n是正整数，那么F(n)=n*ln(n);（由（1）可以推出）；再看一题：题目要求2004的X次方取余29，即（2004X）%29。因为每一个大于1的正整数n都可以唯一的被分解成素数的乘积，在乘积中的素因子按照非降序排列。即正整数n的分解式n=P1a1*P2a2*Pkak，其中P1,P2Pk是素数，P1P2

14、Pk，且a1,a2,ak是正整数。因为2004可以被分解成2004=22*3*167，所以2004X=(22*3*167)X,即2004X=2(2*X)*3X*167X；所以S=2（2*X-1）/(2-1)*(3X-1)/(3-1)*(167X-1)/(167-1)=R332, 其中2（2*X-1）*(3X-1)*(167X-1)；因为很大，所以根据费马小定理：对于任意素数，任意整数，有（）；所以；因此（），所以直接将取余，这样，再大也没有关系，同时，解题时运用了快速模取幂运算，这样在时间复杂度上也有保障，运行是毫无压力的最后，再考虑S=（R/332）mod29，即R+29k=332S（k为满

15、足等式的任意整数），而9*332-103*29=1，所以9*（R+29k）=9*332S=S+103*29S，所以332关于29的逆元是9，所以(R*9)mod29=Smod29。至此，此题已经解出。代码：附录：乘法逆元：如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。 为了证明上面的结论，我们把上述计算中xi、yi看成ti的迭代初始值，考察一组数(t1，t2，t3)，用归纳法证明：当通过扩展欧几里德算法计算后，每一行都满足a

16、t1 + bt2 = t3 第一行：1 a + 0 b = a成立 第二行：0 a + 1 b = b成立 假设前k行都成立，考察第k+1行 对于k-1行和k行有 t1(k-1) t2(k-1) t3(k-1) ；t1(k) t2(k) t3(k) 分别满足： t1(k-1) a + t2(k-1) b = t3(k-1) t1(k) a + t2(k) b = t3(k) 根据扩展欧几里德算法，假设t3(k-1) = j t3(k) + r 则： t3(k+1) = r t2(k+1) = t2(k-1) - j t2(k) t1(k+1) = t1(k-1) - j t1(k) 则 t1(

17、k+1) a + t2(k+1) b =t1(k-1) a - j t1(k) a +t2(k-1) b - j t2(k) b= t3(k-1) - j t3(k) = r = t3(k+1) 得证 因此，当最终t3迭代计算到1时，有t1 a + t2 b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。c语言实现/扩展的欧几里德算法求乘法逆元 #include int ExtendedEuclid( int f,int d ,int *result); int main() int x,y,z; z = 0; printf(输入两个数：n); scanf(%d%d,&x,&y

18、); if(ExtendedEuclid(x,y,&z) printf(%d和%d互素，乘法的逆元是：%dn,x,y,z); else printf(%d和%d不互素，最大公约数为：%dn,x,y,z); return 0; int ExtendedEuclid( int f,int d ,int *result) int x1,x2,x3,y1,y2,y3,t1,t2,t3,q; x1 = y2 = 1; x2 = y1 = 0; x3 = ( f=d )?f:d; y3 = ( f=d )?d:f; while( 1 ) if ( y3 = 0 ) *result = x3; /* 两个数

19、不互素则result为两个数的最大公约数，此时返回值为零 */ return 0; if ( y3 = 1 ) *result = y2; /* 两个数互素则resutl为其乘法逆元，此时返回值为1 */ return 1; q = x3/y3; t1 = x1 - q*y1; t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; 练习题（POJ）：1023 The Fun Number System 数论1091 跳蚤 数论1152 An Easy Problem! 数论21

20、91 Mersenne Composite Numbers 数论2381 Random Gap 数论2417 Discrete Logging 数论1510 Hares and Foxes 数论1641 Rational Approximation 数论1730 Perfect Pth Powers 数论1777 Vivians Problem 数论2061 Pseudo-random Numbers 数论1014 Dividing 数论/DP?/组合数学-母函数?1606 Jugs 数论/搜索1995 Raising Modulo Numbers 数论-大数的幂求余2115 C Looooops 数论-解模线性方程1288 Sly Number 数论-解模线性方程组1395 Cog-Wheels 数学-解正系数的线性方程组