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

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

如果$\sum a_i=\sum b_i$,除掉删除的一项，所有的项都是$c$的倍数，那么删除的一项也是$c$的倍数

移项后提取$c$得证

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

证明：如果存在另一个$a=b{q}_1+r_1,(0\le 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\ast d,a/d\ast 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_i{a}_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$$ (某个数的平方->某个素数存在平方以上的次数)

$\mu (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)$$**

欧拉函数的补充：

$\phi (a)=[gcd(x,a)==1]$的个数，$x<a$(分别对应书中的$\delta =gcd(x,a)$和$f=1$)

$$S^{\prime }=[\delta ==1],S_d^{\prime }=[d|\delta =(x,a)]$$

而$(x,a)$是$d$的倍数只有在$d$是$a$的约数时成立

$S_d^{\prime }$成为$$[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\equiv c$,$b\equiv c$,则$a\equiv b$(均为模$m$)

2.可相加，$a\equiv b$,$c\equiv d$,则$a+c\equiv b+d$

3.可移项，$a+c\equiv b+d$,则$a+c-c\equiv b+d-c$,即$a\equiv b+d-c$

4.任一边可加模$m$任意倍数，$a\equiv b$,$mk\equiv 0$,即$a+mk\equiv b$

5.可逐项相乘，$a\equiv b$,$c\equiv d$,则$ac\equiv bd$,$ak\equiv bk$($k$任意)

两边可以被公约数$d$整除 (如果$d$与模$m$互质)

$a\equiv b,a=a_{1}d,b=b_{1}d$,则$(a-b)\equiv 0$,即$(a_1-b_1)d\equiv 0$,由$(d,m)=1$,得$$(a_1-b_1)

m$$

$$a_1\equiv b_1$$

更多性质

1 两边和模可乘上同一整数，$a\equiv b(modm)$,则$ak\equiv bk(modmk)$

2 两边和模可被三者任意公约数取模 $a_{1}d\equiv b_{1}d(mod{m}_{1}d)$,则$a_1\equiv b_1(mod{m}_1)$

3 $a\equiv b$对于模$m_i$均成立，则$$(a-b)

m_i$,即$a≡b(mod \ lcm(m_i))$$

4 若$a_{1}d\equiv b(mod{m}_{1}d)$,则$b/d$是整数

5 若$a\equiv b(modm)$,则$(a,m)=(b,m)$

Last Update:2018/03/03