初等数论

本讲内容：

? 数论基本性质

? 同余及同余方程

? 【大数取余】

? 【费马定理】

? 【快速幂模运算】

数论主要讨论自然数、整数等一系列数字之间的关系。 数论四大定理

? 费马小定理：a是一个整数，p是一个质数，a、p互素，

则 a^p≡a(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,使得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) * b]y0

= 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 = d = a

明显，这个不定方程的一组解为

x = 1, y = 0

5.1 【求解 x，y的方法的理解】：

设 a>b。 1、显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

2、ab<>0 时 设 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;

这样我们就得到了求解 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 均为该方程的解

? 因此，可设计一个求解出特解的算法，然后利用这条性质

得到该方程的通解

? 步骤如下：

? 求解a、b的最大公约数d=(a,b)，若d不被c整除

则方程无整数解，否则，将方程两边同时除以d，得到:

a0x+b0y=c0

? 使用扩展欧几里得算法计算上述方程的解x0,y0，求

得特解x1=x0c0，y1=y0c0。

? 代入通解得x=x0c0-a0t，y=y0c0+b0t

POJ 1061 青蛙的约会

两只青蛙它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。

不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙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 ( p?Z) 即 (n-m)*t+Lp=x-y (L>0)

问题转化为：

求满足 A*t+Lp=B 的最小 t (t>0)

即求 一次同余方程

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。

求解a`x-n`y=b/d。

x不是唯一的，但x的所有解相差n`的整数倍x,x+n/d,x+2*n/d+…+x+(d-1)*n/d

扩展欧几里得算法：

# include <stdio.h>

__int64 gcd(__int64 a,__int64 b)

{

if(b==0)

return a;

return gcd(b,a%b);

}

void exgcd(__int64 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("Impossible\n");

continue;

}

a/=r;

b/=r;

c/=r;

exgcd(a,b,k1,k2);

t=c*k1/b;

k1=c*k1-t*b;

if(k1<0)

k1+=b;

printf("%I64d\n",k1);

}

return 0;

}

5.3【同余式】

? 若a, b为整数，m为一个常整数，则当

m|(a - b)

时，我们称a，b对模m同余，记作

a≡b(mod m)

5.4 【同余方程】

a,b都是整数，m是正整数，形如ax≡b(mod m)，且x是未知整数的同余式称为一元线性同余方程。设gcd(a,b)=d,如果d|b，则方程恰有d个mod m不同余的解，否则方程无解。 设a0=a/d,m0=m/d;现在我们又回到了之前学的扩展欧几里得算法。由于此时gcd(a0,m0)=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++)

ans[i]=(x+(i-1)*m/d)%m;

}

5.5 【中国剩余定理】

学习这个之前，我们先看一道题目：

POJ 1006 Biorhythms

这是一道中国剩余定理的典型应用。

根据题意，可得同余方程组：X=p(mod 23)

X=e(mod 28)

X=i(mod 33)

因为23,28,33都是两两互素的，即满足中国剩余定理的条件，不过值得注意的是题目要求的是大于d的最小整数解。

根据中国剩余定理，给定两两互素的正整数m[1],m[2],m[3]........m[r],任何小于M=m [1] * m [2] * m [3] *.......m [r]的非负整数N均可由M%m[i]唯一确定。令Mi=M/m[i],因为m[1],m[2],m[3]........，m[r]两两互素，因此gcd（Mi，m[i]）==1，即Mi* Pi==1(mod m[i]),

同余方程组：x=a [1](mod m[1]);

x=a [2](mod m[2]);

x=a [3](mod m[3]);

.....................

x=a [r](mod m[r]); 有模M的唯一解；

容易验证a[1]*M1*P1+a[2]*M2*P2+.............a[r]*Mr*Pr就是

同余方程组的解。

代码：

二、素数：

定义：设整数n≠0，±1.如果除了显然因数±1，±n以外，n没有其他因数，那么，n叫做素数（或质数

不可约数），否则，n叫做合数.

规定：若没有特殊说明，素数总是指正整数，通常写成p或 p1， p2，…， pn。

1. 算术基本定理

因为每一个大于1的正整数n都可以唯一的被分解成素数的乘积，在乘积中的素因子按照非降序排列。即正整数n的分解式n=P1^a1*P2^a2*……Pk^ak，其中P1,P2……Pk是素数，P1<P2<……Pk，且a1,a2,……ak是正整数。

设D(n)为n的正因子个数，则D(n)=（a1+1）*(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）可以推出）；

再看一题：

http://acm./showproblem.php?pid=1452

题目要求2004的X次方取余29，即（2004^X）%29。因为每一个大于1的正整数n都可以唯一的被分解成素数的乘积，在乘积中的素因子按照非降序排列。即正整数n的分解式n=P1^a1*P2^a2*……Pk^ak，其中P1,P2……Pk是素数，P1<P2<……Pk，且a1,a2,……ak是正整数。

因为2004可以被分解成2004=2^2*3*167，所以2004^X=(2^2*3*167)^X,即2004^X=2^(2*X)*3^X*167^X；

所以S=[2^（2*X-1）/(2-1)]*[(3^X-1)/(3-1)]*[(167^X-1)/(167-1)]=R／332, 其中Ｒ＝2^（2*X-1）*(3^X-1)*(167^X-1)；

因为Ｘ很大，所以根据费马小定理：对于任意素数Ｐ，任意整数ａ，有ａ＾（Ｐ－１）ｍｏｄＰ＝１；所以ａ＾２８ｍｏｄ２９＝１；

因此ａ＾ｂｍｏｄ２９＝ａ＾（ｂｍｏｄ２８）ｍｏｄ２９，所以直接将Ｘ取余２８，这样，Ｘ再大也没有关系，同时，解题时运用了快速模取幂运算，这样在时间复杂度上也有保障，运行Ｘ＝１０００００００００是毫无压力的！！！

！

最后，再考虑S=（R/332）mod29，即R+29k=332S（k为满足等

式的任意整数），而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×t1 + b×t2 = 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(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 <stdio.h>

int ExtendedEuclid( int f,int d ,int *result);

int main()

{

int x,y,z;

z = 0;

printf("输入两个数：\n");

scanf("%d%d",&x,&y);

if(ExtendedEuclid(x,y,&z))

printf("%d和%d互素，乘法的逆元是：%d\n",x,y,z);

else

printf("%d和%d不互素，最大公约数为：%d\n",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; /* 两个数不互素则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! 数论

2191 Mersenne Composite Numbers 数论 2381 Random Gap 数论

2417 Discrete Logging 数论

1510 Hares and Foxes 数论

1641 Rational Approximation 数论

1730 Perfect Pth Powers 数论

1777 Vivian's Problem 数论

2061 Pseudo-random Numbers 数论

1014 Dividing 数论/DP?/组合数学->母函数?

1606 Jugs 数论/搜索

1995 Raising Modulo Numbers 数论->大数的幂求余 2115 C Looooops 数论->解模线性方程

1288 Sly Number 数论->解模线性方程组

1395 Cog-Wheels 数学->解正系数的线性方程组