分数的和取模
考虑两个分数 $frac ab, frac cd$（$a,b, c, din mathbb{Z}$，$b,d > 0$），正整数 $m$ 和 $b, d$ 都互质。若正整数 $x$ 与 $m$ 互质，用 $x^{-1}$ 表示 $x$ 在模 $m$ 下的逆元。则有
$ab^{-1} + cd^{-1} equiv (ad + bc) (bd)^{-1} pmod{m}$
这意味着满足上述条件的两个分数相加时，先对分数取模再相加和先把两分数相加再取模结果相等。
线性时间求逆元
对于素数 $p$，可以在线性时间内求出 $1, 2, dots, p-1$ 在模 $p$ 下的逆元。
首先有 $1^{-1} = 1 pmod{p}$，对于 $ 2 le i < p$，设 $ p = ki + r$（$0< r < i$），即
[ ki + r = 0 pmod{p} ]
两边同乘以 $i^{-1} r^{-1}$，有
[
kr^{-1} + i^{-1} = 0 pmod{p}
]
于是
[
i^{-1} = - kr^{-1} = - lfloor p/i
floor r^{-1} pmod{p}
]
其中 $r^{-1}$ 已经求出。
关于欧拉函数的一个等式
[ sum_{dmid n} varphi(d) = n ]
证明：令 $S_d$ 为与 $d$ 互质的正整数的集合，即 $S_d = { x in mathbb{Z}^+ mid x le d, gcd(x, d) = 1 } $ 。再令 $T_d = {frac{x}{d} mid x in S_d}$，则 $T_d$ 是以 $d$ 为分母的最简真分数的集合（$T_1={ 1 }$ 除外）。所以有
$$ igcup_{dmid n} T_d = left{frac1n, frac2n, dots, frac{n-1}{n}, frac{n}{n} ight} $$
从而有
[ sum_{dmid n} varphi(d) = n ]
证毕。
费马小定理
若 $p$ 是素数, 对任意整数 $x$ 有 $x^p equiv x pmod{p}$.
特别地，若 $p
mid x$，$x^p equiv x pmod{p} iff x^{p-1} equiv 1 pmod{p}$
欧拉函数
$phi(n)$：与 $n$ 互质且不超过 $n$ 的正整数的个数。
$phi(n) := |{kcolon 1le kle n, gcd(k,n)=1}|$
-
对于正整数 $a$, $b$（$b mid a$）, 满足 $gcd(a,x)=b$ 的正整数 $x$ 的个数是 $phi(frac{a}{b})$.
-
任意正整数 $n$ 至多有 $1$ 个大于等于 $sqrt{n}$ 的素因子。
-
对于非负整数 $a (a>0), b (0 le b < a), c$, 满足
$$
egin{cases}
x mod a = b \
x le c
end{cases}
$$
的非负整数 $x$ 的数目为(c-b)/a + (c>=b)
分析:
$$x mod a=b quad Longrightarrow quad x= ka + b , k ge 0 $$
$$ ka+b le c quad Longrightarrow quad ka le c-b quad Longrightarrow quad k le dfrac{c-b}{a} $$
注意:
- 当$c ge b$时, $k$可以取$0$.
- 当$c<b$时, (c-b)/a == 0.
- 当要求$x>0$时, 答案要改成(c-b)/a + (c>=b && b>0)
逆元
设 $a, b, m$ 是三个正整数，若 $ab equiv 1 pmod{m}$ 则称 $a, b$ 互为模 $m$ 下的逆元。
$ab equiv 1 pmod{m}$ 等价于存在整数 $k$ 使得 $ ab = km + 1$ 即
$$ab - km = 1$$
换言之，$a$ 在模 $m$ 下的逆元 $b$ 存在等价于不定方程
egin{equation}
ax + my = 1 label{Eq:1}
end{equation}
有解。
而方程 eqref{Eq:1} 有解的充要条件为 $gcd(a,m) = 1$；这一论断可由求最大公约数的辗转相除法构造性地证明。
对商取模
设有正整数 $a, b$ 满足 $bmid a$，求 $ frac{a}{b}mod p$，$p$ 是个素数。
解法：先求出 $a,b$ 中 $p$ 的幂次，设 $a = alpha p^{i}$，$b=eta p^{j}$，显然有 $ige j$ 。
考虑 $i=j$ 的情形，此时有 $frac{a}{b} = frac{alpha}{eta}$ ；又 $gcd(eta, p) = 1$，故 $eta$ 在模 $p$ 下的逆元存在。
Wilson's theorem
Let $p$ be an integer greater than one. $p$ is prime if and only if $(p-1)! = -1 pmod{p}$.
This beautiful result is of mostly theoretical value because it is relatively difficult to calculate $(p-1)!$. In contrast, it is easy to calculate $ a^{p-1}$, so elementary primality tests are built using Fermat's Little Theorem rather than Wilson's.
证明：对 $p$ 用数学归纳法。易证 $p = 2, 3, 4$ 时命题成立。设 $p>4$，若 $p$ 是合数，则有 $gcd(p, (p-1)!) = p$ 。从而 $(p-1)! = 0
e -1 pmod{p}$ 。
为何 $gcd(p, (p-1)!) = p$？
若存在 $1< a < b < p$ 使得 $p = ab$ 则结论显然成立；否则有 $p = q^2$，$q$ 是素数且 $q>2$ ，故 $q < 2q < p$， 结论亦成立。
$p$ 是合数时的另一个证明
反证法。假设 $(p-1)! = -1 pmod{p}$ 。
由于 $p$ 是合数，在 $2$ 到 $p-2$ 之间必有一个数 $d$ 是 $p$ 的因子。从而有
$$(p-1)! = -1 pmod{p} Longrightarrow (p-1)! = -1 pmod{d}$$
（注：之前我对这个式子不敏感，这是因为我对【同余】这个概念理解得不够深刻。）
而这与 $(p-1)! = 0 pmod{d}$ 相矛盾，因为 $0 = -1 pmod{d}$ 不可能。
若 $p$ 是质数，考虑 $1$ 到 $p-1$ 中的每个数 $a$ 在模 $p$ 下的逆元 $a^{-1}$。显然 $a$ 的逆元在模 $p$ 下唯一，且 $ a^{-1} = b^{-1} iff a = b$ 。另外，只有在 $a=1$ 或 $a = p-1$ 时才有 $a = a^{-1} $ 。将 $ 2, 3, dots, p-1, p-2$ 按 $a$ 和 $a^{-1}$ 两两配对，有
$$
prod_{a=2}^{p-2} a = 1 pmod{p}
$$
从而有
$$(p-1)! equiv p-1 pmod{p}$$
为何只有在 $a=1$ 或 $a = p-1$ 时才有 $a = a^{-1} $？
$a^2 = 1 pmod{p} iff a^2 -1 = 0 pmod{p} iff (a-1)(a+1) = 0 pmod{p}$
$iff a = 1pmod{p}$ 或 $a=-1pmod{p}$