安装尼尔等了老半天,翻硬盘找到一本极其古老的数论基础(苏联译本),写一下笔记学习学习(才看到15页就差不多安装完了,LOL)
Note: 博客迁移导致乱码,懒得fix了
如果∑ai=∑bi,除掉删除的一项,所有的项都是c的倍数,那么删除的一项也是c的倍数
移项后提取c得证
a=bq+r,(0≤r<b)是唯一确定的
证明: 如果存在另一个a=bq1+r1,(0≤r1<b)
与原式作差后得到0=b(q−q1)+(r−r1)
,观察到r−r1是b的倍数,而由前面的限制条件得到
∣r−r1∣<b,所以r−r1=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中的元素两两互素,则∏ai与∏bi也互素
个人证明还是用唯一分解定理,两个集合的元素中分解得到的素数p都不一样(没有交集)怎么乘都没所谓啊
书里给出的是很厉害的使用定理1,(ai,bj)=1,推出(aiak,bj)=(ai,bj)=1,不断迭代得(∏ai,bj)=1,对b也用相同的套路,
得(∏ai,∏bi)=1
连分式跳过
课后习题部分记入OneNote
n!中,素数p的次方数为∑[n/pi]
引用某段解释,以下为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=∏piki,则约数个数为∏(1+ki),由组合可知
a/b的约数个数:若a=∏piki,b=∏qimi,则约数个数为∏(ki−mi+1)
积性函数:f(p)f(q)=f(pq),其中p,q互素(不是一定要素数)
完全积性函数多出的性质:f(nk)=fk(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)=∏f(pij),对于不重不漏的约数函数和即为上式的组合(没有系统学过组合不好说话)
f(d)=d时既可计算出n的约数的总和,这是f(d)=ds的特殊情况
Mobius
$$μ(n)=0,i^2 |
n$$ (某个数的平方->某个素数存在平方以上的次数) |
μ(n)=(−1)k,k为n的素约数个数 (n=∏piki)
***$$\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)=d1,
**当n>1时,$$\sum_{d |
n}\frac{μ(d)}{d}=\prod_{i=1}^{m}(1-\frac{1}{p_i})$$** |
n=1时,后者为1
补充一下书里缺少(书写风格极其诡异)的但有必要知道的莫比乌斯反演
f(n)不易求出但∑d∣nf(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],Sd′=[d∣δ=(x,a)]
而(x,a)是d的倍数只有在d是a的约数时成立
Sd′成为$$[d |
x]的个数,既a/d$$ |
**那么$$φ(n)=\sum_{d |
n}μ(d) \frac{n}{d}$$** |
**还有另一常见反演$$\sum_{d |
n}φ(d)=n$$** |
参考数论变换入门:
重新把前面两个式子写出来
①:$$\sum_{d |
n}μ(d)=[n==1]$$(此处指个数) |
对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=a1d,b=b1d,则(a−b)≡0,既(a1−b1)d≡0,由(d,m)=1,得$$(a_1-b_1) |
m$$ |
a1≡b1
更多性质
1 两边和模可乘上同一整数,a≡b(mod m),则ak≡bk(mod mk)
2 两边和模可被三者任意公约数取模 a1d≡b1d(mod m1d),则a1≡b1(mod m1)
3 a≡b对于模mi均成立,则$$(a-b) |
m_i,既a≡b(mod \ lcm(m_i))$$ |
4 若a1d≡b(mod m1d),则b/d是整数
5 若a≡b(mod m),则(a,m)=(b,m)
Last Update:2018/03/03