作者:氯化钡和硫酸银
时间:2014年2月3日 11:14
来源:http://blog.sina.cn/dpool/blog/s/blog_a661ecd50101ax02.html
最近弄到一本电子书,《数论概论》,感觉这本书写得非常棒…先从简单的开始。
费马小定理
费马小定理的内容如下:若 p 为素数,整数 a 与 p 互素,那么有
看着很简单吧。它的证明也非常巧妙。
我们考虑1,2,3,…,p-1 这 p-1 个数,将它们同乘以 a 得到 p-1 个数 a,2a,3a,…,(p-1)a。考虑一些小的例子,我们很容易猜想这 p-1 个数分别与 1,2,3,…,p-1 同余(模 p,次序可能不同)。
我们只需证明这两件事:
1.它们均不是 p 的倍数; 2.它们两两模 p 不同余。
第一项的证明简单,因为如果某一项 ka 是 p 的倍数,则 p 必定整除 k,a 中的一个,但是事实上这两个都不是 p 的倍数( a与 p 互素, k 是 1 到 p-1 的整数),矛盾。所以这些数都不是 p 的倍数。
第二项的证明也不难。若某两项 ka,la 模 p 同余,则 p 被它们的差(k-l)a整除 , p 必定整除k-l,a中的一个,但是事实上这两个都不是 p 的倍数( a 与 p 互素, |k-l| 是 1 到 p-2 的整数),矛盾。
于是,这 p-1个数除以 p 的余数只可能分别是 1,2,3,…,p-1,尽管次序可能不同。这样的话,利用多个同余式可以相乘的性质(以及乘法交换律),就可以得到:
两边有一个公因子,把它约掉我们就证完了。别急,先看看能不能约:可以约分的条件是 p 与要约掉的公因子互质。这里公因子是 (p-1)!,它显然不被素数 p 整除,也就是说它与 p 互素。这样就证完了。
还有一种证法,用到了二项式定理。设 p 为质数,则由二项式定理得:
然后,可以证明C(p,k) 是 p 的倍数(其中 k 是 1 到 p-1 的整数)。证明很简单,把它用组合数公式写开就是:
显然分母上没有因数p ,这样分子上的 p 约不掉,整个分数就是 p 的倍数。
现在设上面二项式定理中的 a,b 为整数,再模 p 就得到:
这个式子很简洁,它可以推广到多个底数的情况。大家都知道,一般的二项式定理推广到多元时形式很复杂,但是在这里就很简单:
这只需对左边用n-1 次二元的定理即可。现在我们只差最后一步,把所有的 a_i 都取为 1 ,并设有 a 个 1 ,就得到:
又因为 a 与 p 互素,两边约掉一个 a 就完成任务。
欧拉定理
欧拉定理是个费马小定理的推广,把素数模数推广为任意正整数。若整数 a 与正整数 m 互素,则有
其中 φ(m)表示在 1,2,3,…,m 中与 m 互素的整数的个数(也叫做欧拉函数)。(互素的定义:两个数的 “最大公约数”是1。)
注:φ(m)=1,欧拉定理两侧mod 1后,均为0,等式依然成立。
既然先说了欧拉函数的定义,我们就用它来把费马小定理的第一个证明变化一下。把 1,2,3,…,p-1 这些数换为在1,2,3,…,m 中与 m 互素的整数,共有 φ(m) 个,再把它们同乘以 a 后,新得到的这 φ(m)个数应满足这两个性质:
1.它们均与 m 互素; 2.它们两两模 m 不同余。
第一个简单,因为两个与 m 互素的整数相乘仍然与 m 互素(这是个很直观的结论,因为找不到大于 1的公因子。互素的本质:两个数分别做质因数分解,二者没有共同的质因数。)。第二个也好证,如果两个数 ka,la 模 m 同余,则 m 整除 (k-l)a ,而由 (a,m)=1 得 m 必定整除k-l ,这显然是不成立的,因为后者的绝对值一定小于 m 。
这样,这 φ(m)个数除以 m 的余数必然一一对应于 1,2,3,…,m 中与 m互素的整数(次序可能不同。因为:互素的两个数相除,余数必然与除数互素,可以采用反证法证明,如果余数与除数不互素,那么除数与被除数必然不互素,即存在相同的质因数。),接下来只需照葫芦画瓢即可:
其中 x_i表示在 1,2,3,…,m 中与 m 互素的 φ(m) 个整数,既然它们与 m互素,那么把它们从同余式两边约去,欧拉定理就证完了。
顺便说一句,因为对于素数p ,有 φ(p)=p-1 (显然 1,2,3,…,p-1 与 p 互素),因此费马小定理可以称为欧拉定理的一个特殊情况。
威尔逊定理
刚才的两个定理描述的是整数的某个特定的幂,而威尔逊定理则着眼于阶乘。设 p 为素数,则有:
(没准 C++的同志们会以为是不等号…)
证明它有个简单易懂的方法:配对。其实在等差数列求和的时候就可以用这种方法:据说高斯上小学的时候算出了1+2+3+…+100,方法是这样的……这个都知道吧。我们用所谓“倒序相加”法代替了配对,避免了奇偶讨论,不过在这里要防止开方的麻烦,我们还是用配对法。
因为这里是相乘,最好能找到两个数的乘积除以 p 余 1 ,把它们配对可以减少运算量。还好我们有这个结论:
对于 1,2,3,…,p-1 中的任意一个数 a ,在 1,2,3,…,p-1 中恰有一个数 b 使得 ab 被p 除余数为 1 。
把 b 称作 a模 p 的数论倒数,用 a^(-1) 表示(当然在 p 不是质数时也可类似定义数论倒数,不过要求 a,p互素)。这个结论其实我们已经证过,刚才证明费马小定理时,把 1,2,3,…,p-1 同时乘上 a ,它们除以 p的余数必然有且仅有一个为 1 ,它对应的 a 的倍数就是满足条件的 b 。
显然, a 也是b 模 p 的数论倒数。
下面我们就开始配对了。考虑集合 {1,2,3,…,p-1},首先从中任选一个数,并且将它连它的数论倒数一起拿出来成对(也可以说这两个数互为数论倒数,正如相反数一样);然后再任选一个数,将它和它的数论倒数一起拿出来成对,……,直到集合里没有元素。
当然这里假设 p为奇素数(这样才可以一对一对),可以先对 p=2 时验证一下,发现威尔逊定理成立,后面就设 p 为奇素数。
稍等一下,下面的两个问题关系到这种配对能否进行:从集合里随便取一个数,
1.它的数论倒数会不会已经取过而不能配对?
2.它的数论倒数会不会是它自己?
对于第一个问题,答案是不会,因为如果出现这样的情况,这个数的数论倒数就可以同时与两个数配对,违反了数论倒数的唯一性。
对于第二个问题,这个是可能的,比如 1 的数论倒数就是它自己。事实上, p-1 的数论倒数也是它自己。不过还好,容易证明在1,2,3,…,p-1 中这种数只有这两个:
若 x的数论倒数是它自己,则 x^2 被 p 除的余数为 1 ,因此 p 整除 x^2-1 即 (x+1)(x-1) ,又由于 p为素数,则 p 必定整除 x+1,x-1 中的一个,整除前者则 x=p-1 ,整除后者则 x=1 。
这样,我们的配对策略只需稍加修改即可:先把 1,p-1 两个数拿出来,剩下的数就不存在那两个问题,可以顺利配成 (p-3)/2对。每对乘积模 p 都余 1 ,不用管它们,起作用的是 1,p-1 两个数,它们的乘积模 p 为 -1。这样威尔逊定理就证完了。
最后简单提一下,这个定理反过来说,设 p>1 为满足 (p-1)!≡-1(mod p) 的正整数,则 p 一定是个质数。
证明很简单,如果p 为合数,那么不妨设 p=ab ,其中 a,b 均大于 1 小于 p 。当 a,b 不同时显然 p 能整除 (p-1)!(因为有这两个因数)。当 a,b 相同时,只要 a>2 ,那么 (p-1)! 中含有 a,2a 两个因数,同样有 p 整除(p-1)! 。若 a=b=2 ,则 p=4 ,代入验证一下发现 (p-1)!≡2(mod p) 也不对。
这个定理是一个判断素数的很准确的算法,不过由于我们不能有效地计算阶乘(计算幂可以用快速幂等方法有效计算),因此实际上没人用这个算法。
中国剩余定理
中国剩余定理研究的是同余方程组,内容如下:
设
是 n 个两两互质的正整数(可以设为大于 1,因为如果有 1 的话这个数相当于废的),则下列关于整数 x 的方程组
恰有一个解满足
也就是说,如果知道一个整数分别除以 n个两两互质的除数的余数,那么这个整数除以全部除数的积的余数也是唯一确定的(并且一定存在)。
看起来这个定理很麻烦,其实要证它只要会数数就行了…还用到乘法原理。
首先我们把所有m_i 的乘积记为 M ,先数一数满足 0<=x
然后,我们再数数如果把每个整数都分别除以 n 个除数 m_i (并且把 n个余数看作是一个数组),会产生多少种情况。这个容易通过乘法原理数出来,第 i 个余数有 m_i 个不同的取值,那么总情况数就是 M。
接下来我们证明关键的一个结论:满足 0<=x
使用反证法很容易证,假设在 0<=x
这样就只有一种可能性:满足 0<=x
还有一种证法用的是构造的思路。没错,这种问题也可以构造,我们想办法构造出一个整数,使得它除了被第一个除数除余数为 1外,其它的除数都能整除它。类似地,我们把“第一个除数”换成“第 i 个除数”,可以构造出 n个这样的整数,然后解同余方程的时候,我只需让 a_1 乘以第一个整数, a_2 乘以第二个整数,……, a_n 乘以第 n个整数,把它们加起来,再除以所有除数的乘积 M 就行了。
找出 n个这样的整数要简单地多。构造第一个时,我们很容易得出它被 M/m_1 (也就是除了第一个除数之外,其它所有除数的乘积)整除,而它被m_1 除的余数是 1 。用裴蜀定理可以很容易证明存在这样的数,不过不知道那个定理也不要紧,我们把 1,2,3,…,m_1-1这些整数全部乘以 M/m_1 ,然后证明这些乘积除以 m_1 的余数两两不同并且不为 0 (由于 m_1 与 M/m_1互素,这是很容易证的)。这样,这些乘积中必然有一个除以 m_1 的余数为 1 。这个数就是我们要找的。
————————————————
来自百度百科
![](https://startbitcoin.org/wp-content/uploads/2022/01/09c2d8f4-d1b9-408f-b36d-12c78c9764c3.jpeg)
![](https://startbitcoin.org/wp-content/uploads/2022/01/2a1a1a93-153b-4a90-b309-c53f3376285e.jpeg)
![](https://startbitcoin.org/wp-content/uploads/2022/01/79c976a6-6c60-41dc-bff8-dc016402621f.jpeg)
![](https://startbitcoin.org/wp-content/uploads/2022/01/b99a37ae-e52b-4a93-81e8-3e7e9c414736.jpeg)
![](https://startbitcoin.org/wp-content/uploads/2022/01/98b8d395-383c-4867-a43e-9a0f807039b8.jpeg)
![](https://startbitcoin.org/wp-content/uploads/2022/01/3daa77d4-47d4-4eab-a0e1-f176dbb5f47f.jpeg)
![](https://startbitcoin.org/wp-content/uploads/2022/01/abffde4d-f5b1-4370-811e-2318bb692652.jpeg)
![](https://startbitcoin.org/wp-content/uploads/2022/01/40e11157-e2b9-481a-8a57-72e4c9fb73af.jpeg)
![](https://startbitcoin.org/wp-content/uploads/2022/01/25654ef0-229f-440c-a17d-6aba32a62a94.jpeg)
顺便提一下,这个定理被命名为“中国剩余定理”或者“孙子定理”是因为中国古算书《孙子算经》上有个问题:
有物不知其数(shù),三三数(shǔ)之余二,五五数(shǔ)之余三,七七(shǔ)数之余二,问物几何?
后来就有人编了首诗,它可以解决模 3,5,7 的同余方程组问题:
三人同行七十稀,五树梅花廿一枝,
七子团圆正半月,除百零五便得知。
注意 70 恰好被5,7 整除,被 3 除余数为 1 ,同理后面的 21,15 也是这么来的。只要除数不变,这三个数就可以用。最后除以 105当然是为了保证结果在 0~104 范围内。
由于M=3×5×7=105
那么通解则是
x=2×70+3×21+2×15 + k×105 (k是任意整数,所以可以是负整数)
那么mod M的唯一解,则是
x=(2×70+3×21+2×15) mod 105=23