安装尼尔等了老半天,翻硬盘找到一本极其古老的数论基础(苏联译本),写一下笔记学习学习(才看到15页就差不多安装完了,LOL)

Note: 博客迁移导致乱码,懒得fix了

如果ai=bi\sum a_i=\sum b_i,除掉删除的一项,所有的项都是cc的倍数,那么删除的一项也是cc的倍数

移项后提取cc得证

a=bq+r,(0r<b)a=bq+r,(0≤r<b)是唯一确定的

证明: 如果存在另一个a=bq1+r1,(0r1<b)a=bq_1+r_1,(0≤r_1<b) 与原式作差后得到0=b(qq1)+(rr1)0=b(q-q_1)+(r-r_1) ,观察到rr1r-r_1bb的倍数,而由前面的限制条件得到 rr1<b|r-r_1|<b,所以rr1=0r-r_1=0

这里使用了作差的技巧

如果a=bq+ca=bq+c,则aabb的公约数集合与bbcc的公约数集合相同,由此推出(a,b)=(b,c)(a,b)=(b,c),这是gcdgcd算法的依据

其实我从来没思考过这是如何证明的orz,大概想到应该是对称性,换了个位置c=abqc=a-bq然后瞪了几秒没啥发现了

上网搜了一下,设dda,ba,b的公约数,既 da,dbd|a,d|b,由 c=abqc=a-bq,得到 c/d=a/dbq/d=mc/d=a/d-bq/d=m,观察到 mm是整数,所以 dcd|c,d也是cc的公约数

自己的想法也只是离正确答案一步之遥,原因在于我只是想过程而没考虑到我需要的结果,很显然我需要知道c/dc/d的结果是什么,可惜我不会构造个简单的整除,弱的一匹(还给老师系列)

显然(am,bm)=(a,b)m(am,bm)=(a,b)m

da,db,(a/d,b/d)=(a,b)/dd|a,d|b,(a/d,b/d)=(a,b)/d ,特别地,a/(a,b)a/(a,b)b/(a,b)b/(a,b)互素

(a,b)=(a/dd,a/dd)=(a/d,b/d)d(a,b)=(a/d*d,a/d*d)=(a/d,b/d)d ←比较有用的式子

定理↓

(a,b)=1(a,b)=1,则(ac,b)=(c,b)(ac,b)=(c,b)

十分显然的结果,因为aabb互质,从唯一分解定理可知只可能是ccbbgcdgcd的贡献

书上的证明:$$(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)(ac,b)=(c,b)

↑还没反应过来就完了,感觉使用姿势比较高只能从猜测得证,很难对未知的结果进行借鉴,突破口是对abcabc的组合的讨论,引出(ac,bc)(ac,bc),可以看作是补全的技巧

**若(a,b)=1(a,b)=1且$$b ac,,则b c$$**
套用上面的方法,因为$$b acb bc,所以,所以b (ac,bc),,既b c$$

集合AA与集合BB中的元素两两互素,则ai\prod{a_i}bi\prod{b_i}也互素

个人证明还是用唯一分解定理,两个集合的元素中分解得到的素数pp都不一样(没有交集)怎么乘都没所谓啊

书里给出的是很厉害的使用定理1,(ai,bj)=1(a_i,b_j)=1,推出(aiak,bj)=(ai,bj)=1(a_ia_k,b_j)=(a_i,b_j)=1,不断迭代得(ai,bj)=1(\prod{a_i},b_j)=1,对bb也用相同的套路,

(ai,bi)=1(\prod{a_i},\prod{b_i})=1

连分式跳过

课后习题部分记入OneNote


n!n!中,素数pp的次方数为[n/pi]\sum[n/p_i]

引用某段解释,以下为20!20!p=2p=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整除)

顺便总结一下其他定理 nn的约数个数:若n=pikin=\prod p_i^{k_i},则约数个数为(1+ki)\prod (1+k_i),由组合可知

a/ba/b的约数个数:若a=pikia=\prod p_i^{k_i},b=qimib=\prod q_i^{m_i},则约数个数为(kimi+1)\prod(k_i-m_i+1)

积性函数:f(p)f(q)=f(pq)f(p)f(q)=f(pq),其中p,qp,q互素(不是一定要素数)

完全积性函数多出的性质:f(nk)=fk(n)f(n^k)=f^k(n)

**对于积性函数,$$\sum_{d n}f(d)=\prod_{i=1}^{m}\sum_{j=0}^{k_i}f(p_i^j),其中,其中mn分解得到的素数个数,分解得到的素数个数,k_i为素数为素数p$$的最高次方数**

证明:顺着证明似乎有难度,我们可以反过来想,不同的约数均为nn分解素数的不同组合,总有一个f(d)=f(pij)f(d)=\prod f(p_i^j),对于不重不漏的约数函数和即为上式的组合(没有系统学过组合不好说话)

f(d)=df(d)=d时既可计算出nn的约数的总和,这是f(d)=dsf(d)=d^s的特殊情况


Mobius

$$μ(n)=0,i^2 n$$ (某个数的平方->某个素数存在平方以上的次数)

μ(n)=(1)kμ(n)=(-1)^k,kknn的素约数个数 (n=pikin=\prod p_i^{k_i})

***$$\sum_{d n}μ(d)f(d)=\prod_{i=1}^{m}(1-f(p_i))$$**

n=1n=1则右式为11

**所以,当f(d)=1f(d)=1时,$$\sum_{d n}μ(d)=[n==1]$$**

f(d)=1df(d)=\frac{1}{d},

**当n>1n>1时,$$\sum_{d n}\frac{μ(d)}{d}=\prod_{i=1}^{m}(1-\frac{1}{p_i})$$**

n=1n=1时,后者为11

补充一下书里缺少(书写风格极其诡异)的但有必要知道的莫比乌斯反演 f(n)f(n)不易求出但dnf(d)\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]φ(a)=[gcd(x,a)==1]的个数,x<ax<a(分别对应书中的δ=gcd(x,a)δ=gcd(x,a)f=1f=1)

S=[δ==1],Sd=[dδ=(x,a)]S'=[δ==1],S_d'=[d|δ=(x,a)]

(x,a)(x,a)dd的倍数只有在ddaa的约数时成立

SdS_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$$

nn变个样子有:

①:$$[(a,b)==1]=\sum_{d (a,b)}μ(d)$$
②:$$(a,b)=\sum_{d (a,b)}φ(d)$$

同余

与等式相似的性质

1.可传递,aca≡c,bcb≡c,则aba≡b(均为模mm)

2.可相加,aba≡b,cdc≡d,则a+cb+da+c≡b+d

3.可移项,a+cb+da+c≡b+d,则a+ccb+dca+c-c≡b+d-c,既ab+dca≡b+d-c

4.任一边可加模mm任意倍数,aba≡b,mk0mk≡0,既a+mkba+mk≡b

5.可逐项相乘,aba≡b,cdc≡d,则acbdac≡bd,akbkak≡bk(kk任意)

两边可以被公约数dd整除(如果dd与模mm互质)

ab,a=a1d,b=b1da≡b,a=a_1d,b=b_1d,则(ab)0(a-b)≡0,既(a1b1)d0(a_1-b_1)d≡0,由(d,m)=1(d,m)=1,得$$(a_1-b_1) m$$
a1b1a_1≡b_1

更多性质

1 两边和模可乘上同一整数,ab(mod m)a≡b(mod \ m),则akbk(mod mk)ak≡bk(mod \ mk)

2 两边和模可被三者任意公约数取模 a1db1d(mod m1d)a_1d≡b_1d(mod \ m_1d),则a1b1(mod m1)a_1≡b_1(mod \ m_1)

3 aba≡b对于模mim_i均成立,则$$(a-b) m_i,,既a≡b(mod \ lcm(m_i))$$

4 若a1db(mod m1d)a_1d≡b(mod \ m_1d),则b/db/d是整数

5 若ab(mod m)a≡b(mod \ m),则(a,m)=(b,m)(a,m)=(b,m)

Last Update:2018/03/03