具体数学数论章-----致敬Kunth

整除性(divisible)：

_{^{引入了代表整除性。 m\n (m|n) 表示m整除n。注意这里的整除。表示的是n = km(k为整数)。}}

_{^{在整除性这里。m必须是个正数。也许你可以描述n 是 m 的k倍。这种描述中m完全可以是任何数。而在整除性中的表达m整除n,规定了m必须是个正数。而0没有限制。}}

那么回答以下问题：

1：什么是0的倍数？

2：什么能被0整除？

3：什么能被-1整除？

4：什么能被1整除？

5：2Pi能被Pi整除吗？

6: 2Pi能被2整除吗？

答案分别是：

1:0

2:没有任何数能被0整除。（因为m>0而在这里m=0）

3:同上没有任何数能被-1整除。也就是-1不能整除任何数（严格意义上来讲）

4:任何整数。

5:可以。根据整除性的定义 m>0 n/m 是一个整数即可。n m 是任何实数（m>0）

6:不可以。Pi是3.14... 是个无限不循环小数非整数。

最大公因子（greatest common divisor）：

用符号 gcd(n,m)表示。也就是所谓的最大公约数了。

首要的就是解决求两个数的最大公约数的问题了。

http://www.cnblogs.com/Milkor/p4379621.html

根据上面的链接里的方法基本上可以完美解决最大公约数的问题。

接下来探讨扩展欧几里德的使用和原理

扩展欧几里德(extended Euclidean):

描述:必然存在n',m'使得 n'n+m'm=gcd（n,m）成立。

证明这个定理有关乎贝祖定理（即裴蜀定理）。要搜的话，最好搜裴蜀定理，有更多的资料。

裴蜀定理（Bézout's identity）：

描述：对于nn'+mm'=d 这个方程有整数对解n',m',那么d一定是gcd(n,m)的倍数。（并且有解时，整数解对有无限对）

证明：

　　分三步证明：

　　　　证明1：证明有正整数对解n'm'的时候d一定是最小d(简称d0)的倍数。(这个d0我们还不能说是gcd(n.m)).

　　　　证明2: 证明nn'+mm'=gcd(n,m)有正整数解对n'm'.

　　　　证明3: 证明d0(最小d,之后不赘述)即位gcd(n,m).

我尽量详细描述。后有图版的。感谢贴出此图的吧主（吧主名字忘记了，抱歉，惭愧）。找了很久很久。

声明:能够满足nn'+mm'=d有正整数对解的值,这个d值是好值。

证明1：证明有正整数对解n'm'的时候d一定是最小d(简称d0)的倍数。(这个d0我们还不能说是gcd(n.m)).

　　　　设d0 = nn'+mm' ，d0是最小好值。 ①

　　　　 d = nn'+mm' , d是任意好值。　　②

　　　　　要证明1，即证明d=kd0(k是正整数) 即d是d0的倍数

　　　　 带余除法 d/d0 -> d = kd0+r ③

　　　　　 即要证明r = 0

　　　　　如果r>0 (r不可能<0)

　　　　　　r = d-kd0 = nn'+mm' - k(nn''+mm'') 由于式子①和式子②中的m'n'是不同的所以前者改用n'' m''来标记

　　　　　　 = (n'-kn'')n + (m'-m'')m

　　　　整理得 r = (n'-kn'')n + (m'-m'')m

其中n'-kn'' 和 (m'-m'')均为整数，所以r应该是一个好值。但是如果r是一个好值,然而根据③有r<d0。所以这和d0是最小好值是矛盾的。

　　　　所以r = 0.

　　　所以d = kd0 证毕。

证明2：nn'+mm'=gcd(n,m)有正整数解对n'm'.

　　利用带余除法：（把余数当做除数，原因后有，符合欧几里得。）

　　r1 = n - k1 m ①

　　r2 = m - k2 r1 ②

　　r3 = r1 - k3 r2 ③

　　r4 = r2 - k4 r3 ④

　　r5 = r3 - k5 r4 ⑤

　　......

　　r(n-1) = r(n-3) - k(n) r(n-2) ⑥

　　r(n) = r(n-2) - k(n) r(n-1) ⑦

　　图上利用数学归纳法证明对于所有的n的不同取值，存在u,v。使得r(n) = up+vq（图上的比较全，严谨）。回忆作者（似乎是他的学生）在旁边的注解。数学归纳法就是先打好地板。然后确立好你能从n层走上n+1层。那么你就能从地板上走到天际。

　　我在这里就不用数学归纳法了。我直接从头推到尾。（个人见解。）

　　那么复合①②式子：

　　r1 = n - k1 m ①

　　r2 = m - k2 r1 ②

　　① 代入 ②

　　r2 = (1+k1) m - k2 n （形式上和原来的式子一样）所以可以设该式为 r2 = s m - tn。

　　所以成立。

　　那么继续 r2 = s m - tn。复合 r3 = r1 - k3 r2 ③

　　r3 = r1 - k3 (s m - tn) 　代入式 ①

　　r3 = n - k1m - k3(s m - t n)

　　r3 = (1 + k3t) n - (k1+k3s) m （形式上和原来的式子一样）所以可以设该式为 r3 = s m - tn。（顺序无所谓只要符合贝组等式，即原等式的形式）

　由此一直递推。可以有

　 r(n-1)= sm+tn 　

　　之后你可以手写一下或者思考一下证明欧几里得的过程到最后一定会有余数 r = 0 (欧几里得的最后终点是gcd(0,n) = n)

　　假设 ⑦ 达到这种情况。即r(n) = 0.

　　gcd(n,m) = gcd(m,r1) = gcd(r1,r2) = gcd(r2,r3)... = gcd(r(n-1),r(n)) = gcd(r(n-1),0) = r(n-1).

　　所以 gcd(n,m) = r(n-1) = sm + tn = nn'+mm'.证毕。

证明3：证明d0(最小d,之后不赘述)即为gcd(n,m).

　　根据证明2。gcd(n,m) = nn'+mm' 其中 gcd(n,m)是好值

　　d0是最小好值。根据证明1 gcd(n,m)|d0。

　　设 c = gcd(n,m) / d0 （我们目的要证明c = 1）

　　对于 d0 = nn'+mm'

　　有 1 = n' (n/d0) + m' (m/d0)

　　其中 c|(n/d0) 把c = gcd(n,m) / d0 代入就可得。 c|(m/d0) .

　　那么 c|1

　　那么 c = 1.证毕

求解m',n'

现在让我们求nn'+mm'=gcd(n,m)的一组特解n',m'.

求解过程：

　　设n>m

　　n%m = r -> n = km+r -> r = n-km.

　　另有 rr'' + mm'' = gcd(r,m) (这个m还是原来的m 对应的m''不是m',注意这个'另'字)

　　由欧几里得定理得:

　　　　rr'' + mm'' = gcd(r,m) = gcd(n,m)

　　　(n-km) r'' + mm'' = gcd(n,m)

　　　 nr'' - kmr'' + mm'' = gcd(n,m)

　　　 nr'' + m(m''-kr'') = gcd(n,m)

　　　 所以 n' = r'' m' = m''- kr''

　　那么我们只要求出r'' 和 m'' 就可以得到 n' m'

那么对 rr'' + mm'' = gcd(n,m) 做同上的处理。　　就能形成递推关系。你可以这样考虑 n' m‘ 需要 r'' 和 m'' 而 r'' 和 m'' 需要 r''' 和 m'''......

　 假如我们知道最终结果的 r''''''''''' 和 m'''''''''' (标点数不知多少,但是是有限的)那么我们可以一直向上推出 n' m' 交给计算机处理吧。递推关系。

　　最后 r''''''''''' = 1 m''''''''''' = 0

可以有证明：

　　一直取模。最后余数会=0,且另外一个参数的值 = gcd(n,m)(因为gcd(0,a) = a) 所以另外一个解值为1 这个已经在证明裴蜀定理得第2条证明的时候已经使用过了。所以不再赘述。

递推关系有了。结尾判断有了。code.

 int x,y;

void EXGCD(int n,int m)

{

    if(m==)

    {

        x = ;

        y = ;

        return;

    }

    EXGCD(m,n%m);

    int t = x;

    x = y;

    y = t - n/m*y;

}

// nx + my = gcd(n.m)

// 所以要控制一下输出!

EXGCD 扩展欧几里德

对于扩展欧几里得的应用不言而喻。

1:经典的求乘法逆元。

定义 a*b mod m = 1 则b是a关于m的逆元。求b

即 a*b = km + 1 -> a*b - km = 1 （由前面的探讨,a和m要互素才能有解）

　　 那问题就是解出b了。直接扩展欧几里得求解

2:求解二元方程，判断二元方程有没有整数解对。

　　其实1是2的一个实例。

其实判断二元方程有没有整数解对应该是裴蜀定理的应用。

中国剩余定理：

对于这个，我深深地意识到WIKI百科才是真爱啊。baidu sougou 百科，都是表面上华丽，却没有进入实质性的探究啊。

附上链接：

http://zh.wikipedia.org/wiki/中国剩余定理

我觉得没有什么可以再去添加的了。或者说我现在也添加不上去什么了。

只能说一句。裴蜀定理真的是贯穿求同余方程的全程。(具体数学中作者也是调皮地写到4.5(指nn'+mm'=d)又拯救了我们一次)

在这里。将mod运算和同余方程联系在了一起。这是我之前怎么都想不通的。其实两者是相同的。

即知道xmod25 知道 xmod4 即能处理xmod100 便是中国剩余定理。这是我当时觉得百思不得其解的。因为百科上又或者是网上的资料都说韩信点兵之类的，也就只是描述mod运算。而非我们熟悉的同余方程组。

而后我知道了。

x mod 25 = 2　　　　->　　　　　　　　　x ≡ 2 (mod 25)

x mod 4 = 3 　　　　->　　　　　　　　　x ≡ 3 (mod 4)

以上转自blog <------强大严谨有钻研性的老人！！！

C = R1Y1C1C（mod G） = R1Y1(mod G) = R1 (mod G)

所以wiki上先证明了互素而有解，我觉得真是严谨,精辟。

主要就是利用Mi = M/mi 其中M为所有mi的值的乘积.

那么Mi % mj = 0.(i != j)

再利用逆元。使得构造出来的数符合条件。

有题：http://acm.hdu.edu.cn/showproblem.php?pid=1370

扩展中国剩余定理（一）：

中国剩余定理对于m1 m2 m3 m4 m5...模的集合若相互均互质十分方便。（构造法确实精美）

但是如果m1 m2 m3 m4 m5 没有相互互质。中国剩余定理的那个构造法就是失效了。此时就是扩展中国剩余定理出现的地方了。

具体分析：

研究问题从小问题开始。我们只考虑2组数据。

x mod 3 = 1

x mod 6 = 2

比如这样的两组数据。

假如我们使用中国剩余定理。

而有3 | 6 那么就找不到6关于3的乘法逆元了（或者叫数论倒数）。也就是找不到6的某个倍数 mod 3 = 1

那么如果说出现了这样的问题了呢？（实际上确实是出现了）

方法一：广义上的孙子定理（论文）

这里直接给出解法，然后再去求证各个部分.

首先对模分别进行质因数分解。

对于因子2 分别有 2^2 2^5 取大的 2^5 来源于同余7的那个式子。

同理对于因子3 最大为3^2 来源于同余2的那个式子。

5 来源于同余7的式子

　　　　　 7 来源于同余 2 的式子

然后可以将原式转成模互质的式子。然后对其进行求解即可。

证明：重点在于为何能等价于对应素因子最大的那个式子。

先有 x≡b(mod m) 对m进行素因子分解有 x≡b(mod p1) x≡b(mod p2)....... p 为 m的素因子。（带指数）这个是基本的同余定理。

然后对于不同的式子有

x ≡ b1(mod m1)

x ≡ b2(mod m2)

....

可以等价于 x≡b1(mod p1) x≡b1(mod p2).......

　　　　　　x≡b2 (mod p1') x≡b(mod p2').......

　　　　　　....

其中p1 p1' 只是指数不同。

我们拿一组来讲。 x≡b1 (mod p1) 和 x≡b2 (mod p1')

根据上述的运算。我们要证明

x≡b1 (mod p1) 和 x≡b2 (mod p1')

如果 p1>p1' (其实是比较指数大小)

则等价于 x≡b1 (mod p1)

如果p1<p1'

则等价于 x≡b2 (mod p1')

假如p1>p1'

先证：x≡b(mod m) 那么可以推得 x≡(b+km)(mod m)

也就是说如果 x≡b1(mod m) 等价于 x≡b2(mod m)

　　　ps:一定有b1和b2之差=km 也就是说这组方程等价于一个方程 x≡b1(mod m) 或 x≡b2(mod m) 因为解x是一样的。

　　　那么对于 x≡b1 (mod p1) 和 x≡b2 (mod p1')

　　　 因为p1|p1', 所以符合x≡b1 (mod p1) 一定符合 x≡b1 (mod p1‘)

　　　 而符合 x≡b1 (mod p1‘) 的x 一定符合 x≡b2 (mod p1').

　　　 那么整个方程组等价于 x≡b1 (mod p1)

反之同理可证.这个方法是从一个中国(China,祖国要大写！)的论文上获得的。不过它没有证明。证明是我自己想出来添加上去的。也许有疏忽。望见谅。

扩展中国剩余定理（二）:

处理的还是非互素模的同余方程组求解问题。

先从2个方程组的规模(问题小规模)开始看起。

x≡b1 (mod m1)

x≡b2 (mod m2)

解2个式子的方程组并不难。可以思考一下。这个方程组联立之后目测有2个参数。我们可以利用扩展欧几里得算法求解。

x - b1 = n1m1

x - b2 = n2m2

去x, n1m1+b1 = b2+n2m2

其中n1 n2 是未知的。所以化成 n1m1-n2m2 = b2 - b1.

求解n1 n2.

根据n1或者n2 可以直接获得 x

题外话：考虑一个这样的问题: 给你一堆这样的m 和对应 b 注意各个b的值为一个范围。问存在不存在一个x 满足其中2个式子。

　　对于这个问题。我们只要枚举取两个式子。　判断 n1m1-n2m2 = b2 - b1 有无解即可。尽管b2 b1是范围。我们可以取公共范围。

那么考虑多个方程组的时候。

2个方程组我们可以解决。那我们是否可以把2个方程组合并成一个方程组呢，并且保留原来的形式呢?如果可以的话。多个方程组就解决了。因为2个合成1个。合成出来的那个又能和下一个方程合并。一直传递下去。

x≡b1 (mod m1)

x≡b2 (mod m2)

对于这个，我可以求得x的值。而我们需要的是满足多个的值。设这个值是k.那么k ≡ x(mod m1) 且 k≡x(mod m2)这样k值就能满足式1 和式2

而 k ≡ x(mod m1) 且 k≡x(mod m2) -> k≡x(mod lcm(m1,m2))而这个式子始终保留了原来式子的特点把k看作x x看作b 你就懂了。然后不断的继续下去。最后的值就是结果了。

巴特西

具体数学数论章-----致敬Kunth

最新文章

热门文章