吉法师的博客

一、整数

1.基础

1.1 良序性质

每个非空的正整数集合都有一个最小元

部分整数集合没有最小元，如小于100的整数，负整数，所有整数。

1.2 证明根号2是无理数

有理数都可以写成p/q的形式，其中p和q是整数

1.3 代数数和超越数

如果x是整系数多项式的根，则称为代数数，如根号2，和任何有理数。

有理数a/b是bx-a的根(a,b是整数且b不为0)，所有有理数是代数数。

如果数a不是代数数，则称为超越数，如π，e（1+1/x)^x的极限

1.4 抽屉原理（鸽笼原理）

抽屉原理I：把n+1个苹果放到n个抽屉里，则至少有一个抽屉中有2个或2个以上的苹果。 抽屉原理II：把mxn+r个苹果放到n个抽屉里，则至少有一个抽屉中有不少于m+l个苹果。

1.5 求和符号

100 ←上界 n ∑ i = 1+2+3+4+5+···+100 i=1↘下界 i

1.6 数学归纳法

数学归纳法需要两个步骤：

1. 设S属于命题里的正整数集合，命题对整数1为真。（基础步骤）

2. 证明对每个正整数n，n属于S则n+1也疏忽S。（归纳步骤)

1.7 斐波那契数列

fn = fn-1 + fn-2

如f3 =f1 + f2 = 1+1 = 2 f4 = 3 f5 = 5 f6 = 8 ……

1.8 整除性

a|b 表示a可以整除b。

1.9 整数运算的复杂度

用大O记法来表示。

2 素数

每一个大于1的正素数都有一个素因子

2.1 素性校验

1. 如果n是一个合数，则n一定有一个不超过根号n的素因子(艾拉托色尼斯筛法)

比如小于100的合数，一定有小于10的素因子，小于10的素数为2，3，5，7，则分别筛去能被2，3，5，7整除的数即可。

2. 梅森素数

形如2^n - 1的素数

3. 哥德巴赫猜想

每一个大于2的正偶数可以写成两个素数的和

4. 欧几里得原理

求(a,b)用辗转相除法，最后一个乘数就是a和b的最大公因数。

2.2 算数基本原理

每一个大于1的正整数都可以被唯一地写成素数的乘积，在乘积中的素因子按照非降序排列。

2.3 因子分解法

试除法

设n是42833，n不能被2，3，5整除，但是7|n，得到42833 = 7 * 6119

6119不能被7，11，13，17，19，23整除，但6119 = 29 * 211

因为 29 >= 根号211 ，所以211是素数，42833 = 7 * 29 * 211

这个方法的素因式分解效率很低。

2.4 特殊的同余式

威尔逊定理

当p是素数时，(p-1)! 可以被p整除