常用数学结论证明汇总
简单事实
- \(\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\) 的阶数为 \[ \Large ord = \frac{\phi(p)}{\gcd(\phi(p),\log_g(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(n*m) = \phi(n) *\phi(m)\)
证明一
考虑若干个同余方程组 \[ x ≡ r_1 \pmod n\\ x ≡ r_2 \pmod 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(n*m) \ge \phi(n) *\phi(m)\)
再证明 \(\forall\ x\in T\)，可以对应一个以上同余方程组的解，假设不对应，那么它一定与 \(n,m\) 中的一个不互质，由事实 1 推出矛盾。
故 \(\phi(n*m) \le \phi(n) *\phi(m)\)
证毕。
证明二
欧拉定理
内容
\[ \Large 若 \ \gcd(a,m)= 1 ,\ 则\ a^{\phi(m)}≡1\mod 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\)
扩展欧拉定理
内容
\[ \Large 若 \ b≥φ(m) ,\ 则\ a^b≡a^{b \mod φ(m) +φ(m)}\mod m \]
证明
对 \(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)\)。