资源描述：
《数论入门教程v0.0》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ACM数论入门前言数论就像一杯毒酒，美，却令人蛋碎。——俺，2011一般来说，数论书上的证明都又屎又长，其实数论的很多东西我认为有着更直接的理解方式，特别是引入群论这个强大的工具之后，很多需要繁琐证明的结论都成了“显然”，这也是我写这篇文章的动因。当然那些教程自有其存在的原因——不是所有人都搞ACM(能深刻理解递归)，也不是所有人都懂群论。所以我还是介绍一下其他的经典教材：《数论概论》：简单实用。给非数学专业学生上课用的，可以说是扫盲级别的教材……但是，就是这本书吃透了前半部分，ACM的数论题绰绰有余了。《初
2、等数论及其应用》：上一本的扩充版，作者Rosen讲问题非常清晰，节后的习题不仅非常丰富全面，还会对该章节的主题进行扩展，让读者自己去研究探索。另外很注重对数论的应用。《哈代数论》：您看懂了？求交往……UESTC_TeamZ1最大公约数开始讨论这个话题之前我们还是来定义一些以后会用到的符号，比如说“
3、”。这个根竖线呢，不是分隔符，而是表示整除。a
4、b意味着b=a*k(k是一个整数)。比如说有3
5、6，4
6、12。注意任意整数a，有a
7、0。有了这个简洁的符号，就开始讨论公约数这个话题。两整数a,b公约数的定义是k
8、a
9、并且k
10、b，则k就是a,b的一个公约数。1.1算术基本定理与最大公约数如何求最大的公约数呢？一个思路是利用算术基本定理。算术基本定理听上去很神（装逼适用），其实就是说一个数能被唯一分解成若干质因子的乘积。这不是显然的么？嗯，在群众喜闻乐见的整数集上确实成立，但是在另外一些奇怪的集合上就未必了。不过，ACM题一般也不会涉及到那些（当然你学好了数论可以去出这种题坑人XD）。一个数a能成为另一个数b的因子则意味着a的质因子集合是b质因子集合的子集，当a的质因子集合与b的质因子集合相等的时候，即a=b的时候，得到最大
11、的因子。那么a,b的公因子就是{a的质因子}∩{b的质因子}的子集，其中最大的，当然就是该集合本身了。如何求{a的质因子}∩{b的质因子}（也就是最大公约数）呢？显然有：(注意：Pi表示自然数集上的第i个质数，而不是a或b的第i个质因数(参考0的质因数分解定义))在ACM界，有一个万用的证明结论的简单方法，它的名字叫“显然”。在这个地方我也用“显然”就这么混过去算了。于是我们得到了一个求最大公约数的方法，分解质因数，然后求交集。不过分解大数的质因数非常困难，在RSA分解挑战上可以看到，截止2007年，一些两百
12、位的整数都还没有被人分解。1.2欧几里得算法当然，还有一个更好的方法求最大公约数，那就是有名的欧几里得算法。设gcd(a,b)表示a,b的最大公约数。假设a>bad
13、a并且d
14、b<->a=k1*d并且b=k2*d<->a-b=(k1-k2)*d这意味a和b的公约数同a和a-b的公约数完全相同！这有啥用？搞ACM的都懂递归吧？这意味着我们可以把求gcd(a,b
15、)转化为求gcd(a-b,b)，并且我们每次都是拿其中大数减去小数，整个问题的规模会不断缩小！递归当然要研究递归的边界是啥。首先吧，如果较小数是0,那就开始循环了(gcd(a-0,0)=gcd(a,0))。gcd(0,a)是个啥呢？根据我们的对0分解质因数的定义，那当然就是a。如果没有0呢？可以看到我们的减法过程保证了不会出现负数，并且每搞一下两数的和的不断减小。和不断减小，且没有负数，这就保证了一定会搞出0。这里还有几个问题：1尼玛那啥我艹的0的什么定义啊？太流氓了有木有？gcd(0,a)居然是a！特么我觉
16、得该是0啊！！！！这确实是一个问题。先证明gcd(a,b)=gcd(a+b,a)。令a-b=c，代入我们之前的公式可以得到gcd(c+b,b)=gcd(c,b)。证明完毕。gcd(0,a)=gcd(0+a,a)=gcd(a,a)=a。这下你没话说了吧。2那好吧，如果搞成gcd(0,0)了肿么办？除非一开始a=b=0，否则不会出现这种情况。gcd(a,b)->gcd(a-b,b)这样搞一把:两个正数的情况：最多把一个正数搞成0。一个正数一个0的情况：已经搞不动了。证明完毕。3那我想知道gcd(0,0)的值是啥…
17、…我说了怕你不懂。好吧，如果你一定要知道的话，答案就是：gcd(0,0)=1/0。当然在程序实现中一个更常用的形式是gcd(a,b)=gcd(b,a%b)。设a=q*b+a%b,则a%b=a-q*b。其实就是一次性在a上减了q次b，减到a比b小，然后交换大小顺序罢了。就是:gcd(a,b)=gcd(a-b,b)=gcd(a-2*b,b)…=gcd(a-q*b,b)=gcd(a%b,b)=gcd(b,
