数论学习笔记1

跟着《算法竞赛进阶指南》学习数论知识做的笔记

之前的那个数论定理只是单纯的记了一下公式， 很多公式并不知道是怎么推出来的， 所以重新学习一遍

算术基本定理的推论

推论

如果算数基本定理中$N=p_1^{b_1}{p}_2^{b_2}\cdots p_m^{b_m}$， 其中$p$为质数， 设$N$的约数和为$S$， 则有

$$S=(1+p_1+p_1^2+\cdots +p_1^{b_1})\times \cdots \times (1+p_m+p_m^2+\cdots +p_m^{b_m})=\underset{i=1}{\overset{m}{\mathrm{\Pi }}}(\sum _{j=0}^{c_i}(p_i{)}^j)$$

证明类似于高中的二项式展开， 这样展开从每个括号里选一个数出来相乘就包括了$N$的全部约数

题目

给出$1\le A,B\le 5\times {10}^7$， 求$A^B$的所有约数和 $mod9901$

欧拉函数

$\varphi ()$

定义

$\varphi (N)$为$1\cdots N$中和$N$互质的数的个数， 即$gcd(x,N)=1,1\le x\le N$的$x$的个数

计算

如果算数基本定理中$N=p_1^{b_1}{p}_2^{b_2}\cdots p_m^{b_m}$， 其中$p$为质数， 则

$$\varphi (N)=\underset{i=1}{\overset{m}{\mathrm{\Pi }}}(1-\frac{1}{p_i})$$

证明

$1\cdots N$中$p_1$的倍数有$\frac{N}{p_1}$个， $p_2$的倍数有$\frac{N}{p_2}$个， 去掉这两个数的倍数得到的结果多除了既是$p_1$的倍数也是$p_2$的倍数的数， 有$\frac{N}{p_1\times p_2}$个， 所以$1\cdots N$中不和$N$含有共同质因子$p_1,p_2$的数的个数为

$$N-\frac{N}{p_1}-\frac{N}{p_2}+\frac{N}{p_1\times p_2}=N\times (1-\frac{1}{p_1}-\frac{1}{p_2}+\frac{1}{p_1\times p_2})=N\times (1-\frac{1}{p_1})(1-\frac{1}{p_2})$$

对于三个质因子及以上的情况要用到容斥原理， 也类似于高中二项式的展开

一些性质

性质1

内容

任意$n>1$， $1\cdots n$中与$n$互质的所有数的和为$\varphi (n)\times n/2$

证明

由于$gcd(n,x)=gcd(n,n-x)$， 与$n$互质的$x,n-x$是成对出现的， 每一对的和为$n$， 由于与$n$互质的数一共有$\varphi (n)$个， 所以总共的和为$\varphi (n)\times n/2$

性质二

内容

设$p$为质数， 若$p|n,p^2|n$， 则$\varphi (n)=\varphi (n/p)\times p$； 若$p|n$但是$p^2$不能整除$n$， 则$\varphi (n)=\varphi (n/p)\times (p-1)$

证明

1. $p^2|n$

   因为$p^2|n$， 所以$n/p$必然含有质因子$p$， 所以$n$和$n/p$含有完全相同的质因子， 那么有

   $$\varphi (n)=n\times (1-\frac{1}{p})\cdots$$

$$\varphi (\frac{n}{p})=\frac{n}{p}\times (1-\frac{1}{p})\cdots$$

显然有$\varphi (n)=\varphi (n/p)\times p$

1. $p^2$不整除$n$

   这种情况下$n/p$和$p$是互质的， 根据积性函数性质得$\varphi (n)=\varphi (n\times \frac{n}{p})=\varphi (\frac{n}{p})\times \varphi (p)=\varphi (\frac{n}{p})\times (p-1)$

性质三

内容

$$\sum _{d\mid n}\varphi (d)=n$$

证明

首先证明$f(n)=\sum _{d\mid n}\varphi (d)$是一个积性函数， 设$n,m$互质， 则有

$$f(nm)=\sum _{d\mid nm}\varphi (d)=(\sum _{d_1\mid n}\varphi (d_1))\times (\sum _{d_2\mid m}\varphi (d_2))=f(n)\times f(m)$$

第二个等号的转换由乘法分配律得到， 因为$n,m$互质， 所以必然$gcd(d_1,d_2)=1,\varphi (d)=\varphi (d_1)\times \varphi (d_2)$， $nm$的所有因子$d$都可以由$d_1\times d_2$得到， 展开该式就能得到所有的$d$

对于$n$的一个质因子$p$， 由性质二有

$$\begin{array}{}\text{(1)}& f(p^m)& =\sum _{d\mid p^m}\varphi (d)=\varphi (1)+\varphi (p)+\varphi (p^2)+\cdots +\varphi (p^m)\text{(2)}& & =1+(p-1)+(p-1)\times p+\cdots (p-1)\times p^{m-1}\text{(3)}& & =p^m\end{array}$$

若在算数基本定理中有$n=p_1^{m_1}{p}_2^{m_2}\cdots p_b^{m_b}$， 则有

$$\begin{array}{}\text{(4)}& f(n)& =f(p_1^{m_1}{p}_2^{m_2}\cdots p_b^{m_b})\text{(5)}& & =f(p_1^{m_1})f(p_2^{m_2})\cdots f(p_b^{m_b})\text{(6)}& & =p_1^{m_1}{p}_2^{m_2}\cdots p_b^{m_b}\text{(7)}& & =n\end{array}$$

得证

同余类与剩余系

定义

对于$\mathrm{\forall }a\in [0,m-1]$， 集合$\{a+km\}$的所有数模$m$同余， 余数都是$a$。 该集合称为一个模$m$的同余类， 记为$\bar{a}$

模$m$同余类一共有$m$个， 分别为$\bar{0},\bar{1},\cdots ,\overline{m-1}$， 它们构成$m$的完全剩余系

$1\cdots m$中与$m$互质的数代表的同余系有$\varphi (m)$个， 它们构成$m$的简化剩余系

简化剩余系

性质

简化剩余系关于模$m$乘法封闭

证明

若$a,b$均与$m$互质， 则$a\times b(1\le a,b\le m)$也必然与$m$互质， 则$gcd(a\times b,m)=gcd(m,(a\times b)\mathrm{\%}m)=1$， 即$(a\times b)\mathrm{\%}m$也与$m$互质， 即$(a\times b)\mathrm{\%}m$也属于$m$的简化剩余系

欧拉定理

内容

若正整数$a,n$互质， 则$a^{\varphi (n)}\equiv 1(modn)$

证明

设$n$的简化剩余系为$\{\overline{a_1},\overline{a_2},\cdots \overline{a_{\varphi (n)}}\}$，对$\mathrm{\forall }{a}_i,a_j$， 如果$a\times a_i\equiv a\times a_j(modn)$， 则有$a\times (a_i-a_j)\equiv 0(modn)$， 因为$a,n$互质， 得到$a_i-a_j\equiv 0(modn)$， 即$a_i\equiv a_j(modn)$。故当$a_i\ne a_j$时， $a\times a_i,a\times a_j$也代表了不同的同余类

又因为简化剩余系关于$n$乘法封闭， 故$\overline{a{a}_i}$也在简化剩余系中， 因此集合$\{\overline{a_1},\overline{a_2},\cdots ,\overline{a_{\varphi (n)}}\}$和$\{\overline{a{a}_1},\overline{a{a}_2},\cdots ,\overline{a{a}_{\varphi (n)}}\}$都能表示$n$的简化剩余系

由上可得

$$a^{\varphi (n)}{a}_1{a}_2\cdots a_{\varphi (n)}\equiv (a{a}_1)(a{a}_2)\cdots (a{a}_{\varphi (n)})\equiv a_1{a}_2\cdots a_{\varphi (n)}(modn)$$

所以$a^{\varphi (n)}\equiv 1(modn)$得证

推论

内容

若正整数$a,n$互质， 则对于任意正整数$b$， 有$a^b\equiv a^{bmod\varphi (n)}(modn)$

证明

显然， 因为之前证明过了$a^{\varphi (n)}\equiv 1(modn)$

费马小定理

内容

若$p$是质数， 则对于任意整数$a$， 有$a^p\equiv a(modp)$

证明

由欧拉函数得若$a,p$互质， 则$a^{\varphi (p)}\equiv 1(modp)$， 现在$p$是质数， $\varphi (p)=p-1$， 所以有$a^{p-1}\equiv 1(modp)$， 即$a^p\equiv a(modp)$

拓展欧几里得算法

贝组定理

内容

对于$\mathrm{\forall }a,b$， 存在一对整数$x,y$， 使得$a\times x+b\times y=gcd(a,b)$

证明

在欧几里得算法的最后一步有$b=0$， 此时显然有$a\times 1+0\times 0=gcd(a,0)$

若$b>0$， 则有$gcd(a,b)=gcd(b,amodb)$， 假设存在一对正整数$x,y$满足$b\times x+(amodb)\times y=gcd(b,amodb)$

则有

$$\begin{array}{}\text{(8)}& & b\times x+(amodb)\times y\text{(9)}& & =b\times x+(a-\lfloor \frac{a}{b}\rfloor \times b)\times y\text{(10)}& & =a\times y+b\times (x-\lfloor \frac{a}{b}\rfloor \times b)\end{array}$$

另$x_1=y,y_1=x-\lfloor \frac{a}{b}\rfloor \times b$就得到了$a\times x_1+b\times y_1=gcd(a,b)$了

推论

1. 方程$a\times x+b\times y=c$有解， 当且仅当$gcd(a,b)\mid c$

2. 方程$a\times x+b\times y=c$的通解为

   $$\begin{gathered} x=\frac{c}{gcd(a,b)}{x}_0+k\frac{b}{gcd(a,b)} \\ y=\frac{c}{gcd(a,b)}{y}_0-k\frac{a}{gcd(a,b)} \end{gathered}$$

   其中$x_0,y_0$为拓展欧几里得求出的一组特解