初等数论

YQD_Q · 2024-07-30 21:38:07 · 算法·理论

前言

以下的资料和证明来自《算法竞赛进阶指南》和《信息学奥林匹克大纲》、OI-Wiki~以及~CSDN~和博客园~(作者标在前面)，也有笔者手推得到的。如果你在阅读时遇到没弄懂的公式或者证明，不妨将有关的知识点连在一起，试着得出结论。若有不足之处，欢迎指出，请将您的意见私信给笔者

整除~\mid ~& 不整除~\nmid

设~a,b~两数，a是不为0(a\ne 0)的整数，b~是整数。

• 若存在整数~k，满足~a\cdot k=b，称~a~是~b~因子（因数）,b~是~a~的倍数，记作~a\mid b，即~b~可被~a~整除。
• 若不存在整数~k，无法满足~a\cdot k=b，记作~a\nmid b，即~b~无法被~a~整除。

整除的性质：

• 若~a\mid b~且~b\mid c，则~a\mid c
• 若~a\mid b~且~a\mid c，则对于任意正整数~x,y，有~a\mid(bx+cy)
• 若~a\mid b，取一个数k(k\ne 0) ，则有~(a\cdot k)\mid(b\cdot k)
• 若~a\mid b~且~b\mid a，则~b=\pm a
• 若~a\mid b~且~b\ne0，则有~ \left|a\right|~ \mid~\left|b\right|
• 若~a\mid b，则有~a\mid b \Longleftrightarrow -a\mid b\Longleftrightarrow a\mid -b\Longleftrightarrow -a\mid -b
• 若~b=a\cdot k+c，a\mid b~的充分必要条件为~a\mid c

最大公约数(GCD)

定义

• \gcd(a,\gcd(b,c))= \gcd(\gcd(a,b),c)
• 若~a \mid b~，则~ \gcd(a,b)=a~
• 对于任意整数~k，~\gcd(a,b)=\gcd(a,b+ak)~
• 若~ \gcd(a,b)=d~，则~ \gcd(\Large\frac{a}{d}\normalsize,\Large\frac{b}{d}\normalsize)=1~
• 裴蜀定理：存在一组~x,y~来满足~ \gcd(a,b)=ax+by~
• 欧几里得算法：设~k=\Large\left\lfloor\frac{a}{b} \right\rfloor\normalsize~，~r=a \mod b~，则有~ \gcd(a,b)= \gcd(b,r)
• 若~b\mid ac~且~\gcd(a,b)=1，则有~b \mid c~
• 若~b\mid c,a\mid c~且~\gcd(a,b)=1，则有~ab\mid c~
• 若~ \gcd(a,b)=1~，则有~\gcd(a,b c)= \gcd(a,c)~

  证明

  建议先去理解裴蜀定理（下文）

• 对于若~b\mid ac~且~\gcd(a,b)=1，则有~b \mid c~ \ 设~k=\Large\frac{a c}{b}~ \normalsize，则有~kb=ac~ \ 根据裴蜀定理，当~ \gcd(a,b)=1~时，有一组~x,y~满足~xa+yb=1~ \ 在等式两边同时乘上~c，得~xac+ybc=c \ 带入~kb=ac，得~xkb+ybc=c，提取出一个~b，b(xk+yc)=c \ \therefore b\mid c
• 对于若~b\mid c,a\mid c~且~\gcd(a,b)=1，则有~ab\mid c~ \ 设~n=\Large\frac{c}{a}\normalsize ,m=\Large\frac{c}{b}\normalsize，所以~na=c,mb=c \ 还是裴蜀定理，当~ \gcd(a,b)=1~时，有一组~x,y~满足~xa+yb=1~ \ 在等式两边同时乘上~c，得~xac+ybc=c 带入~na=c,mb=c，得xa\cdot mb+yb\cdot na=c \ 根据乘法分配律~ab(xm+yn)=c \ \therefore ab\mid c
• 对于若~ \gcd(a,b)=1~，则有~\gcd(a,b c)= \gcd(a,c)~ \ 设~k=\gcd(a,bc),k^{'}=\gcd(a,c) \ $\because \gcd(a,b)=1$ \ $\therefore \gcd(k,b)=1$ \ $\therefore k\mid c$ \ $\therefore k\le k^{'}$ \ 同理可得，$k^{'}\le \gcd(a,bc)$ \ 综上所述，$k=k^{'}，$因此$~\gcd(a,b c)= \gcd(a,c)~

证毕 \ 解释说明： \

设~a,b~两数，a~与~b~除~m~的余数相同，则a~与~b~模~m~(m \ne0)同余，记为~a\equiv b\pmod m

性质

• 自反性：~a\equiv a \pmod m
• 对称性：若~a\equiv b \pmod m~~~~~~~~~~则~b\equiv a \pmod m
• 传递性：若~a\equiv b \pmod m,b\equiv c \pmod m~~~~~~则~a\equiv c \pmod m
• 可加性：若~a\equiv b \pmod m~~~~~~~~~~则~a\pm d\equiv b\pm d \pmod m
• 可乘性：若~a\equiv b \pmod m,c\equiv d \pmod m~~~~~~则~ac\equiv bd \pmod m
• 当~a=-1~时，a\bmod b=b-1

其他性质详见数论基础 OI-Wiki

由此推出\

整数唯一分解定理

定义

唯一分解定理又名算术基本定理，对于任何大于~1~的整数~n~，如果~n~是质数，那么~n~分解等于本身，如果~n~不是质数，则可以分解为~2~个或~2~个以上的质数的乘积，并且分解方式唯一。

分解方式

欧拉函数

定义

规律

例如:~~ \varphi(1)=1

通过观察以上数据，我们容易发现：

• \varphi(i)=i-1

• 当~i \bmod p_j=0时，并且~p_j~是质数，则~\varphi(i\cdot p_j)= \varphi(i)\cdot p_j
• 当~i \bmod p_j \ne0时，并且~p_j~是质数，则~\varphi(i\cdot p_j)= \varphi(i)\cdot( p_j-1)
• 当i是奇数时，有\varphi(2\cdot i)=\varphi(i)

证明

当~i~是个质数时

• 显而易见~\varphi(i)=i-1

当~i~不是质数时

• 当~i \bmod p_j=0，且~p_j~是质数，则~\varphi(i\cdot p_j)= \varphi(i)\cdot p_j\ 因为~i~中有因数~p_j~，因此~\varphi(i\cdot p_j)等同于~\varphi(i)~翻~p_j~倍
• 当~i \bmod p_j\ne0，且~p_j~是质数，则~\varphi(i\cdot p_j)= \varphi(i)\cdot( p_j-1) \ 因为~i~中有不含因数~p_j~，因此~\varphi(i\cdot p_j)等同于~\varphi(i)~翻~p_j~倍再乘上~\Large\frac{p_j-1}{p_j}~

计算方式

用整数唯一分解定理分解~n\ 得到：n = p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\cdot ... \cdot p_m^{a_m}

化简一下就是：

例子

当~n=10时\

欧拉定理

定义

对于任意整数~a~和正整数~m，如果~a~和~m~互质，即~\gcd(a,m)=1，则~a^{\varphi(m)}\equiv 1\pmod m 。 \ 比如~3~和~8~，\gcd(3,8)=1，3^{ \varphi(8)}=3^4=81，81 \bmod 8=1。

推论

证明

设~k= \Large\left\lfloor\frac{b}{\varphi(m)}\right\rfloor\normalsize,r=b\bmod~\varphi(m)

根据欧拉定理得，当~ \gcd(a,m)=1时,~a^{\varphi(m)}\equiv 1\pmod m

转换形式过程

扩展欧拉定理

伟大的欧拉觉得欧拉定理太慢，于是扩展欧拉定理诞生了~!

定义

欧几里得算法

定义

欧几里得算法又称辗转相除法，通常用于求两个数的最大公约数(GCD)。\

证明

• 若~a<b，则 \gcd(a,b)= \gcd(b,a)= \gcd(b,a\bmod b) \ 设~a=4,b=18，则~\gcd(4,18)=\gcd(18,4)=\gcd(18,4)，命题成立
• 若~a\ge b，设~k=\Large\left\lfloor\frac{a}{b}\right\rfloor\normalsize,r=a\bmod b，所以~a=k\cdot b+r，a,b~的公约数集合中取出任意数~d，d\mid a~且~d\mid (k\cdot b)，所以~d\mid (a-k\cdot b)，即~d \mid r，因此~d~是~a,b,r~的公约数，因此~ \gcd(b,a\bmod b)~成立

证毕

裴蜀定理

介绍

裴蜀定理又称贝祖定理，是数论中的重要定理、一个关于最大公约数的定理，可用于求解不定方程~ax+by=c~是否有解。

定义

对于整数 ~a,b(a,b不全为0)~ ，对于整数~m~和任意整数~x,y，方程 ~ax+by=m~ 有解需满足~m~是~ \gcd(a,b)~的倍数~(\gcd(a,b)\mid m)，并且在上文 ~x,y~中存在一组 ~x_0,y_0~ 满足 ~ ax_0+by_0= \gcd(a,b)~，特别的，若~ax+by=1~有解需满足~\gcd(a,b)=1

证明

• 对~ax+by=m~有解需满足~m是~\gcd(a,b)~的倍数\ $\therefore \gcd(a,b)\mid ax~,~\gcd(a,b)\mid by(~x,y~$为任意整数$)$\ $\therefore \gcd(a,b)\mid ax+by$ \ $\therefore \gcd(a,b)\mid m
• 对~ax+by=1~有解需满足~\gcd(a,b)=1\ 若 \gcd(a,b) \ne 1，根据上文证明，则~ax+by\ne 1 \ 反之，当\gcd(a,b)=1,ax+by=1~有解
• 对任意~x,y~中存在一组~x_0,y_0~满足~ax_0+by_0= \gcd(a,b)
  1. 当~a~或者~b~其中一个等于~0， \gcd(a,b)=a，此时定理一定成立
  2. 当~a,b~不为~0，因为~\gcd(a,b)=\gcd(a,-b) \ 设a,b>0，d=\gcd(a,b)，则ax+by=d \ 在等号两边同时除以~d，得~a_0x+b_0y=1，此时~\gcd(a_0,b_0)=1，有解

证毕\ 解释说明：\

推广

假设有~n~个整数~a_1,a_2,a_3,...,a_n~。其中，d~是它们的最大公约数，则存在整数~x_1,x_2,x_3,...,x_n~来满足~a_1x_1+a_2x_2+a_3x_3+...+a_nx_n=d\ 既然裴蜀定理都有特殊情况，那推广一定也有：\ 当~ \gcd(a_1,a_2,a_3,...,a_n)=1~时，则存在整数~x_1,x_2,x_3,...,x_n~来满足~a_1x_1+a_2x_2+a_3x_3+...+a_nx_n=1

例子

三个整数~114,514,1919810，它们的~\gcd(114,514,1919810)~=2，有一组解~x_1=-9,x_2=2,x_3=0~满足~114\times -9+514\times 2+1919810\times 0=2~ \ 四个整数~114,514,1919,810~它们的~ \gcd(114,514,1919,810)~=1，有一组解~x_1=？,x_2=？,x_3=？,x_4=？~满足~114\times ？+514\times ？+1919\times ?+810\times ?=1~聪明的homo一定能得出答案（我懒）

模运算意义下的逆元

定义

一个整数~a~在模~m~的意义下的逆元是指~a^{-1}~满足~a\cdot a^{-1}\equiv 1\pmod m 。例如一个线性同余方程~a \cdot b \equiv 1\pmod m ，此时称~b~是~a \bmod m~的逆元，记作a^{-1}。通常在求逆元时限制~0\le b<m~，这样的限制使得逆元具有唯一性和确定性

性质

• 存在性：当~ \gcd(a,m)=1~时，逆元存在；否则逆元不存在
• 唯一性：对于给定的整数~a~和正整数~b~，如果逆元存在，那么它是唯一的。
• 组合性：a,b~在模~m~下的逆元~a^{-1},b^{-1}~，此时~(a\cdot b)~的逆元是~(a^{-1}\cdot b^{-1}~) \bmod m

  证明

• 对存在性进行证明 \ 在同余式~a\cdot b\equiv 1\pmod m 中 \ 当 \gcd(a,m)=1~时，根据裴蜀定理可得，ax+my=1 \ 在方程两边同时模~m~，得~ax\equiv1\pmod m \ 此时~x~就是~a~的逆元 \ 当~ \gcd(a,m)\ne1~时，设d= \gcd(a,m)~，则有~kd=a~和~k^{'}d=m~ \ 设~a^{-1}，则~aa^{-1}\equiv 1\pmod m ，根据同余式的性质推出 \ 进一步推出$~aa^{-1}-pm=1$ \ 可以发现，$d~$可以整除右边而不能整除左边，导致等式无法成立 \ 综上所述，当$~ \gcd(a,m)=1~$时，逆元存在；否则逆元不存在
• 对唯一性进行证明 \ 假设在模~m~下~a~有两个逆元~k~和~k^{'} \ 则有同余方程组\begin{cases} ak\equiv 1\pmod m \\ ak^{'}\equiv 1\pmod m \\ \end{cases} \ 所以有ak\equiv ak^{'}\pmod m \ 进一步推出~ak-ak^{'}\equiv 0\pmod m \ 于是就有~m\mid (ak-ak^{'})~ \ 因为~ \gcd(a,m)=1~，所以~m\mid (k-k^{'})~ \ 因为~0\le k,k^{'}<m，所以m< k-k^{'}<m \ 在此范围中~k-k^{'}~若被~m~必然等于~0~，所以~k=k^{'}
• 对组合性进行证明 \ 此时得到两个同余方程$\begin{cases} a\cdot a^{-1}\equiv 1\pmod m \\ b\cdot b^{-1}\equiv 1\pmod m \\ \end{cases} $\ 同时\ $\begin{aligned}(a\cdot b)\cdot (a^{-1}\cdot b^{-1}) &=a\cdot b\cdot a^{-1}\cdot b^{-1} \\ &=a\cdot a^{-1}\cdot b\cdot b^{-1} \\ &=(a\cdot a^{-1})\cdot (b\cdot b^{-1})\\ \end{aligned}$ \ 让我们在两端模上$~m$ \ $\begin{aligned}(a\cdot b)\cdot (a^{-1}\cdot b^{-1}) &\equiv(a\cdot a^{-1})\cdot (b\cdot b^{-1})\pmod m \\ &\equiv 1\cdot 1\pmod m \\ &\equiv 1\pmod m \end{aligned} $\ 因此，$a,b~$在模$~m~$下的逆元$~a^{-1},b^{-1}~$，此时$~(a\cdot b)~$的逆元是$~(a^{-1}\cdot b^{-1}~) \bmod m

证毕 \ 解释说明：\

而扩展欧几里得算法则是在这个求~( \gcd)~的过程中，同时求一组~x,y~来满足~ax+by= \gcd(a,b)~。

算法步骤（过程）

让我们利用裴蜀定理和欧几里得算法先对~ax+by= \gcd(a,b)~进行分解

解法

不定方程~ax+by=c，若有解需满足条件~ \gcd(a,b)\mid c~，设~k=\Large\frac{c}{\gcd(a,b)}~于是方程就变成了~ax+by=k\cdot\gcd(a,b)~，我们可以先找一对满足~ax+by=\gcd(a,b)~得~x_0,y_0~，求得解后在方程两边同时乘一个~k（等同于乘上\Large\frac{c}{\gcd(a,b)}~），得到x_0k,y_0k这就是不定方程~ax+by=c~的一组解

不定方程~ax+by=c~的通解（通解：在一个方程或方程组中，能够表示出所有可能解的表达式。）可以表示为如下表达式\ 其中~x_0,y_0~为一组特解，d=\gcd(a,b)，C~为任意整数 \ 通解：\begin{cases} x=\Large\frac{c}{d}\normalsize x_0+\Large\frac{b}{d}\normalsize C \\ \\ y=\Large\frac{c}{d}\normalsize y_0-\Large\frac{a}{d}\normalsize C \\ \end{cases} \ 注意：通解的~C~是同一个数

例子

有不定方程3x+5y=18，求出\gcd(3,5)=1，先求出3x+5y=1(别忘了这里是~ \gcd)，得出x=2,y=-1\ 此时~k=18，因此原方程的解为x=36,y=-18。\ 通解为x=18\times 2+5C=36+5C\

求解线性同余方程

解法

有同余式~ax \equiv b\pmod m ~，因为它只有一个未知数，又名线性同余方程~or~一次同余方程 \ 根据同余式的性质，我们可以设~k= \Large\frac{ax-b}{m}~（k~没必要计算），方程转换一下就是~ax-b=km~\ 想想~ax+by=c~这个不定方程，我们是不是可以将~ax-b=km~转换为前面的不定方程来求解 \ 所以这里设~k=-y，方程变为~ax-b=-ym~，再次变换~ax+ym=b~ \ 这时线性同余方程变成了一个不定方程，若~gcd(a,m)\mid b~，方程有解

例子

当~3x\equiv 5\pmod 7，根据方法，方程变为~3x+7y=5，因为~gcd(3,7)\nmid 5~，无解

求解乘法逆元

乘法逆元定义

想什么呢，它就是上面的模运算意义下的逆元

解法

乘法逆元，aa^{-1}\equiv 1\pmod m ，有解需满足~\gcd (a,m)=1\

证明

• 当~p~是质数时，1~的逆元是本体，而~p-1~的逆元也是本体\ $ \begin{aligned} (p-1)(p-1) &=p^2-2p+1 \\ &\equiv 1\pmod p \end{aligned}$\ 而$~2 \thicksim p-2~$之间都会有非本体的逆元，因为逆元具有唯一性 \ 因为$~p~$是质数，与非本体和$~1~$的数都互质，保证一定有这个区间里一定会有逆元 \ 因此$~(p-1)!~$中仅有$~p-1~$和$~1~$没有被消掉，其他的数都被消了 \ $\therefore (p-1)!\equiv p-1\equiv -1\pmod p
• 当~p~不是质数\ 所以有了除~1,p~以外的约数，而这些约数它们一定在~1 < 约数 <p~中，因而~(p-1)!\bmod p=0

综上所述，当~p~是质数时才会有(p-1)!\equiv -1\pmod p，定理成立\ 证毕

例子

下面放一个式子你谷题目\

设~(3k+6)!+1=m(3k+7)\

则有~m= \Large\frac{(3k+6)!+1}{3k+7}\

有~3k+7\mid (3k+6)!~ \

因为~3k+7~不是质数了，所以有了除~1,3k+7~以外的约数，而这些约数它们一定在~1 < 约数 <3k+7~中 \

设~(3k+6)!=m(3k+7)\

则有~m=\Large\frac{(3k+6)!}{3k+7} \

这里得~0~的原因显而易见了，因为~ \Large\frac{1}{3k+7}~在向下取整后会得到~0~

综上所述，\Large\sum_{k=1}^{n} \left \lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right \rfloor\right \rfloor~等同于求\Large\sum_{k=1}^{n}\normalsize [3k+7 为质数]

卢卡斯定理

中国剩余定理(CRT)

引入

今有物不知其数量，三三数之余二；五五数之余三；七七数之余二。问物几何？ 　　——《孙子算经》

这是一道典型的中国剩余定理例题

定义

中国剩余定理一般用于求在已知同余方程组中能满足方程组的最小整数解\ 假设有一组同余方程如下\

• 先求出所有模数的积，也就是~P= \Large\prod_{i=1}^{3}\normalsize p_i~，也就是~p_1\cdot p_2\cdot p_3
• 对于每一个方程\ 求出积除模数的值~k_i~，也就是~k_i= \Large\frac{P}{p_i}\ 计算出~k_i~的在模~P~下的逆元~k_i^{-1}\ 最后计算~k_i\cdot k_i^{-1}~，用~b_i~表示
• 答案就是~ x=\Large\sum_{i=1}^{3}\normalsize a_i\cdot b_i~，也就是~x=(a_1\cdot b_1)+ (a_2\cdot b_2)+(a_3\cdot b_3)~
• 若要求最小值，则为~x\bmod P

证明

• 对模数需要两两互质进行证明\ 假设~p_1,p_2,p_3~中~p_1,p_2~两数不互质，当~k_1=p_2\cdot p_3~时（因为~k_1= \Large\frac{P}{p_1}~，而~P=p_1\cdot p_2\cdot p_3），此时~\gcd(k_1,p_1)\ne 1~，根据逆元的存在性可知，k_1~不会有逆元~k_1^{-1}，方程无解；若换为其他模数不互质，p_i,p_j~两个模数不互质，总会有个~k~没有逆元，因此模数之间需要两两互质
• 对解的正确性的证明\ x \equiv a_1~(\bmod~p_1)\\ x \equiv a_2~(\bmod~p_2)\\ x \equiv a_3~(\bmod~p_3)\ \end{cases}$\ 我们计算出$~P~$之后，得到$~k_i~$的方法为$~k_i= \Large\frac{P}{p_i}$，将$~k_1,k_2,k_3~$展开得到\ $\begin{cases} k_1=p_2\cdot p_3\\ k_2=p_1\cdot p_3\\ k_3=p_1\cdot p_2\ \end{cases}$\ 这里我们代入$~b_i=k_i\cdot k_i^{-1}$，同时分解掉$~k_i~$后，得到的$~x~$为\ $\begin{aligned}x &=(a_1\cdot b_1)\cdot (a_2\cdot b_2)\cdot(a_3\cdot b_3)\\ &=(a_1\cdot k_1\cdot k_1^{-1})\cdot (a_2\cdot k_2\cdot k_2^{-1})\cdot(a_3\cdot k_3\cdot k_3^{-1})\\ &=(a_1\cdot p_2\cdot p_3\cdot k_1^{-1})\cdot (a_2\cdot p_1\cdot p_3\cdot k_2^{-1})\cdot(a_3\cdot p_1\cdot p_2\cdot k_3^{-1}) \end{aligned}$\ 可以发现，对于任意$~p_i\left \{ i\in \mathbb{Z^{+}}\mid i\le 3 \right \} $，总会有$~(a_j\cdot b_j)\equiv 0~(\bmod ~p_i)(i\ne j)~$。对于剩下的$~(a_i\cdot b_i)$，因为$~b_i\equiv 1~(\bmod ~p_i)~$，在两边同时乘上一个$~a_i~$（同余式的可乘性），得$~a_i\cdot b_i\equiv a_i~(\bmod ~p_i)~$，因此解$~x~$是正确的

证毕

扩展中国剩余定理(EXCRT)

定义

普通的中国剩余定理只能处理模数互质的情况，扩展中国剩余定理便为处理模数不互质而诞生 假设有一组同余方程如下\

• 判断是否有解\ 设~z_i={\Large \frac{x-a_i}{p_i}}~\ 则有~x=p_i\cdot z_i+a_i~\

  $\therefore p_1z_1-p_2z_2=a_2-a_1$\ 设$~z_1=n,z_2=-m$\ $\therefore np_1+mp_2=a_2-a_1$\ 据裴蜀定理可得，$\gcd(p_1,p_2)\mid a_2-a_1~$，方程有解，否则方程无解。

• 两方程有解，合并式子\ 此处过程与中国剩余定理/算法步骤（过程） 一致\ 取解为~x_0，则新方程为~x\equiv x_0\pmod{P}

如有新的式子，重复判断是否有解，确认有解执行合并式子\ 若无新式子，答案为~x_0~

证明

• 对同余方程组是否有解的证明\ 请见扩展中国剩余定理/算法步骤（过程）

• 对解的正确性的证明\ 请见中国剩余定理/证明/对解的正确性的证明，证明类似