简单事实
- $\gcd(a,x_1)=1,\gcd(a,x_2)=1 \iff \gcd(a,x_1x_2)$
- 若 $n\ |\ m$ 则 $\phi(n)\ |\ \phi(m)$
- 若 $\gcd(a,p)=1$,则 $ax,x \in [1,p]$ 模 $p$ 意义下互不相同，反之亦然。
模运算和满足的运算率
注：符号均为模 $p$ 意义下。
- 加法交换律
- 加法结合律
- 乘法交换律
- 乘法结合率
- 如果 $p$ 为质数 ，$g$ 为 $p$ 的一个原根，则 $\log_x(y) = \frac{\log_g(y)}{\log_g(x)} \pmod {p-1}$
复数运算满足的运算性质
- 加法交换律
- 加法结合律
一些抽象代数内容
事实1
令 $g$ 为 $p$ 的一个原根，记 $\log_g(x) = y$，模 $p$ 意义下 $x$ 的阶数为
证明1
显然 $g$ 的阶数为 $\phi(p)$，又因为 $g^y = x$。所以 $x^{ord} = 1$。
然后证明 $x^i,i \in [1,ord]$ 互不相同。
反证，如果相同，设为 $i,j(i\ge j)$，那么 $g^{yi} = g^{yj}$ 得到 $\phi(x) |\ y(i-j)$ 两边同时除以 $\gcd(\phi(p),y)$，得到 $ord |\ y’(i-j)$，其中 $\gcd(y’,ord) = 1$ ，得出 $i-j \ge ord$ 矛盾。
所以 $x$ 的阶数为 $ord$
裴蜀定理
内容
$\exist\ x,y \in \Z$ 使得 $ax+by=\gcd(x,y)$
证明
归纳构造。
先证明 $\exist\ x’,y’\in \Z$ 使得 $bx’+(a\%b)y’ = \gcd(a,b)$
即 $ay’ + b(x’-\big\lfloor\dfrac{a}{b}\big\rfloor y’) = \gcd(a,b)$
构造 $x = y’,y=x’- \big\lfloor\dfrac{a}{b}\big\rfloor y’$ 即可满足条件。
递归证明构造式子，得到边界证明 $\exist \ x,y$ 使得 $\gcd(a,b)x + 0 \times y =\gcd(a,b)$
令 $x=1,y=0$
欧拉函数是积性函数
即证明若 $\gcd(n,m) =1,$ 则 $\phi(nm) = \phi(n) \phi(m)$
证明一
考虑若干个同余方程组
列出 $n,m,nm$ 意义下的最小缩系 $S_n,S_m,T$
容易证明 $\forall\ r_1\in S_n, r_2 \in S_m$，存在唯一 $x \in [1,nm]$ 是上同余方程组的解，且 $x \in T$。
存在唯一就是 EXCRT， $x\in T$ 由事实 1 显然。
故 $\phi(nm) \ge \phi(n) \phi(m)$
再证明 $\forall\ x\in T$，可以对应一个以上同余方程组的解，假设不对应，那么它一定与 $n,m$ 中的一个不互质，由事实 1 推出矛盾。
故 $\phi(nm) \le \phi(n) \phi(m)$
证毕。
证明二
欧拉定理
内容
证明
考虑模 $m$ 意义下的最小缩系，即最小完全剩余系删去与 $m$ 不互质的元素后的剩余系，记为 $S$。
构造 $T = \{ax,x \in S\}$
可以证明 $T=S$， 若 $\exist\ x_1,x_2$ 使得 $x_1\neq x_2$ 且 $ax_1 ≡ ax_2 \pmod m$ ，因为 $\gcd(a,m)=1$
所以 $m\ |\ x_1 - x_2$，并推出 $x_1 \neq x_2$，故 $T$ 中元素两两不同且均与 $m$ 互质，即为 $S$。
考虑 $T,S$ 中所有元素的乘积，得到 $\prod\limits_{i=1}^{\phi(n)} ax_i ≡ \prod\limits_{i=1}^{\phi(n)} x_i \pmod n$，又因为 $\prod\limits_{i=1}^{\phi(n)} x_i$ 与 $m$ 互质，所以 $a^{\phi(n)} ≡ 1\pmod n$
扩展欧拉定理
内容
证明
对 $m$ 考虑唯一分解定理。
对于任意因子 $p_i^{k_i}$，若与 $a$ 互质，那就有 $a^b≡a^{b \mod φ(m) +φ(m)}\mod p^{k_i}_i$。
如果和 $a$ 不互质，因为 $b\ge \phi(m)$，那么因为有 $b\ge \phi(m)\ge k_i$，所以 $a^b,a^{(b \mod φ(m)) +φ(m)}$ 都是 $p^{k_i}_i$ 的倍数。
得到 $a^b - a^{(b \mod φ(m)) +φ(m)}$ 是 $p_i^{k_i}$ 的倍数，故同余。
原根：
定义：
如果 $x^1,x^2,x^3 \cdots x^{\phi(n)}$ 模 $n$ 意义下互不相同，且 $\gcd(x,n)=1$，则称 $x$ 为 $n$ 的原根。
性质:
质数 $p$ 的原根的方幂能取遍 $[1,p-1]$
求质数的原根
数学大佬证明了一个数 $n$ 的最小正原根不超过 $n^{\frac{1}{4}+\epsilon}$，所以枚举每个数，检查所有 $n$ 的约数是否是 $a$ 的阶，如果不是，那么 $a$ 为一个原根，复杂度 $\sqrt n$，瓶颈在分解质因数。
应用
开离散对数的时候上原根和换底公式有奇效。
原根存在定理
一个数 $x$ 有原根当且仅当 $x= 2,4,p^n,2\times p^n$，其中 $p$ 为奇素数。
证明不会。
中国剩余定理
咕咕咕
平面图欧拉定理
顶点数-边数-连通块数+区域数=1
几何体欧拉定理
顶点数-边数+面数=2
除法下取整相关：
- $\lfloor\frac{a}{b}\rfloor\ge x\iff b\le \lfloor\frac{a}{x}\rfloor$
- 含义：$b=\lfloor\frac{a}{x}\rfloor$ 是满足 $\lfloor\frac{a}{b}\rfloor\ge x$ 的最大的 $b$。
- $\lfloor\frac{a}{b}\rfloor< x \iff b>\lfloor\frac{a}{x}\rfloor$
- 上面那个反过来。
- $\big\lfloor\dfrac{\lfloor\frac{n}{a}\rfloor}{b}\big\rfloor=\lfloor\dfrac{n}{ab}\rfloor$
- 设 $n=kab+r,r< ab$，则 $\lfloor\frac{n}{a}\rfloor<(k+1)b$，自然有 $\big\lfloor\dfrac{\lfloor\frac{n}{a}\rfloor}{b}\big\rfloor\le \lfloor\dfrac{n}{ab}\rfloor$。又因为 $\lfloor\frac{n}{a}\rfloor\ge kb$，因此 $\big\lfloor\dfrac{\lfloor\frac{n}{a}\rfloor}{b}\big\rfloor\ge \lfloor\dfrac{n}{ab}\rfloor$，得证。
余数相关
- 若 $\gcd(x,y)=1,k\in[0,y)$，则 $kx\pmod y$ 互不相同。
- 证明反证法，移到同一边然后是倍数。
解析几何相关
- $(x_0,y_0)$ 关于 $y=x+m$ 的对称点：$(y_0 - m,x_0 + m)$。
- $(x_0,y_0)$ 关于 $y=-x+m$ 的对称点：$(- y_0 + m,- x_0 + m)$。