《数论概论》

本原勾股数组（PPT）：

一个三元组（a, b, c），其中 a, b, c 没有公因数，且满足 a² + b² = c²。
a 和 b 的奇偶性不同 且 c 总是奇数。

c - b 与 c + b 没有公因数 而且 由于 (c - b)(c + b) = a²，所以 c - b 与 c + b 的积是平方数，这种情况只有在 c - b 与 c + b 自身都是平方数时才出现。

勾股数组定理 ：
假设
c + b = s²
c - b = t²
（s > t >= 1 是任意没有公因数的奇数）
每个本原勾股数组（a, b, c）（其中 a 为奇数，b 为偶数）都可从如下公式得出：
a = st
b = (s² - t²) / 2
c = (s² + t²) / 2

费马大定理

n >= 3 时 方程 aⁿ + bⁿ = cⁿ 没有正整数解

推论：x⁴ + y⁴ = z² （x, y, z互素） z 可以看作 c²， 所以这个等式相当于x⁴ + y⁴ = c⁴，由费马大定理得知，x, y, z 没有整数解。

ps：至今没有有效证明，但也没有被推翻

目前已证明 存在无穷多个素数 p 使得 a^p + b^p = c^p 没有解且 p 不整除 abc

GCD

如果 gcd(a, b) = 1，则 a, b 互素。

欧几里得算法

要计算两个整数 a 与 b 的最大公因数， 先令 r_-1 = a 且 r₀ = b，然后计算相继的商和余数
r_i-1 = q_i+1 * r_i + r_i+1 （i = 0, 1, 2, …）
直到某余数 r_n+1为 0，最后的非零余数 r_n 就是 a 和 b 的最大公因数。
欧几里得算法的步数至多是 b 的位数的 7 倍。

线性方程定理

因数分解

素数整除性质

假设素数 p 整除乘积 a₁a₂……a₃，则 p 整除 a₁, a₂, ……, a_r 中至少一个因数。
（对合数不成立）

算术基本定理

每个整数 n >= 2 可唯一分解成素数乘积 n = p₁p₂……p_r
如果 n 自身是素数，则记 n = n 并认为这是由单个素数构成的乘积。
当记作 n = p₁p₂……p_r 时，并非指p₁p₂……p_r 一定是不同的素数。

数 n 可以以某种方式分解成素数乘积。
仅有一种这样的因数分解 （除因数重排外）。

同余式

如果 m 整除 a - b，我们就说 a 与 b 模 m 同余，并记为 a ≡ b (mod m)

具有相同模的同余式在许多方面表现得很像通常的等式

费马小定理

欧拉函数

欧拉公式

欧拉函数公式

中国剩余定理

设 m 与 n 是整数，gcd(m, n) = 1，b 与 c 是任意整数，则同余式组 x ≡ b (mod m) 与 x ≡ c (mod n) 恰有一个解 0 <= x < mn。