安装尼尔等了老半天,翻硬盘找到一本极其古老的数论基础(苏联译本),写一下笔记学习学习(才看到15页就差不多安装完了,LOL)
如果$\sum a_i=\sum b_i$,除掉删除的一项,所有的项都是$c$的倍数,那么删除的一项也是$c$的倍数
移项后提取$c$得证
$a=bq+r,(0≤r<b)$是唯一确定的
证明: 如果存在另一个$a=bq_1+r_1,(0≤r_1<b)$与原式作差后得到$0=b(q-q_1)+(r-r_1)$,观察到$r-r_1$是$b$的倍数,而由前面的限制条件得到$|r-r_1|<b$,所以$r-r_1=0$
这里使用了作差的技巧
如果$a=bq+c$,则$a$和$b$的公约数集合与$b$和$c$的公约数集合相同,由此推出$(a,b)=(b,c)$,这是$gcd$算法的依据
其实我从来没思考过这是如何证明的orz,大概想到应该是对称性,换了个位置$c=a-bq$然后瞪了几秒没啥发现了
上网搜了一下,设$d$为$a,b$的公约数,既$d|a,d|b$,由$c=a-bq$,得到$c/d=a/d-bq/d=m$,观察到$m$是整数,所以$d|c$,d也是$c$的公约数
自己的想法也只是离正确答案一步之遥,原因在于我只是想过程而没考虑到我需要的结果,很显然我需要知道$c/d$的结果是什么,可惜我不会构造个简单的整除,弱的一匹(还给老师系列)
显然$(am,bm)=(a,b)m$
设$d|a,d|b,(a/d,b/d)=(a,b)/d$,特别地,$a/(a,b)$与$b/(a,b)$互素
$(a,b)=(a/d*d,a/d*d)=(a/d,b/d)d$ ←比较有用的式子
定理↓
若$(a,b)=1$,则$(ac,b)=(c,b)$
十分显然的结果,因为$a$与$b$互质,从唯一分解定理可知只可能是$c$对$b$有$gcd$的贡献
书上的证明:$(ac,b)|ac$且$(ac,b)|bc$(★),由公约数集合相同的定理,$(ac,b)|[(ac,bc)=(a,b)c=c]$ ←有点绕
又$(ac,b)|b$,所以$(ac,b)|(c,b)$ ←很跳
反之,$(c,b)|ac$和$(c,b)|b$,所以$(c,b)|(ac,b)$
既$(ac,b)=(c,b)$
↑还没反应过来就完了,感觉使用姿势比较高只能从猜测得证,很难对未知的结果进行借鉴,突破口是对$abc$的组合的讨论,引出$(ac,bc)$,可以看作是补全的技巧
若$(a,b)=1$且$b|ac$,则$b|c$
套用上面的方法,因为$b|ac$且$b|bc$,所以$b|(ac,bc)$,既$b|c$
集合$A$与集合$B$中的元素两两互素,则$\prod{a_i}$与$\prod{b_i}$也互素
个人证明还是用唯一分解定理,两个集合的元素中分解得到的素数$p$都不一样(没有交集)怎么乘都没所谓啊
书里给出的是很厉害的使用定理1,$(a_i,b_j)=1$,推出$(a_ia_k,b_j)=(a_i,b_j)=1$,不断迭代得$(\prod{a_i},b_j)=1$,对$b$也用相同的套路,
得$(\prod{a_i},\prod{b_i})=1$
连分式跳过
课后习题部分记入OneNote
$n!$中,素数$p$的次方数为$\sum[n/p_i]$
引用某段解释,以下为$20!$时$p=2$的情况
2、4、6、8、10、12、14、16、18、20能被2整除
4、8、12、16、20能被4整除(即被2除一次后还能被2整除)
8、16能被8整除(即被2除两次后还能被2整除)
16能被16整除(即被2除三次后还能被2整除)
顺便总结一下其他定理 $n$的约数个数:若$n=\prod p_i^{k_i}$,则约数个数为$\prod (1+k_i)$,由组合可知
$a/b$的约数个数:若$a=\prod p_i^{k_i}$,$b=\prod q_i^{m_i}$,则约数个数为$\prod(k_i-m_i+1)$
积性函数:$f(p)f(q)=f(pq)$,其中$p,q$互素(不是一定要素数)
完全积性函数多出的性质:$f(n^k)=f^k(n)$
对于积性函数,$\sum_{d|n}f(d)=\prod_{i=1}^{m}\sum_{j=0}^{k_i}f(p_i^j)$,其中$m$为$n$分解得到的素数个数,$k_i$为素数$p$的最高次方数
证明:顺着证明似乎有难度,我们可以反过来想,不同的约数均为$n$分解素数的不同组合,总有一个$f(d)=\prod f(p_i^j)$,对于不重不漏的约数函数和即为上式的组合(没有系统学过组合不好说话)
$f(d)=d$时既可计算出$n$的约数的总和,这是$f(d)=d^s$的特殊情况
Mobius
$μ(n)=0,i^2|n$ (某个数的平方->某个素数存在平方以上的次数)
$μ(n)=(-1)^k$,$k$为$n$的素约数个数 ($n=\prod p_i^{k_i}$)
*$\sum_{d|n}μ(d)f(d)=\prod_{i=1}^{m}(1-f(p_i))$
若$n=1$则右式为$1$
所以,当$f(d)=1$时,$\sum_{d|n}μ(d)=[n==1]$
令$f(d)=\frac{1}{d}$,
当$n>1$时,$\sum_{d|n}\frac{μ(d)}{d}=\prod_{i=1}^{m}(1-\frac{1}{p_i})$
$n=1$时,后者为$1$
补充一下书里缺少(书写风格极其诡异)的但有必要知道的莫比乌斯反演 $f(n)$不易求出但$\sum_{d|n}f(d)$容易求得时
令$F(n)=\sum_{d|n}f(d)$ $=>$ $f(n)=\sum_{d|n}μ(d)F(n/d)$
反过来也行$F(n)=\sum_{n|d}f(d)$ $=>$ $f(n)=\sum_{n|d}μ(d/n)F(d)$
欧拉函数的补充:
$φ(a)=[gcd(x,a)==1]$的个数,$x<a$(分别对应书中的$δ=gcd(x,a)$和$f=1$)
$S'=[δ==1],S_d'=[d|δ=(x,a)]$
而$(x,a)$是$d$的倍数只有在$d$是$a$的约数时成立
$S_d'$成为$[d|x]$的个数,既$a/d$
那么$φ(n)=\sum_{d|n}μ(d) \frac{n}{d}$
还有另一常见反演$\sum_{d|n}φ(d)=n$
参考数论变换入门:
重新把前面两个式子写出来
①:$\sum_{d|n}μ(d)=[n==1]$(此处指个数)
②:$\sum_{d|n}φ(d)=n$
对$n$变个样子有:
①:$[(a,b)==1]=\sum_{d|(a,b)}μ(d)$
②:$(a,b)=\sum_{d|(a,b)}φ(d)$
同余
与等式相似的性质
1.可传递,$a≡c$,$b≡c$,则$a≡b$(均为模$m$)
2.可相加,$a≡b$,$c≡d$,则$a+c≡b+d$
3.可移项,$a+c≡b+d$,则$a+c-c≡b+d-c$,既$a≡b+d-c$
4.任一边可加模$m$任意倍数,$a≡b$,$mk≡0$,既$a+mk≡b$
5.可逐项相乘,$a≡b$,$c≡d$,则$ac≡bd$,$ak≡bk$($k$任意)
两边可以被公约数$d$整除(如果$d$与模$m$互质)
$a≡b,a=a_1d,b=b_1d$,则$(a-b)≡0$,既$(a_1-b_1)d≡0$,由$(d,m)=1$,得$(a_1-b_1)|m$
$a_1≡b_1$
更多性质
1 两边和模可乘上同一整数,$a≡b(mod \ m)$,则$ak≡bk(mod \ mk)$
2 两边和模可被三者任意公约数取模 $a_1d≡b_1d(mod \ m_1d)$,则$a_1≡b_1(mod \ m_1)$
3 $a≡b$对于模$m_i$均成立,则$(a-b)|m_i$,既$a≡b(mod \ lcm(m_i))$
4 若$a_1d≡b(mod \ m_1d)$,则$b/d$是整数
5 若$a≡b(mod \ m)$,则$(a,m)=(b,m)$
*Last Update:2018/03/03*