良序性质(The Well-Ordering Property)

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

数学归纳法(Mathematical Induction)

原理：一个包含整数1的正整数集合如果具有如下性质，即若其包含整数k,则其也包含整数k + 1，那么这个集合一定是所有正整数的集合。
证明：S是包含整数1的正整数集合，并且如果它包含整数n，则一定包含n + 1（良序性）
步骤：

1. 设集合S为命题成立的正整数集合，且1属于S（命题对1为真）
2. 证明对每个正整数n，如果n属于S，则n+1也属于S
3. 由数学归纳原理可得结论

例：证n! <= n^n
当n = 1时，由于1! = 1 <= 1^1，命题成立。（基础步骤）
假设n! <= n^n，(归纳假设)
(n + 1)! = (n + 1)n! <= (n + 1)n^n < (n + 1)(n + 1)^n = (n + 1)^(n + 1) （归纳步骤）
因此n! <= n^n

第二数学归纳原理

对于包含1的正整数集合，如果它具有下述性质：对于每个正整数n，如果它包含全体正整数1,2,…n，则它也包含整数n+1，那么这个集合一定是由所有正整数构成的集合。
用途：递归定义：指定f(1)，通过某种规则可从f(n)推出f(n + 1)

素数

素数是大于1的正整数，且除了1和自身外不能被其他正整数所整除。大于1且不是素数的正整数称为合数。

• 1不是素数
• 判断一个数不为素数：若P为素数，则P整除2^p - 2 – Fermat （反之未必，如P=341）
• 每个正整数都可被唯一的写成素数的乘积（按大小升序）

• 素数有无穷个

  丢番图逼近（有理数逼近实数）

  • 实数和与之最接近的整数距离不超过1/2
  • （狄利克雷逼近）实数a的前n个倍数中（1a, 2a, 3*a,…）至少有一个实数与最接近它的整数距离小于1/n。
    （这个整数为[ka] - [ja]，即|{ka} - {ja}| < 1/n, 0<=j<k<=n） ([]表示向下取整，{}表示有理数的小数部分)

  数列 求和 求积

• 前n个正奇数的和为n^2，即 1 + 3 + 5 + … + (2n - 1) = n^2 (数学归纳法)
• 1/1^2 + 1/2^2 + … + 1/n^2 <= 2 - 1/n
• 调和级数: 1/1 + 1/2 + … + 1/n
• 算术平均：A = (a1 + a2 + … + an) / n
• 几何平均：G = (a1a2…an)^1/n
• 第n个斐波那契数为 1/(5^1/2) x (a^n - b^n), a = (1 + (5^1/2)) / 2, b = (1 - (5^1/2)) / 2
• 在线查找整数序列的网站：oeis.org

整除性

a,b为整数且a != 0，则当存在整数c使得 b = ac时称 a 整除 b，a是b的一个因子，b是a的倍数。记为a|b。

• a,b,m,n为整数，且c|a, c|b，则c|(ma + nb)
  例:3|21, 3|33，则3|(521 - 333)，即3|6

带余除法

a, b为整数且b > 0，则存在唯一整数q, r使得a = bq + r, 0 <= r < b. q为商，r为余数，a为被除数，b为除数
q = [a/b], r = a - b[a/b]，a能被b整除当且仅当r = 0。

• 若n为正整数，则对于实数x，有[x/n] = [[x]/n].

最大公因子

整数a,b的最大公因子是指能够同时整除a和b的最大整数。记为(a, b)或gcd(a, b)。特别的，(0, n) = (n, 0) = n, (0, 0) = 0.

互素

若gcd(a, b) = 1，则a与b互素。

四则运算

• 两个n位整数的乘法可通过O(nlognloglogn)次位运算完成(记为M(n))。
• 2n位整数a被整数b(不超过n位)除时，有使用O(M(n))次位运算求商q=[a/b]的算法。
• O(n^log3)的方法：a = 2^n A1 + A0, b = 2^n B1 + B0, 其中A1,B1为高n位，A0,B0为低n位，则
  ab = (2^(2n) + 2^n)A1B1 + 2^n(A1 - A0)(B0 - B1) + (2^n + 1)A0B0
• 快速口算乘法（独创，不用列竖式）：23 45 = 23 5 + (23 * 4)0 = 115 + 920 = 1035
• 当一个整数最后一位为5时，其平方为AnAn-1…A1A0 ^ 2 = (An…An-1 (An…An-1 + 1))25，其中25为其低两位，不是乘法。
  例165^2 = (16 17)25 = (112 + 160)25 = (272)25 = 27225

对数、指数

• a^(logb) = b^(loga)