[学习笔记23] 简单数论定理及其证明
Imaginative
·
2025-08-17 09:08:13
·
个人记录
前置小定理
定理1 ~~~~~gcd(a,b)=gcd(a-b,b)(a≥b)
证1:
设 gcd(a,b)=d ，则 a=k_1d , b=k_2d(k_1、k_2互质)
a-b=(k_1-k_2)d
因为未知(k_1-k_2) 与 k2 是否互质，因此
gcd(a-b,b)≥d
证2
设 gcd(a-b,b)=t ，则 (a-b)=k_3t , b=k_4t
a=(a-b)+b=k_3t+k_4t=(k_3+k_4)t
同理未知(k_3+k_4) 与 k4 是否互质，因此
gcd(a,b)≥t
证3
综合证1证2，
gcd(a-b,b)≥gcd(a,b)~~~~~~~~gcd(a,b)≥gcd(a-b,b)
gcd(a-b,b)=gcd(a,b)
定理2~~~~~gcd(a,b)=gcd(a %b,b)(a≥b)
设 a=kb+r ,即证 gcd(a,b)=gcd(r,b)
证1:
r=a-kb
设 gcd(a,b)=d ，则 a=k_1d , b=k_2d(k_1、k_2互质)
r=k_1d-kk_2d=d(k_1-kk_2)
因为未知(k_1-kk_2) 与 k2 是否互质，因此
gcd(r,b)≥d
证2
设 gcd(r,b)=t ，则 r=k_3t , b=k_4t
a=kb+r=kk_4t+k_3t=(kk_4+k_3)t
同理未知(k_3+kk_4) 与 k4 是否互质，因此
gcd(a,b)≥t
证3
综合证1证2，
gcd(r,b)≥gcd(a,b)~~~~~~~~~~~~~~~~gcd(a,b)≥gcd(r,b)
gcd(a~mod~b,b)=gcd(a,b)
裴蜀定理
内容: 有不定方程 ax+by=c(c>0) , a,b 为不全为0的整数。若其有整数解，则 gcd(a,b)|c , c 的最小取值为 gcd(a,b) .
证明：
设 ax+by 的最小值为 d , 设此时的解为 x_0,y_0
ax_0+by_0=d
设 a=dq+r(0≤r<d)
r=a-dq=a-(ax_0+by_0)q=a(1-x_0q)+b(-y_0q)
若 r>0 , 则说明存在 x=(1-x_0q),y=(-y_0q) ,且 r<d ,说明 ax+by 的最小值应为 r 而非 d ,矛盾。
则 r=0 ,即 d|a 同理可得 d|b
现已知 d 是 a,b 的公约数，设 c 是 a,b 的任意公约数，易知
c|ax_0~~~~~~~~~~与~~~~~~~~~~ c|by_0
c|(ax_0+by_0)~~->~c|d
所以 d 是 a,b 的最大公约数
重要推论
a,b$ 互质的充要条件是存在整数$x,y$ ,使 $ax+by=1
通解构造
\left\{
\begin{aligned}
x=x_0+b/d*k\\
y=y_0-a/d*k
\end{aligned}
\right.
费马小定理
前置定理1
ac≡bc\pmod m$ 且 $\gcd(c,m)=1$ ，则 $a≡b\pmod m
证明
ac-bc≡0\pmod m
c(a-b)≡0\pmod m
$$a-b≡0\pmod m$$
$$a≡b\pmod m$$
### 前置定理2
若 $gcd(a,m)=1$ ，则{$0,a,2a,3a,...,(m-1)a$} 是模 $m$ 的完全剩余系。
**证明**
假设存在 $pa≡qa\pmod m(p\not≡q\pmod m)
(q-p)a≡0\pmod m
$$q-p≡0\pmod m$$
$$q≡p\pmod m$$
矛盾，证毕
**费马小定理内容：**
$$a^{p-1}≡1\pmod p(p为质数且p∤a)$$
**证明**
模 $p$ 的余数集合是 $[1,p-1]$ 的排列，因此
$$a\times 2a\times 3a\times ...(p-1)a≡\prod_{i=1}^{p-1}i \pmod p$$
$$a^{p-1}(p-1)!≡(p-1)!\pmod p$$
$(p-1)!$ 与 $p$ 互质
$$a^{p-1}≡1\pmod p$$
# 逆元
$$a^{p-1}≡1\pmod p$$
$$a\times a^{p-2}≡1\pmod p$$
$a,a^{p-2}$ 互为模 $p$ 下的逆元
### 唯一性证明
## exgcd
考虑辗转相除法
$$ax+by=\gcd(a,b)$$
$$bx_1+(a~mod~b)y1=\gcd(b,a~mod~b)$$
$$......$$
$$\gcd(a,b)x_n+0y_n=gcd(gcd(a,b),0)$$
显然 $x=1,y=0$ 是最后一个式子的一组解
考虑回溯，设$a=bq+r(0\leq r<b)(q=⌊a/b⌋)$ ,有
$$ax+by=\gcd(a,b)(上层)$$
$$bx_0+ry_0=\gcd(b,r)(下层)$$
联立
$$ax+by=bx_0+ry_0$$
可推$$r=a-bq$$
$$ax+by=bx_0+(a-bq)y_0$$
$$ax+by=ay_0+b(x_0-qy_0)$$
故$$x=y_0,y=x_0-qy_0$$
实现
```cpp
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int x1,y1;
int k=exgcd(b,a%b,x1,y1);
x=y1,y=x1-a/b*y1;
return k;
}
```
### 求逆元
若 $a$ 与 $p$ 互质，根据裴蜀定理，存在 $ax+py=1$ ，即$ax≡1\pmod p
求出 [0,p) 之间的 x 即可。exgcd 可求出 p 不为质数的情况。
线性递推逆元
注意，最终求出来是负数，要用模数加上转为正数
for (int i = 2; i <= n; i++){
inv[i]=(p-(p/i)*inv[p%i])%p;
}
中国剩余定理
内容: 给定一组两两互质的正整数 m_1..m_n ，以及任意正整数 a_1...a_n ，求一个正整数 x ,满足
\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\dots\\x\equiv a_n\pmod{m_n}\end{cases}
中国剩余定理指出在模 M=\prod_{i=1}^n m_i 下有唯一解
x≡\sum_{i=1}^n a_i\times M_i\times y_i \pmod M
证明:
易知 gcd(M_i,m_i)=1 ,由裴蜀定理：
M_iy_i≡1\pmod m
其中 y_i 为 M_i 在模 m 下的逆元
再定义：
x=\sum_{j=1}^n a_jM_jy_j
我们要验证 x≡a_i\pmod{m_i}
对于一个固定的 i ，我们做分讨
i=j$ 时，显然该项模 $m_i$ 为 $a_i$ $(M_iY_i≡1\pmod{m_i})
i\neq j$ 时，$M_j$ 有因子 $m_i$ 因此该项模 $m_i$ 为 $0
相加起来正确性显然。
唯一性证明:
命题：若 x,x' 均为方程组的解，则 x≡x'\pmod M
假设存在两个解
x≡a_i\pmod{m_i}~~~~~~~~~~~x'≡a_i\pmod{m_i}
x-x'≡0\pmod{m_i}~~~~~~即~~~~~~~m_i|x-x'
因为 m_i 两两互质
M|x-x'->x-x'≡0\pmod{M}->x≡x'\pmod{M}
扩展中国剩余定理
去除了 m_i 互质的条件,具体实现通过合并两个方程为一个新方程，逐步减少方程数量，最终得到解。
合并
\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\end{cases}
等价于
x=k_1m_1+a_1=k_2m_2+a_2(k1,k2∈\Z)
k_1m_1-k_2m_2=a_2-a_1
可看成线性丢番图方程(ax+by=c;x=k_1,y=k_2 )
若方程有解，需满足 \gcd(m_1,m_2)|(a_2-a_1)
剩余在左右同时除以 gcd 后使用 exgcd
卢卡斯定理
内容： 设 p 为质数， n 和 k 的 p 进制展开为:
n=\sum_{i=0}^m n_ip^i~~~~~~~~~~~~~~~~k=\sum_{i=0}^m k_ip^i
则：
\begin{pmatrix}n\\k\end{pmatrix}≡\prod_{i=0}^m\begin{pmatrix}n_i\\k_i\end{pmatrix}\pmod p
也可写成：
\begin{pmatrix}n\\k\end{pmatrix}≡\begin{pmatrix}\lfloor n/p\rfloor\\\lfloor k/p\rfloor\end{pmatrix}\begin{pmatrix}n~mod ~p\\k~mod~p\end{pmatrix}\pmod p
前置小定理
(1+x)^{qp}≡(1+x^p)^q\pmod p
证明： 根据费马小定理
x^p≡x\pmod p
因此对于多项式 f(x)=1+x ,有：
f(x)^p≡1+x≡1+x\times x^{p-1}≡1+x^p\pmod p
两边同时取 q 次方
f(x)^{p^q}=f(x)^{pq}≡(1+x^p)^q \pmod p
证毕
卢卡斯定理证明：
若n<p且k<p ,此时n=n_0,k=k_0 定理退化为
\begin{pmatrix}n\\k\end{pmatrix}≡\begin{pmatrix}n_0\\k_0\end{pmatrix}\pmod p
显然成立
若对于所有n'<n ，即对于 n'=\lfloor n/p\rfloor,k'=\lfloor k/p\rfloor ，有
\begin{pmatrix}\lfloor n/p\rfloor\\\lfloor k/p\rfloor\end{pmatrix}≡\prod_{i=1}^m\begin{pmatrix}n_i\\k_i\end{pmatrix}\pmod p
我们需要证明其对 n 成立，设
n=qp+r,k=sp+t(q=\lfloor n/p\rfloor,r=n~mod~~p,s=\lfloor k/p\rfloor,r=k~mod~~p)
引入刚刚的定理
(1+x)^n=(1+x)^{qp+r}=(1+x)^{qp}(1+x)^r≡(1+x^p)^q(1+x)^r\pmod p
比较两边 x^k 的系数
左边系数为\begin{pmatrix}n\\k\end{pmatrix}
右边(1+x^p)^q(1+x)^r 中，x^k=x^{sp+t} 的系数为
\begin{pmatrix}q\\s\end{pmatrix}\begin{pmatrix}r\\t\end{pmatrix}
这是因为
(1+x)^r$ 贡献 $x^t$ 的系数$\begin{pmatrix}r\\t\end{pmatrix}
则
\begin{pmatrix}n\\k\end{pmatrix}≡\begin{pmatrix}q\\s\end{pmatrix}\begin{pmatrix}r\\t\end{pmatrix}\pmod p
根据假设
\begin{pmatrix}q\\s\end{pmatrix}≡\prod_{i=1}^m\begin{pmatrix}n_i\\k_i\end{pmatrix}\pmod p
易知\begin{pmatrix}r\\t\end{pmatrix}=\begin{pmatrix}n_0\\k_0\end{pmatrix}
所以
\begin{pmatrix}n\\k\end{pmatrix}≡\prod_{i=0}^m\begin{pmatrix}n_i\\k_i\end{pmatrix}\pmod p