专栏文章

[学习笔记23] 简单数论定理及其证明

IImaginative
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioaklyn
此快照首次捕获于
2025/12/02 16:03
3 个月前
此快照最后确认于
2025/12/02 16:03
3 个月前
查看原文

前置小定理

定理1      gcd(a,b)=gcd(a−b,b)(a≥b)~~~~~gcd(a,b)=gcd(a-b,b)(a≥b)

证1:
设 gcd(a,b)=dgcd(a,b)=d，则 a=k1da=k_1d, b=k2d(k1、k2互质)b=k_2d(k_1、k_2互质)
a−b=(k1−k2)da-b=(k_1-k_2)d
因为未知(k1−k2)(k_1-k_2) 与 k2k2 是否互质，因此
gcd(a−b,b)≥dgcd(a-b,b)≥d
证2
设 gcd(a−b,b)=tgcd(a-b,b)=t ，则 (a−b)=k3t(a-b)=k_3t, b=k4tb=k_4t
a=(a−b)+b=k3t+k4t=(k3+k4)ta=(a-b)+b=k_3t+k_4t=(k_3+k_4)t
同理未知(k3+k4)(k_3+k_4) 与 k4k4 是否互质，因此
gcd(a,b)≥tgcd(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)~~~~~~~~gcd(a,b)≥gcd(a-b,b)
gcd(a−b,b)=gcd(a,b)gcd(a-b,b)=gcd(a,b)

定理2     gcd(a,b)=gcd(a~~~~~gcd(a,b)=gcd(a%b,b)(a≥b)b,b)(a≥b)

设 a=kb+ra=kb+r ,即证 gcd(a,b)=gcd(r,b)gcd(a,b)=gcd(r,b)
证1:
r=a−kbr=a-kb
设 gcd(a,b)=dgcd(a,b)=d ，则 a=k1da=k_1d , b=k2d(k1、k2互质)b=k_2d(k_1、k_2互质)
r=k1d−kk2d=d(k1−kk2)r=k_1d-kk_2d=d(k_1-kk_2)
因为未知(k1−kk2)(k_1-kk_2) 与 k2k2 是否互质，因此
gcd(r,b)≥dgcd(r,b)≥d
证2
设 gcd(r,b)=tgcd(r,b)=t ，则 r=k3tr=k_3t , b=k4tb=k_4t
a=kb+r=kk4t+k3t=(kk4+k3)ta=kb+r=kk_4t+k_3t=(kk_4+k_3)t
同理未知(k3+kk4)(k_3+kk_4) 与 k4k4 是否互质，因此
gcd(a,b)≥tgcd(a,b)≥t
证3
综合证1证2， gcd(r,b)≥gcd(a,b)                gcd(a,b)≥gcd(r,b)gcd(r,b)≥gcd(a,b)~~~~~~~~~~~~~~~~gcd(a,b)≥gcd(r,b) gcd(a mod b,b)=gcd(a,b)gcd(a~mod~b,b)=gcd(a,b)

裴蜀定理

内容: 有不定方程 ax+by=c(c>0)ax+by=c(c>0) , a,ba,b 为不全为0的整数。若其有整数解，则 gcd(a,b)∣cgcd(a,b)|c , cc 的最小取值为 gcd(a,b)gcd(a,b).
证明：
设 ax+byax+by 的最小值为 dd , 设此时的解为 x0,y0x_0,y_0
ax0+by0=dax_0+by_0=d
设 a=dq+r(0≤r<d)a=dq+r(0≤r<d)
r=a−dq=a−(ax0+by0)q=a(1−x0q)+b(−y0q)r=a-dq=a-(ax_0+by_0)q=a(1-x_0q)+b(-y_0q)
若 r>0r>0 , 则说明存在 x=(1−x0q),y=(−y0q)x=(1-x_0q),y=(-y_0q) ,且 r<dr<d ,说明 ax+byax+by 的最小值应为 rr 而非 dd ,矛盾。
则 r=0r=0 ,即 d∣ad|a 同理可得 d∣bd|b
现已知 dd 是 a,ba,b 的公约数，设 cc 是 a,ba,b 的任意公约数，易知 c∣ax0          与          c∣by0c|ax_0~~~~~~~~~~与~~~~~~~~~~ c|by_0 c∣(ax0+by0)  −> c∣dc|(ax_0+by_0)~~->~c|d 所以 dd 是 a,ba,b 的最大公约数

重要推论

a,ba,b 互质的充要条件是存在整数x,yx,y ,使 ax+by=1ax+by=1

通解构造

{x=x0+b/d∗ky=y0−a/d∗k\left\{ \begin{aligned} x=x_0+b/d*k\\ y=y_0-a/d*k \end{aligned} \right.

费马小定理

前置定理1

ac≡bc(modm)ac≡bc\pmod m 且 gcd⁡(c,m)=1\gcd(c,m)=1 ，则 a≡b(modm)a≡b\pmod m
证明
ac−bc≡0(modm)ac-bc≡0\pmod m c(a−b)≡0(modm)c(a-b)≡0\pmod m c,mc,m互质 a−b≡0(modm)a-b≡0\pmod m a≡b(modm)a≡b\pmod m

前置定理2

若 gcd(a,m)=1gcd(a,m)=1 ，则{0,a,2a,3a,...,(m−1)a0,a,2a,3a,...,(m-1)a} 是模 mm 的完全剩余系。
证明
假设存在 pa≡qa(modm)(p≢q(modm))pa≡qa\pmod m(p\not≡q\pmod m)
(q−p)a≡0(modm)(q-p)a≡0\pmod m a,ma,m 互质 q−p≡0(modm)q-p≡0\pmod m q≡p(modm)q≡p\pmod m 矛盾，证毕
费马小定理内容：
ap−1≡1(modp)(p为质数且p∤a)a^{p-1}≡1\pmod p(p为质数且p∤a)
证明
模 pp 的余数集合是 [1,p−1][1,p-1] 的排列，因此 a×2a×3a×...(p−1)a≡∏i=1p−1i(modp)a\times 2a\times 3a\times ...(p-1)a≡\prod_{i=1}^{p-1}i \pmod p ap−1(p−1)!≡(p−1)!(modp)a^{p-1}(p-1)!≡(p-1)!\pmod p (p−1)!(p-1)! 与 pp 互质 ap−1≡1(modp)a^{p-1}≡1\pmod p

逆元

ap−1≡1(modp)a^{p-1}≡1\pmod p a×ap−2≡1(modp)a\times a^{p-2}≡1\pmod p a,ap−2a,a^{p-2} 互为模 pp 下的逆元

唯一性证明

exgcd

考虑辗转相除法 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) bx1+(a mod b)y1=gcd⁡(b,a mod b)bx_1+(a~mod~b)y1=\gcd(b,a~mod~b) ............ gcd⁡(a,b)xn+0yn=gcd(gcd(a,b),0)\gcd(a,b)x_n+0y_n=gcd(gcd(a,b),0) 显然 x=1,y=0x=1,y=0 是最后一个式子的一组解
考虑回溯，设a=bq+r(0≤r<b)(q=⌊a/b⌋)a=bq+r(0\leq r<b)(q=⌊a/b⌋) ,有 ax+by=gcd⁡(a,b)(上层)ax+by=\gcd(a,b)(上层) bx0+ry0=gcd⁡(b,r)(下层)bx_0+ry_0=\gcd(b,r)(下层) 联立 ax+by=bx0+ry0ax+by=bx_0+ry_0 可推r=a−bqr=a-bq ax+by=bx0+(a−bq)y0ax+by=bx_0+(a-bq)y_0 ax+by=ay0+b(x0−qy0)ax+by=ay_0+b(x_0-qy_0) 故x=y0,y=x0−qy0x=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;
}

求逆元

若 aa 与 pp 互质，根据裴蜀定理，存在 ax+py=1ax+py=1 ，即ax≡1(modp)ax≡1\pmod p
求出 [0,p)[0,p) 之间的 xx 即可。exgcdexgcd 可求出 pp 不为质数的情况。

线性递推逆元

注意，最终求出来是负数，要用模数加上转为正数
CPP
for (int i = 2; i <= n; i++){
  inv[i]=(p-(p/i)*inv[p%i])%p;
}

中国剩余定理

内容: 给定一组两两互质的正整数 m1..mnm_1..m_n，以及任意正整数 a1...ana_1...a_n，求一个正整数 xx,满足
{x≡a1(modm1)x≡a2(modm2)…x≡an(modmn)\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=∏i=1nmiM=\prod_{i=1}^n m_i 下有唯一解 x≡∑i=1nai×Mi×yi(modM)x≡\sum_{i=1}^n a_i\times M_i\times y_i \pmod M
  • 其中 Mi=M/miM_i=M/m_i
  • yiy_i 是 MiM_i 模 mim_i 的逆元
证明:
易知 gcd(Mi,mi)=1gcd(M_i,m_i)=1 ,由裴蜀定理： Miyi≡1(modm)M_iy_i≡1\pmod m 其中 yiy_i 为 MiM_i 在模 mm 下的逆元
再定义： x=∑j=1najMjyjx=\sum_{j=1}^n a_jM_jy_j
我们要验证 x≡ai(modmi)x≡a_i\pmod{m_i}
对于一个固定的 ii ，我们做分讨
  • i=ji=j 时，显然该项模 mim_i 为 aia_i (MiYi≡1(modmi))(M_iY_i≡1\pmod{m_i})
  • i≠ji\neq j 时，MjM_j 有因子 mim_i 因此该项模 mim_i 为 00
相加起来正确性显然。
唯一性证明:
命题：若 x,x′x,x' 均为方程组的解，则 x≡x′(modM)x≡x'\pmod M
假设存在两个解 x≡ai(modmi)           x′≡ai(modmi)x≡a_i\pmod{m_i}~~~~~~~~~~~x'≡a_i\pmod{m_i} x−x′≡0(modmi)      即       mi∣x−x′x-x'≡0\pmod{m_i}~~~~~~即~~~~~~~m_i|x-x' 因为 mim_i 两两互质 M∣x−x′−>x−x′≡0(modM)−>x≡x′(modM)M|x-x'->x-x'≡0\pmod{M}->x≡x'\pmod{M}

扩展中国剩余定理

去除了 mim_i 互质的条件,具体实现通过合并两个方程为一个新方程，逐步减少方程数量，最终得到解。

合并

{x≡a1(modm1)x≡a2(modm2)\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\end{cases} 等价于 x=k1m1+a1=k2m2+a2(k1,k2∈Z)x=k_1m_1+a_1=k_2m_2+a_2(k1,k2∈\Z) k1m1−k2m2=a2−a1k_1m_1-k_2m_2=a_2-a_1 可看成线性丢番图方程(ax+by=c;x=k1,y=k2ax+by=c;x=k_1,y=k_2)
若方程有解，需满足 gcd⁡(m1,m2)∣(a2−a1)\gcd(m_1,m_2)|(a_2-a_1)
剩余在左右同时除以 gcdgcd 后使用 exgcdexgcd

卢卡斯定理

内容： 设 pp 为质数， nn 和 kk 的 pp 进制展开为: n=∑i=0mnipi                k=∑i=0mkipin=\sum_{i=0}^m n_ip^i~~~~~~~~~~~~~~~~k=\sum_{i=0}^m k_ip^i 则： (nk)≡∏i=0m(niki)(modp)\begin{pmatrix}n\\k\end{pmatrix}≡\prod_{i=0}^m\begin{pmatrix}n_i\\k_i\end{pmatrix}\pmod p 也可写成： (nk)≡(⌊n/p⌋⌊k/p⌋)(n mod pk mod p)(modp)\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+xp)q(modp)(1+x)^{qp}≡(1+x^p)^q\pmod p 证明： 根据费马小定理 xp≡x(modp)x^p≡x\pmod p 因此对于多项式 f(x)=1+xf(x)=1+x ,有： f(x)p≡1+x≡1+x×xp−1≡1+xp(modp)f(x)^p≡1+x≡1+x\times x^{p-1}≡1+x^p\pmod p 两边同时取 qq 次方 f(x)pq=f(x)pq≡(1+xp)q(modp)f(x)^{p^q}=f(x)^{pq}≡(1+x^p)^q \pmod p 证毕
卢卡斯定理证明：
若n<p且k<pn<p且k<p,此时n=n0,k=k0n=n_0,k=k_0定理退化为 (nk)≡(n0k0)(modp)\begin{pmatrix}n\\k\end{pmatrix}≡\begin{pmatrix}n_0\\k_0\end{pmatrix}\pmod p 显然成立 若对于所有n′<nn'<n，即对于 n′=⌊n/p⌋,k′=⌊k/p⌋n'=\lfloor n/p\rfloor,k'=\lfloor k/p\rfloor，有 (⌊n/p⌋⌊k/p⌋)≡∏i=1m(niki)(modp)\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 我们需要证明其对 nn 成立，设 n=qp+r,k=sp+t(q=⌊n/p⌋,r=n mod  p,s=⌊k/p⌋,r=k mod  p)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+xp)q(1+x)r(modp)(1+x)^n=(1+x)^{qp+r}=(1+x)^{qp}(1+x)^r≡(1+x^p)^q(1+x)^r\pmod p 比较两边 xkx^k 的系数
  • 左边系数为(nk)\begin{pmatrix}n\\k\end{pmatrix}
  • 右边(1+xp)q(1+x)r(1+x^p)^q(1+x)^r 中，xk=xsp+tx^k=x^{sp+t} 的系数为 (qs)(rt)\begin{pmatrix}q\\s\end{pmatrix}\begin{pmatrix}r\\t\end{pmatrix} 这是因为
  • (1+xp)q(1+x^p)^q 贡献 xspx^{sp} 的系数 (qs)\begin{pmatrix}q\\s\end{pmatrix} (二项式定理)
  • (1+x)r(1+x)^r 贡献 xtx^t 的系数(rt)\begin{pmatrix}r\\t\end{pmatrix}
则 (nk)≡(qs)(rt)(modp)\begin{pmatrix}n\\k\end{pmatrix}≡\begin{pmatrix}q\\s\end{pmatrix}\begin{pmatrix}r\\t\end{pmatrix}\pmod p 根据假设 (qs)≡∏i=1m(niki)(modp)\begin{pmatrix}q\\s\end{pmatrix}≡\prod_{i=1}^m\begin{pmatrix}n_i\\k_i\end{pmatrix}\pmod p 易知(rt)=(n0k0)\begin{pmatrix}r\\t\end{pmatrix}=\begin{pmatrix}n_0\\k_0\end{pmatrix}
所以 (nk)≡∏i=0m(niki)(modp)\begin{pmatrix}n\\k\end{pmatrix}≡\prod_{i=0}^m\begin{pmatrix}n_i\\k_i\end{pmatrix}\pmod p

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...