安装尼尔等了老半天，翻硬盘找到一本极其古老的数论基础 (苏联译本),写一下笔记学习学习 (才看到 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$$ |
更多性质
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