Home 夜深人静补数学
Post
Cancel

夜深人静补数学

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

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

如果\(\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

This post is licensed under CC BY 4.0 by the author.