在这总结下基本数论，其实数论并不是什么深奥的东西。不过现在讨论的是基本数论
一.素数
所谓素数，就是一个正整数，它除了本身和 1 以外并没有任何其他因子。素数就好象是正整数的原子一样，著名的高斯「唯一分解定理」说，任何一个整数。可以写成一串质数相乘的积。所以这又称为质数
数论中有两个关于素数的著名猜想：
1.哥德巴赫猜想：任意一个大于4的偶数必定可以表示为两素数之和
哥德巴赫猜想有两个内容，第一部分叫做奇数的猜想，第二部分叫做偶数的猜想。奇数的猜想指出，任何一个大于等于7的奇数都是三个素数的和。偶数的猜想是说，大于等于4的偶数一定是两个素数的和。”（引自《哥德巴赫猜想与潘承洞》）
2.孪生素数猜想：所谓孪生素数指的就是这种间隔为 2 的相邻素数，它们之间的距离已经近得不能再近了，就象孪生兄弟一样。最小的孪生素数是 (3, 5)，在 100 以内的孪生素数还有 (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61) 和 (71, 73)，总计有 8 组。
二.费马(Fermat):数论大师
1.费马大定理：n>2是整数，则方程x^n+y^n=z^n没有满足xyz≠0的整数解。这个是不定方程，它已经由美国数学家证明了(1995年)，证明的过程是相当艰深的！
2.费马小定理：若p为素数，a为正整数，那么一定有a^p≡a(Mod p)
三：倍数和约数：若a被m整除，则m是a的约数，a是m的倍数 (a/m)
四：约数个数公式：若任意整数a的标准分解：a=p1^e1*p2^e2*...*pn^en 那么a的约数的个数为(e1+1)(e2+1)...(en+1)
五：最大公约数：设a>b，若r≡a(Mod b)，则gcd(a,b) = gcd(r,b) ，符号gcd(a,b)表示a,b的最大公约数，算法时间复杂度O(logb)
- int g(int a , int b) //递归实现
- {
- return (b? g(b , a%b ) : a);
- }
- int g(int a , int b) //非递归实现
- {
- while (b){ int t = a % b; a = b; b = t; } //辗转相除
- return a;
- }
六：最小公倍数：lcm(a,b) = a*b/gcd(a,b)
七：同余运算基本定理：
例子：100-60除以8正好除尽，我们就说100和60对于模数8同余 =>可以把它写成 100≡60(mod 8)
a mod 3 = 1 -> a≡1(mod 3)
性质：如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m)。
证明：条件告诉我们，可以找到p和q使得a-mp = b-mq，也存在r和s使得x-mr = y-ms。于是a-mp + x-mr = b-mq + y-ms，即a+x-m(p+r) = b+y-m(q+s)，这就告诉我们a+x和b+y除以m的余数相同。
容易想到，两个同余式对应相乘，同余式两边仍然相等：
如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)。
证明：条件告诉我们，a-mp = b-mq，x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms)，等式两边分别展开后必然是ax-m(...) = by-m(...)的形式，这就说明ax≡by(mod m)。
证明：条件告诉我们，a-mp = b-mq，x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms)，等式两边分别展开后必然是ax-m(...) = by-m(...)的形式，这就说明ax≡by(mod m)。
八：互素性质：又可以称为互质,若两正整数的最大公约数为1，那么这两个数为互素关系
九.梅森素数：
对于p=2，3，5，7，13，17，19，31，67，127和257，2p-1都是素数，而对于其它小于257的素数p，2p-1都是合数。今天我们把形如M_p=2p-1的素数叫做梅森素数，M_p中的M就是梅森姓氏的第一个字母