翻了翻之前写的博客……

为啥我还写过这么牛的东西啊啊啊啊啊啊

马上搬过来,不说别的了

2019.7.25

最近在搞数论,为了防止忘记,在这里留一个文章记录,其中包含一些非常细节的证明和推导,据说这对数学思维的培养很有帮助 ~~(大佬莫喷,蒟蒻刚学OI)~~

1.整除

定义

$\exists q满足 a=qb$
则a能被b整除，记作：$b|a$

性质

若$a|b且b|a,则a=b或a=-b$
$若a|b,b|c,则a|c$
$若a|b,a|c,则对于任意整数x,y,有a|(bx+cy)$
证明:
$由a|b,a|c$
$得k_1\times a=b,k_2\times a=c$
$则bx+cy=k_1\times a+k_2\times a=a(k_1+k_2)$
$故a|(bx+cy)$

2.带余除法

定义

$对于整数a,b(a>=b),a可以被唯一表示为a=bq+r,r即为余数$

余数的范围和唯一性

余数范围~~显然是~~:$[0,|b|)$
唯一性证明:考虑使用反证法
$假设a可以被表示为a=b\times q_1+r_1=b\times q_2+r_2$
$则b\times q_1+r_1=b\times q_2+r_2$
$b\times (q_1-q_2)=r_2-r_1$
$即b|r2-r1$
$由于r_i\in [0,|b|)且b|r_2-r_1$
$r_2-r_1=0,即r_2=r_1$
$由于开始我们假设r_2 != r_1,故与原命题矛盾$
$得证$

3.素数

定义

除了1和它本身外没有其他因子的数

性质

一个数除1以外的最小正因数是素数
任意数可以被分解为若干素数之积
素数有无穷个

判定素数和线性筛

判定素数

各种筛法

算数基本定理(唯一分解定理)

内容

$\forall x=p_1^{s1}\times p_2^{s_2}\times……p_n^{s_m}=\prod_{i=1}^{m}p_i^{s_i},p_i是素数$
即:任意数可以被分解为若干素数之积

推论

$x的约数个数d(n)=\prod_{i=1}^{m}(s_i+1),根据乘法原理可证明$
$x的约数和\sigma(n)=\prod_{i=1}^{m}(p_i+p_i^2+……+p_i^{c_i})=\prod_{i=1}^{m}(\sum_{j=1}^{c_i}(p_i)^j)$

应用

$令a=p_1^{s1}\times p_2^{s_2}\times……p_n^{s_n},b=p_1^{k1}\times p_2^{k_2}\times……p_n^{k_n}$
$[a,b]=p_1^{max(s_1,k_1)}\times p_2^{max(s_2,k_2)}\times……p_n^{max(s_n,k_n)}=\prod_{i=1}^{n}p_i^{max(s_i,k_i)}$
$(a,b)=p_1^{min(s_1,k_1)}\times p_2^{min(s_2,k_2)}\times……p_n^{min(s_n,k_n)}=\prod_{i=1}^{n}p_i^{min(s_i,k_i)}$
由上面这个性质可得,$[a,b]\times(a,b)=|a\times b|$
若(a,b)=1,则$\prod_{i=1}^{n}p_i^{min(s_i,k_i)}=1$,即每一个pi的最小指数为0

4.最大公因数

定义

从字面意思即可了解
$\oplus$:a,b的最大公因数表示为$(a,b)$

性质

$若(a,b)=1,则a,b互素$
辗转相减$(a,b)=(a-b,b)$

证明:
$设a和b的所有因子组成集合S,a-b和b的所有因子组成集合K$
$则对于任意的d\in S有:$
$d|a,d|b$
$则d|(a\times x+b\times y),x和y任意取值$
$令x=1,y=-1,则有$
$d|(a-b)$
$则对于任意的d\in S有d|(a-b),d|b,即d\in K$
$同理,对于任意的d\in K有d\in S$
$由上可知:K\subseteq S且S \subseteq K$
$故S=K$
$故(a,b)=(a-b,b)$

辗转相除$(a,b)=(b,a\pmod b)$

证明:

$设r=a\pmod b,根据带余除法:$
$r=a-k\times b$
$待证式子即化为:(a,b)=(a,a-k\times b)$
按照辗转相减的证明思路不难证得辗转相减的推论:
$(a,b)=(a-q\times b,b)$
$令q=k,得证$

$(\frac{a}{(a,b)},\frac{b}{(a,b)})=1$(用唯一分解定理互素的等价变换可知)

5.裴蜀定理

内容

$若d=(a,b)$
$则\exists m,n 使得 a\times m+b\times n=d$

证明

考虑用数学归纳法证明：

$当b=0时:$
$显然a=d，a可以取任意值，存在m，n满足上式$
$当b>0时：$
$假设对于x\in [0,b-1],都满足上式，其中a可以取任意值$
$首先,显然(a,b)=(b,a\pmod b)=d$
$则对于c=a\pmod b，由于c\in[0,b-1]$
$故:b\times m+c\times n=d ——(\theta)$
$由带余除法得:a=k\times b+c,即c=a-k\times b$
$将c代入(\theta)中得b\times m+(a-k\times b)\times n=d$
$整理得a\times n+b\times(m-k\times n)=d$
$则对于a,b,有m’=n,n’=m-k\times n使得a\times m’+b\times n’=d成立$
(这里证得了若对于[0,n]满足上式，则[0,n+1]满足了上式)
$故对于任意a，b，d=(a,b),\exists m,n 使得 a\times m+b\times n=d$

特殊情况

$(a,b)=1\Leftarrow\Rightarrow a\times m+b\times n=1$

证明

推论

若$a|b\times c,(a,b)=1,则a|c$
$若p是素数,p|a\times b,则p|a或p|b$
$若(a,n)=1,(b,n)=1,则(a\times b,n)=1$

6.最小公倍数

定义

从字面意思即可了解
$\oplus$:最小公倍数表示为$[a,b]$

性质

$[a,b]\times(a,b)=|a\times b|$

7.同余

定义

$若若a和b被n除后余数相同，则称a与b同余，记作:a \equiv b \pmod n$

性质

$a \equiv b \pmod n \Leftarrow\Rightarrow n|(a-b)$
$若a \equiv b \pmod n,c \equiv d \pmod n$
则:
$a+c \equiv b+d \pmod n$
$a\times c \equiv b\times d \pmod n$
$k\times a \equiv k\times b \pmod n$
$a^m \equiv b^m \pmod n$
若$k\times a \equiv k\times b \pmod n,且(a,n)=1$
则$b\equiv c \pmod n$(消去律,后面会用到)

8.剩余类

定义

$把所有模n后与a同余的整数构成的集合叫做一个剩余类，记作[a]$

则:$a \equiv b \pmod n \Leftarrow\Rightarrow [a]=[b]$

运算

$[a] + [b] = [a+b], [a] * [b] = [a*b]$

零元,单位元,负元和逆元

$[0]是零元，[1]是单位元$
$[a]的负元与逆元(用[b]表示)：[a]+[b] = [b] + [a] = 0, [a][b] = [b][a] = 1$

性质

$[a]有逆元充要条件：(a,n)=1$

证明：（充要条件：即充分必要条件，若条件p可以推出条件q，则p是q的充分条件，若q又可以反推p，则q是p的必要条件）

1.充分性：
若[a]存在逆元[b],则有$a\times b \equiv 1\pmod n$,即$a\times b+k\times n=1(k<0)$
$由于(a,n)|a,(a,n)|n$
$即(a,n)|a\times b,(a,n)|k\times n$
$因此(a,n)|(a\times b+k\times n)$
$则(a,n)|1$
$故(a,n)=1$
2.必要性：
若$(a,n)=1,根据裴蜀定理,存在一对b,y满足:$
$a\times b+n\times y=(a,n)=1$
$等价于a\times b\equiv1\pmod n$
$即b为a的逆元$
$证毕$

$若[a]有逆元,则逆元唯一$

证明:
假设逆元不唯一:
$设[a]有逆元[b_1],[b_2]$
$则有:a\times b_1\equiv a\times b_2 \mod n$
$由于(a,n)=1,根据消去律:b_1\equiv b_2 \mod n$
$即[b_1]=[b_2]$
$矛盾,则[a]的逆元唯一$
$证毕$

$无零因子充要条件：n为素数(显然嘛)$

9.群论初步(不是很严谨,看看就好)

定义

在数学中，群表示一个拥有满足封闭性、结合律、有单位元、有逆元的二元运算的代数结构，包括阿贝尔群、同态和共轭类。——–baidu

说的直白点,就是集合+运算

性质

运算封闭性(整数加/减整数依然是整数)
结合律
存在单位元(唯一)
每个数都存在逆元(唯一)

子群,循环群

子群:如果群G的非空子集合H对于G的运算也成一个群，那么H称为G的子群。

用大白话来讲就是H是包含在G中,且有单位元,每个H中的元素都有逆元

若—个群G的每—个元都是G的某—个固定元a的乘方，则称G为循环群，记作G=(a)={am |m∈Z}，a称为G的—个生成元。

其实就是说若群里的某个元素可以以乘方的方式来形成其他的元素,那么这就是一个循环群

陪集

陪集是指H是群G的子群，对于某一g∈G，{gh|对于所有h∈H}表示H的一个左陪集，记作gH;{hg|对于所有h∈H}表示H的一个右陪集，记作Hg；也译作傍系，旁集等。

注意,陪集不一定是群,它不一定满足群的性质

拉格朗日定理

对于群G的子群H,满足$|H|$ | $|G|$(G被H整分)
~~(不会证)~~

有限循环群的性质

$r^{| < r > |}=1$

10.初等数论相关定理

欧拉定理

内容

$对于正整数a,b,若(a,b)=1,则有a^{\varphi(n)}\equiv 1\pmod n$

证明

$在模n下设群G$:{$x|(x,n)=1$}
$设群a为G的子群$
$则a中的元素也和n互质$
由于$|<a>|$ | $\varphi(n)$
$得\varphi(n)=k\times |<a>|$
$由于a^{|<a>|}=1$
$乘k次方得 a^{|<a>|\times k}=1$
$于是a^{\varphi(n)}=1$
$由于这是在模n下的推导,所以放到一般情况有:a^{\varphi(n)}\equiv 1\pmod n$
$得证$

关于欧拉函数

$欧拉函数的计算:$
$对于n,将其唯一分解为 \prod_{i=1}^{n}p_i^{k_i}$
$则\varphi(n)=n\times \prod_{i=1}^{n} (1- \frac{1}{p_i})$

费马小定理

内容

$若p为素数,a不是p的倍数,则a^p\equiv a\pmod p$

证明

(其实可以用欧拉定理证明,但我偏不干~~)
$令x=1\times 2\times3\times…..\times(p-1)$
$令y=a\times1\times a\times 2\times a\times3\times…..\times a\times(p-1)$
$则x=(p-1)!且y=a^{p-1}(p-1)!$

若是在模p的剩余类下定义x和y,那么有$x= y$
即在一般情况下的
$x\equiv y\pmod p$
$代入x和y:(p-1)!\equiv a^{p-1}\times(p-1)!\pmod p$
$根据消去律,由于p是素数,故((p-1)!,p)=1$
$于是$
$1\equiv a^{p-1}\pmod p$
$即a^p\equiv a\pmod p$
$证毕$