算数基本定理：
正整数 \(N\) 可以被唯一分解为 \(N = p_1^{c_1} \times p_2^{c_2} \times p_3^{c_3} \times\cdots \times p_k^{c_k}\)。
性质：
\(N\) 的正约数个数： \(\prod_{i=1}^k (c_i+1)\)
\(N\) 的正约数和：\(\prod_{i=1}^k\big(\sum_{j=0}^{c_i}p_i^j\big)\)
九章算术·更相减损术：
\(\forall a,b \in N\)，有 \(\gcd(a,b) = \gcd(b,a-b) = \gcd(a,a-b)\)
欧几里得算法：
\(\forall a,b \in N,b \ne 0\)，有 \(\gcd(a,b) = \gcd(b,a \bmod b)\)
欧拉函数：
\(\varphi(N)\) 为小于等于 \(N\) 的所有正整数中与 \(N\) 互质的数的数目，
\[\varphi(N) = N \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times \cdots \times \frac{p_k-1}{p_k} = N \times \prod_{i=1}^k (1-\frac{1}{p_i}) \]证明：\(1 \sim N-1\) 中不含 \(p\) 或 \(q\) 质因子的个数为
\[N - \frac{N}{p} - \frac{N}{q} + \frac{N}{p \times q} = N \times (1 - \frac{1}{p}) \times (1 - \frac{1}{q}) \]对所有质因子做容斥即可。
性质：
- \(\forall n > 1\)，\(1 \sim n\) 中于 \(n\) 互质的数的和为 \(n \times \varphi(n)/2\)
- 若 \(\gcd(a,b)=1\)，则 \(\varphi(ab)=\varphi(a)\varphi(b)\)
- 设 \(p\) 为质数，若 \(p|n\) 且 \(p^2|n\)，则 \(\varphi(n)=\varphi(n/p)\times p\)
- 设 \(p\) 为质数，若 \(p|n\) 且 \(p^2\nmid n\)，则 \(\varphi(n)=\varphi(n/p)\times (p-1)\)
- \(\sum_{d/n} \varphi(d)=n\)
性质 \(1\) 证明：
有 \(\gcd(n,x)=\gcd(n,n-x)\)，所以与 \(n\) 不互质的数 \(x,n-x\) 成对出现，平均值为 \(n/2\)，所以与 \(n\) 互质的数平均值也为 \(n/2\)，得到性质 \(1\)。